无向图的遍历演示（两种遍历方式）

#define MAX_NAME 3 // 顶点字符串的最大长度+1 #define MAX_VERTEX_NUM 50 typedef char VertexType[MAX_NAME]; // 字符串类型 typedef int QElemType; // 队列类型 #include<stdio.h> #include<stdlib.h> #include <iostream> #include <fstream> #include <cstdlib> #include <string> using namespace std; int visite[MAX_VERTEX_NUM]; // 访问标志数组(全局量) enum VisitIf{unvisited,visited}; struct EBox { VisitIf mark; // 访问标记 int ivex,jvex; // 该边依附的两个顶点的位置 EBox *ilink,*jlink; // 分别指向依附这两个顶点的下一条边 }; struct VexBox { string data; EBox *firstedge; // 指向第一条依附该顶点的边 }; struct AMLGraph { VexBox adjmulist[MAX_VERTEX_NUM]; int vexnum,edgenum; // 无向图的当前顶点数和边数 }; typedef struct QNode { QElemType data; QNode *next; }*QueuePtr; struct LinkQueue { QueuePtr front,rear; // 队头、队尾指针 }; int CreateGraph(AMLGraph &G); int LocateVex(AMLGraph G,string u); void Display(AMLGraph G); void MarkUnvizited(AMLGraph G); void DFS(AMLGraph G,int v); int visit(string v); void BFSTraverse(AMLGraph G,int(*Visit)(string),int v); int InitQueue(LinkQueue &Q); int DeQueue(LinkQueue &Q,QElemType &e); int QueueEmpty(LinkQueue Q); int EnQueue(LinkQueue &Q,QElemType e); int NextAdjVex(AMLGraph G,string v,string w); int FirstAdjVex(AMLGraph G,string v); string GetVex(AMLGraph G,int v); int CreateGraph(AMLGraph &G) { int i,j,k; string va,vb; EBox *p; printf("请输入无向图G的顶点数,边数(以逗号作为间隔): "); scanf("%d,%d",&G.vexnum,&G.edgenum); getchar(); printf("请输入%d个顶点的值:\n",G.vexnum); for(i=0;i<G.vexnum;++i) // 构造顶点向量 { cin>>G.adjmulist[i].data; G.adjmulist[i].firstedge=NULL; } printf("请顺序输入每条边的两个端点(以空格作为间隔):\n"); for(k=0;k<G.edgenum;++k) // 构造表结点链表 { cin>>va>>vb; i=LocateVex(G,va); // 一端 j=LocateVex(G,vb); // 另一端 p=(EBox*)malloc(sizeof(EBox)); p->mark=unvisited; // 设初值 p->ivex=i; p->jvex=j; p->ilink=G.adjmulist[i].firstedge; // 插在表头 G.adjmulist[i].firstedge=p; p->jlink=G.adjmulist[j].firstedge; // 插在表头 G.adjmulist[j].firstedge=p; } return 1; } int LocateVex(AMLGraph G,string u) { // 初始条件: 无向图G存在,u和G中顶点有相同特征 // 操作结果: 若G中存在顶点u,则返回该顶点在无向图中位置;否则返回-1 int i; for(i=0;i<G.vexnum;++i) if(u==G.adjmulist[i].data) return i; return -1; } void Display(AMLGraph G) { // 输出无向图的邻接多重表G int i; EBox *p; MarkUnvizited(G); // 置边的访问标记为未被访问 printf("%d个顶点：\n",G.vexnum); for(i=0;i<G.vexnum;++i) cout<<G.adjmulist[i].data<<" "; printf("\n%d条边:\n",G.edgenum); for(i=0;i<G.vexnum;i++) { p=G.adjmulist[i].firstedge; while(p) { if(p->ivex==i) // 边的i端与该顶点有关 { if(!p->mark) // 只输出一次 { cout<<G.adjmulist[i].data<<"-"<<G.adjmulist[p->jvex].data; p->mark=visited; printf("\n"); } p=p->ilink; } else // 边的j端与该顶点有关 { if(!p->mark) // 只输出一次 { cout<<G.adjmulist[p->ivex].data<<"-"<<G.adjmulist[i].data; p->mark=visited; printf("\n"); } p=p->jlink; } } } } void MarkUnvizited(AMLGraph G) { // 置边的访问标记为未被访问 int i; EBox *p; for(i=0;i<G.vexnum;i++) { p=G.adjmulist[i].firstedge; while(p) { p->mark=unvisited; if(p->ivex==i) p=p->ilink; else p=p->jlink; } } } void DFS(AMLGraph G,int v) { int j; EBox *p; visit(G.adjmulist[v].data); visite[v]=1; p=G.adjmulist[v].firstedge; while(p) { j=p->ivex==v?p->jvex:p->ivex; if(!visite[j]) DFS(G,j); p=p->ivex==v?p->ilink:p->jlink; } } int InitQueue(LinkQueue &Q) { // 构造一个空队列Q if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)))) exit(0); Q.front->next=NULL; return 1; } int EnQueue(LinkQueue &Q,QElemType e) { // 插入元素e为Q的新的队尾元素 QueuePtr p; if(!(p=(QueuePtr)malloc(sizeof(QNode)))) // 存储分配失败 exit(0); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return 1; } int QueueEmpty(LinkQueue Q) { // 若Q为空队列,则返回TRUE,否则返回FALSE if(Q.front==Q.rear) return 1; else return 0; } int DeQueue(LinkQueue &Q,QElemType &e) { // 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR QueuePtr p; if(Q.front==Q.rear) return 0; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; free(p); return 1; } string GetVex(AMLGraph G,int v) { // 初始条件: 无向图G存在,v是G中某个顶点的序号。操作结果: 返回v的值 if(v>=G.vexnum||v<0) exit(0); return G.adjmulist[v].data; } int FirstAdjVex(AMLGraph G,string v) { // 初始条件: 无向图G存在,v是G中某个顶点 // 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 int i; i=LocateVex(G,v); if(i<0) return -1; if(G.adjmulist[i].firstedge) // v有邻接顶点 if(G.adjmulist[i].firstedge->ivex==i) return G.adjmulist[i].firstedge->jvex; else return G.adjmulist[i].firstedge->ivex; else return -1; } int NextAdjVex(AMLGraph G,string v,string w) { // 初始条件: 无向图G存在,v是G中某个顶点,w是v的邻接顶点 // 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。 // 若w是v的最后一个邻接点,则返回-1 int i,j; EBox *p; i=LocateVex(G,v); // i是顶点v的序号 j=LocateVex(G,w); // j是顶点w的序号 if(i<0||j<0) // v或w不是G的顶点 return -1; p=G.adjmulist[i].firstedge; // p指向顶点v的第1条边 while(p) if(p->ivex==i&&p->jvex!=j) // 不是邻接顶点w(情况1) p=p->ilink; // 找下一个邻接顶点 else if(p->jvex==i&&p->ivex!=j) // 不是邻接顶点w(情况2) p=p->jlink; // 找下一个邻接顶点 else // 是邻接顶点w break; if(p&&p->ivex==i&&p->jvex==j) // 找到邻接顶点w(情况1) { p=p->ilink; if(p&&p->ivex==i) return p->jvex; else if(p&&p->jvex==i) return p->ivex; } if(p&&p->ivex==j&&p->jvex==i) // 找到邻接顶点w(情况2) { p=p->jlink; if(p&&p->ivex==i) return p->jvex; else if(p&&p->jvex==i) return p->ivex; } return -1; } void BFSTraverse(AMLGraph G,int(*Visit)(string),int v) { int j,u,w; string u1; LinkQueue Q; for(j=0;j<G.vexnum;j++) visite[j]=0; // 置初值 InitQueue(Q); // 置空的辅助队列Q for(j=0;j<G.vexnum;j++) if(!visite[v]) // v尚未访问 { visite[v]=1; // 设置访问标志为TRUE(已访问) visit(G.adjmulist[v].data); EnQueue(Q,v); // v入队列 while(!QueueEmpty(Q)) // 队列不空 { DeQueue(Q,u); // 队头元素出队并置为u u1=GetVex(G,u); for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,GetVex(G,w))) if(!visite[w]) // w为u的尚未访问的邻接顶点的序号 { visite[w]=1; visit(G.adjmulist[w].data); EnQueue(Q,w); } } } printf("\n"); } int visit(string v) { cout<<v<<" "; return 1; } void main() { int k,h; char e,y; AMLGraph g; cout<<"******************************图的遍历******************************"<<endl; cout<<"本程序以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。"<<endl; cout<<"欢迎使用，下面根据提示开始操作。"<<endl; CreateGraph(g); Display(g); do { getchar(); printf("\n请您选择遍历的方式（深度：D/广度：B)"); scanf("%c",&e); getc