图的遍历 深度优先遍历 宽度优先遍历

#include"c2.h" #include"c3.h" #include"c1.h" int chose() { int i; printf("*******************************\n"); printf("* 试验五 无向图的遍历 *\n"); printf("*******************************\n"); printf(" 1、创建邻接表 \n"); printf(" 2、深度优先遍历 \n"); printf(" 3、广度优先遍历 \n"); printf(" 4、退出 \n"); printf("*******************************\n"); printf("请选择："); fflush(stdin); scanf("%d",&i); return i; } int LocateVex(ALGraph G,VertexType u) {//返回顶点u在图中的位置 int i; for(i=0;i<G.vexnum;++i) if(strcmp(u,G.vertices[i].data)==0) return i; return -1; } void CreateGraph(ALGraph &G) {//建图 int i,j,k; char c; ElemType e; VertexType v1,v2; printf("请输入图的顶点数，边数："); scanf("%d%c%d",&G.vexnum,&c,&G.arcnum); printf("请输入%d个顶点的值（10个字符）：\n",G.vexnum); for(i=1;i<=G.vexnum;i++){//输入顶点值 printf("请输入第%d个顶点的值：",i); scanf("%s",&G.vertices[i-1].data); G.vertices[i-1].firstarc=NULL;//初始化边 } for(i=1;i<=G.arcnum;i++){//输入边 printf("输入第%d条边的弧尾和弧头（以空格作为间隔）：",i); scanf("%s%s",v1,v2); j=LocateVex(G,v1);//求v1的在图中的位置 k=LocateVex(G,v2);//求v2的在图中的位置 e.adjvex=k; ListInsert(G.vertices[j].firstarc,1,e); e.adjvex=j; ListInsert(G.vertices[k].firstarc,1,e); } printf("各顶点的邻接点为：\n"); for(i=0;i<G.vexnum;i++){ printf("G.vertices[%d]=%s :",i,G.vertices[i].data);//每个点都是头结点 LinkList p = G.vertices[i].firstarc; while(p){//结点存在，打出每个顶点的邻接点 printf("%s ",G.vertices[p->data.adjvex].data); p = p->nextarc; } printf("\n"); } } int visited[MAX_VERTEX_NUM];//全局变量 void DFSTraverse(ALGraph G)//深度优先遍历 { int i,v; char V[MAX_NAME]; for(i=0;i<G.vexnum;i++) visited[i]=0; printf("请输入起始结点："); scanf("%s",&V); v=LocateVex(G,V); printf("深度优先搜索结果为：\n"); DFS(G,v);//v-1为v点在图中的位置 for(i=0;i<G.vexnum;i++){ if(visited[i]==0) DFS(G,i); } printf("\n"); } void DFS(ALGraph G,int v) { int w; visited[v]=1; printf("%s ",G.vertices[v].data);//打印结点 for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){ if(visited[w]==0)//如果标志结点为0则遍历该结点 DFS(G,w); } } int FirstAdjVex(ALGraph G,int v) { LinkList p; p=G.vertices[v].firstarc; if(!p) return -1;//如果不存在v点的邻接点则返回负数 else return p->data.adjvex;//返回邻接点所在的位置 } int NextAdjVex(ALGraph G,int v,int w) {//返回第v结点相对于w邻接点的下一个结点 LinkList p; p=G.vertices[v].firstarc; while(p&&p->data.adjvex!=w) p=p->nextarc; if(p->data.adjvex==w&&p->nextarc) return p->nextarc->data.adjvex; else return -1; } void BFSTraverse(ALGraph G) {//广度优先搜索 int i; int v; int w; LinkQueue Q; QElemType u; for(i=0;i<G.vexnum;i++) visited[i]=0; InitQueue(Q);//初始化链队列 printf("请输入起始点："); scanf("%d",&v); printf("广度优先搜索结果为：\n"); if(visited[v-1]==0){ visited[v-1]=1; printf("%s ",G.vertices[v-1].data); EnQueue(Q,v-1); while(!QueueEmpty(Q)){ DeQueue(Q,u); for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)){ if(visited[w]==0){ visited[w]=1; printf("%s ",G.vertices[w].data); EnQueue(Q,w); } } } } for(i=0;i<G.vexnum;i++){//当所建立的图不是连通图时，该步骤是用来遍历剩下的结点 if(visited[i]==0){ visited[i]=1; printf("%s ",G.vertices[i].data); EnQueue(Q,i); while(!QueueEmpty(Q)){ DeQueue(Q,u); for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)){ if(visited[w]==0){ visited[w]=1; printf("%s ",G.vertices[w].data); EnQueue(Q,w); } } } } } printf("\n"); }