图的遍历源代码.docx
图的遍历源代码图的遍历顺序有两种：深度优先搜索和广度优先搜索。深度优先遍历的基本思想是：首先从图中某个顶点v0出发，访问此顶点，然后依次从v0相邻的顶点出发深度优先遍历，直至图中所有与v0路径相通的顶点都被访问了；若此时尚有顶点未被访问，则从中选一个顶点作为起始点，重复该步骤直到所有的顶点都被访问。而广度优先遍历首先从图的某个顶点v0出发，访问了v0之后，依次访问与v0相邻的未被访问的顶点，然后分别从这些顶点出发，广度优先遍历，直至所有的顶点都被访问完。 流程图如下： 程序代码如下： #include<iostream> #include<process.h> #include<stdlib.h> #define MaxVerNum 50 using namespace std; struct edgenode int endver; int inform; edgenode* edgenext; ; struct vexnode char vertex; edgenode* edgelink; ; struct Graph vexnode adjlistsMaxVerNum; int vexnum; int arcnum; ; /队列的定义及相关函数的实现 struct QueueNode int nData; QueueNode* next; ; struct QueueList QueueNode* front; QueueNode* rear; ; void EnQueue(QueueList* Q,int e) QueueNode *q=new QueueNode; q->nData=e; q->next=NULL; if(Q=NULL) return; if(Q->rear=NULL) Q->front=Q->rear=q; else Q->rear->next=q; Q->rear=Q->rear->next; void DeQueue(QueueList* Q,int* e) if (Q=NULL) return; if (Q->front=Q->rear) *e=Q->front->nData; Q->front=Q->rear=NULL; else *e=Q->front->nData; Q->front=Q->front->next; /创建图 void CreatAdjList(Graph* G) int i,j,k; edgenode* p1; edgenode* p2; cout<<"请输入顶点数和边数:"<<endl; cin>>G->vexnum>>G->arcnum; cout<<"开始输入顶点表:"<<endl; for (i=0;i<G->vexnum;i+) cin>>G->adjlistsi.vertex; G->adjlistsi.edgelink=NULL; cout<<"开始输入边表信息:"<<endl; for (k=0;k<G->arcnum;k+) cout<<"请输入各边对应的顶点<Vi,Vj>:" cin>>i>>j; p1=new edgenode; p1->endver=j; p1->edgenext=G->adjlistsi.edgelink; G->adjlistsi.edgelink=p1; p2=new edgenode; p2->endver=i; p2->edgenext=G->adjlistsj.edgelink; G->adjlistsj.edgelink=p2; /因为是无向图，所以有两次建立边表的过程 /-深度优先遍历 void DFS(Graph *G,int i,int visit) cout<<G->adjlistsi.vertex<<" " visiti=1; edgenode *p=new edgenode; p=G->adjlistsi.edgelink; if(G->adjlistsi.edgelink&&!visitp->endver) DFS(G,p->endver,visit); void DFStraversal(Graph *G,char c)/深度优先遍历 cout<<"该图的深度优先遍历结果为:"<<endl; int visitMaxVerNum; for(int i=0;i<G->vexnum;i+) visiti=0;/全部初始化为0，即未访问状态 int m; for (i=0;i<G->vexnum;i+) if (G->adjlistsi.vertex=c)/根据字符查找序号 m=i; DFS(G,i,visit); break; /继续访问未被访问的结点 for(i=0;i<G->vexnum;i+) if(visiti=0) DFS(G,i,visit); cout<<endl; /-广度优先遍历 void BFS(Graph* G,int v,int visit) QueueList *Q=new QueueList; Q->front=Q->rear=NULL; EnQueue(Q,v); while(Q->rear!=NULL) int e=0; DeQueue(Q,&e); cout<<G->adjlistse.vertex<<" " visite=1; edgenode* p=new edgenode; p=G->adjlistse.edgelink; if(p) int m=p->endver; if(m=0) EnQueue(Q,m); while(visitm=0) p=p->edgenext; if(p=NULL) break; m=p->endver; EnQueue(Q,m); void BFStraversal(Graph *G,char c) cout<<"该图的广度优先遍历结果为:"<<endl; int visitedMaxVerNum; for (int i=0;i<G->vexnum;i+) visitedi=0; int m; for (i=0;i<G->vexnum;i+) if (G->adjlistsi.vertex=c) m=i; BFS(G,i,visited); break; /继续访问未被访问的结点 for(i=0;i<G->vexnum;i+) if(visitedi=0) BFS(G,i,visited); cout<<endl; void main system("color 75"); /设置颜色以美观 Graph * G=new Graph; CreatAdjList(G); char ch; cout<<"请输入开始遍历的顶点:" cin>>ch; DFStraversal(G,ch); BFStraversal(G,ch); 程序运行结果如下图：
