// Graph.cpp : Defines the entry point for the console application.
//邻接矩阵
#include "stdafx.h"
// test.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <iostream>
#include <queue>
using namespace std;
//图的数组（邻接矩阵）存储
#define MAX_VERTEX_NUM 20 //最大顶点个数
//顶点关系，对无权图，用1(是)或0(否)表示相邻否
bool visited[20];
typedef struct
{
char* vexs[MAX_VERTEX_NUM];//顶点向量,指针数组，用于存储顶点
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];////邻接矩阵 .顶点关系，对无权图，用1(是)或0(否)表示相邻否
int vexnum,arcnum;
}MGraph;
int LocateVex(MGraph G, char* u)
{//操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1
int i ;
for(i = 0; i < G.vexnum; ++i)
if(strcmp(G.vexs[i],u) == 0) //strcmp的参数必须是const char*
return i;
return -1;
}
void CreateFAG(MGraph *G)
{//采用数组(邻接矩阵)表示法,由文件构造没有相关信息的无向图G
int i, j ,k ;
int N = 3; //N表示顶点字符数 在开辟空间时用到
char filename[30];
char va[5];
char vb[5];
FILE* pFile;
printf("请输入数据文件名:");
scanf("%s",filename); //请输入数据文件名 //D:\\Graph\\1.txt or D:/Graph/1.txt
pFile = fopen(filename, "r");
//pFile = fopen("1.txt","r");
if(pFile == NULL)
{
printf("fail to read");
getchar();
getchar();
exit(1);
}
fscanf(pFile, "%d", &(*G).vexnum);
fscanf(pFile, "%d", &(*G).arcnum);
for(i = 0; i < G->vexnum; i++){
G->vexs[i] = (char*)malloc(N*sizeof(char));//分配顶点数目
}
for(i = 0; i < G->vexnum; i++){
fscanf(pFile, "%s", G->vexs[i]);
}//存储节点
for(i = 0 ; i < (*G).vexnum; ++i) //初始化邻接矩阵
for(j = 0; j <(*G).vexnum; ++j)
{
(*G).arcs[i][j] = 0;
}
for(k = 0; k < (*G).arcnum; ++k)
{
fscanf(pFile, "%s %s",va,vb);
i = LocateVex(*G, va);
j = LocateVex(*G, vb);
(*G).arcs[i][j] = (*G).arcs[j][i] = 1;//无向图
}
fclose(pFile);
return;
}
//图G中顶点k的第一个邻接顶点
int FirstVex(MGraph G, int k){
if(k >= 0 && k < G.vexnum){// k合理
for(int i = 0; i < G.vexnum; i++)
if(G.arcs[k][i] != 0) return i ;//顶点相连，则返回顶点位置
}
return -1;
}
//图G中顶点i的第j个邻接顶点的下一个邻接顶点
int NextVex(MGraph G, int i, int j){
if( i >= 0 && i <G.vexnum && j >=0 && j < G.vexnum){//i,j合理
for(int k = j+1; k < G.vexnum; k++)
if(G.arcs[i][k] != 0) return k;
}
return -1;
}
//深度优先遍历 test.exe!mainCRTStartup() Line 371 C
void DFS(MGraph G, int k){
int i ;
visited[k] = true;
printf("%s ", G.vexs[k]);////访问第K个节点
for( i = FirstVex(G,k); i >= 0; i = NextVex(G, k, i))
if(!visited[i]) DFS(G, i);//对K的尚未访问的邻接顶点i递归调用DFS
}
void DFStrieval(MGraph G)
{
int i;
for( i = 0; i< G.vexnum;i++)
{
if(visited[i] != true)
DFS(G, i);
}
}
//---------广度遍历-------------
void BFS(MGraph G)
{
for(int n = 0; n < G.vexnum; n++)
{
int k ;
queue<int> SQ; //辅助队列SQ ,存储顶点的位置
if(!visited[n]){//i未访问
visited[n] = true;
printf("%s ", G.vexs[n]);
SQ.push(n);
while(!SQ.empty()){
k = SQ.front();
SQ.pop();
for(int w = FirstVex(G, k); w >= 0; w = NextVex(G, k ,w))
if(!visited[w]){ //w为k的尚未访问的邻接顶点
visited[w] = true;
printf("%s ", G.vexs[w]);
SQ.push(w);
}
}//while
}
}
}
int main(){
MGraph *G;
G = (MGraph*)malloc(sizeof(MGraph));
CreateFAG(G);
memset(visited, 0, sizeof(visited));
printf("深度遍历：\n");
//DFS(*G, 1);//从第二个节点开始
DFStrieval(*G);
memset(visited, 0, sizeof(visited));
printf("\n");
printf("广度遍历：\n");
BFS(*G); //从第一个节点开始
getchar();
getchar();
return 0;
}
1.txt
8 9
V0 V1 V2 V3 V4 V5 V6 V7
V0 V1
V0 V3
V0 V4
V1 V2
V1 V4
V2 V5
V3 V6
V4 V6
V6 V7
