Graph(邻接矩阵)-两种遍历

#include "C1.h" int num=0; int num1=0; #define INFINIT 10000 //最大值 #define MAX_VERTEX_NUM 20 //最大顶点个数 typedef char VertexType[10]; //顶点名称字符串的最大长度 typedef struct{ VertexType vexs[MAX_VERTEX_NUM]; //顶点向量 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧数 }MGraph; int LocateVex(MGraph G, VertexType u) { // 初始条件:图G存在,u和G中顶点有相同特征 // 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 int i; for(i=0;i<G.vexnum;++i) if(strcmp(u,G.vexs[i])==0) return i; return -1; } /* void CreateG(MGraph &G) { // 采用数组(邻接矩阵)表示法，构造有向网G int i,j,k,w; VertexType v1,v2; // 顶点类型 printf("请输入有向网G的顶点数,弧数："); scanf("%d,%d",&G.vexnum,&G.arcnum); printf("请输入%d个顶点的值：\n",G.vexnum); for(i=0;i<G.vexnum;++i) // 构造顶点向量 scanf("%s",G.vexs[i]); // 根据顶点信息的类型，输入顶点信息 for(i=0;i<G.vexnum;++i) // 初始化二维邻接矩阵(弧(边)信息) for(j=0;j<G.vexnum;++j) { G.arcs[i][j]=INFINIT; // 图，不相邻 } printf("请输入%d条弧的弧尾,弧头,权值(用回车分隔)：\n",G.arcnum); for(k=0;k<G.arcnum;++k) { printf("第%d条弧：\n",(k+1)); scanf("%s%s%d",v1,v2,&w); //不能用逗号隔开，因为逗号也会作为字符串的内容 //用回车隔开 i=LocateVex(G,v1); // 弧尾的序号 j=LocateVex(G,v2); // 弧头的序号 G.arcs[i][j]=w; // 有向网 //G.arcs[j][i]=w; // 无向网 } } */ void CreateG(MGraph &G) { // 采用数组(邻接矩阵)表示法，构造有向网G G.vexnum=9; G.arcnum=9; VertexType vexs0[MAX_VERTEX_NUM]={"v1","v2","v3","v4","v5","v6","v7","v8","v9"}; for(int i=0;i<G.vexnum;i++) strcpy(G.vexs[i],vexs0[i]);//字符串赋值 int arcs0[MAX_VERTEX_NUM][MAX_VERTEX_NUM]= { {0,1,1,0,0,0,0,0,0}, {1,0,0,1,1,0,0,0,0}, {1,0,0,0,0,1,1,0,0}, {0,1,0,0,0,0,0,1,0}, {0,1,0,0,0,0,0,1,0}, {0,0,1,0,0,0,1,0,0}, {0,0,1,0,0,1,0,0,0}, {0,0,0,1,1,0,0,0,0}, {0,0,0,0,0,0,0,0,0}, }; for(i=0;i<G.vexnum;i++) for(int j=0;j<G.vexnum;j++) G.arcs[i][j]=arcs0[i][j]; } void print(MGraph G) { int i,j; printf(" "); for(i=0;i<G.vexnum;i++) printf("%7s",G.vexs[i]); printf("\n"); for(i=0;i<G.vexnum;i++) { printf("%7s",G.vexs[i]); for(j=0;j<G.vexnum;j++) printf("%7d",G.arcs[i][j]); printf("\n"); } } int FirstAdjVex(MGraph G,int v) { for(int i=0;i<G.vexnum;i++) if(G.arcs[v][i]!=0&&G.arcs[v][i]!=INFINIT) return i; return -1; } int NextAdjVex(MGraph G,int v,int w) { for(int i=w+1;i<G.vexnum;i++) if(G.arcs[v][i]!=0&&G.arcs[v][i]!=INFINIT) return i; return -1; } Boolean visited[MAX_VERTEX_NUM]; void DFS(MGraph G, int v) { visited[v]=TRUE; printf("%s ",G.vexs[v]); for(int w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w)) if(!visited[w]) DFS(G,w); } void DFSTraverse(MGraph G) { for(int v=0;v<G.vexnum;++v) visited[v]=FALSE; for(v=0;v<G.vexnum;++v) { if(!visited[v]) { num++; DFS(G,v); } } } void BFSTraverse(MGraph G) { int v,u,w; for (v=0; v<G.vexnum; ++v) visited[v] = FALSE; //初始化访问标志 int Q[MAX_VERTEX_NUM]; // 置空的辅助队列Q int front=0,rear=0; for ( v=0; v<G.vexnum; ++v ) if ( !visited[v]) { // v 尚未访问 num1++; visited[v] = TRUE; printf("%s ",G.vexs[v]); // 访问v Q[rear++]=v; // v入队列 while (front!=rear) { u=Q[front++]; // 队头元素出队并置为u for(w=FirstAdjVex(G, u); w>=0; w=NextAdjVex(G,u,w)) if ( ! visited[w]) { visited[w]=TRUE; printf("%s ",G.vexs[w]); // 访问w Q[rear++]=w; // 访问的顶点w入队列 } // if } // while } } // BFSTraverse void main() { MGraph G; CreateG(G); print(G); printf("\n\n深度遍历序列: "); DFSTraverse(G); printf("\n"); printf("\n广度遍历序列: "); BFSTraverse(G); printf("\n\n连通分量数(num)=%d\n",num); printf("\n连通分量数(num1)=%d\n\n",num1); }