《图的遍历源代码.docx》由会员分享，可在线阅读，更多相关《图的遍历源代码.docx（6页珍藏版）》请在三一办公上搜索。
1、图的遍历源代码图的遍历顺序有两种：深度优先搜索和广度优先搜索。深度优先遍历的基本思想是：首先从图中某个顶点v0出发，访问此顶点，然后依次从v0相邻的顶点出发深度优先遍历，直至图中所有与v0路径相通的顶点都被访问了；若此时尚有顶点未被访问，则从中选一个顶点作为起始点，重复该步骤直到所有的顶点都被访问。而广度优先遍历首先从图的某个顶点v0出发，访问了v0之后，依次访问与v0相邻的未被访问的顶点，然后分别从这些顶点出发，广度优先遍历，直至所有的顶点都被访问完。 流程图如下： 程序代码如下： #include #include #include #define MaxVerNum 50 using n
2、amespace 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*
3、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; e
4、lse *e=Q-front-nData; Q-front=Q-front-next; /创建图 void CreatAdjList(Graph* G) int i,j,k; edgenode* p1; edgenode* p2; cout请输入顶点数和边数:G-vexnumG-arcnum; cout开始输入顶点表:endl; for (i=0;ivexnum;i+) cinG-adjlistsi.vertex; G-adjlistsi.edgelink=NULL; cout开始输入边表信息:endl; for (k=0;karcnum;k+) cout请输入各边对应的顶点:; cinij;
5、 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) coutadjlistsi.vertexadjlistsi.edgelink; if(G-adjlistsi.e
6、dgelink&!visitp-endver) DFS(G,p-endver,visit); void DFStraversal(Graph *G,char c)/深度优先遍历 cout该图的深度优先遍历结果为:endl; int visitMaxVerNum; for(int i=0;ivexnum;i+) visiti=0;/全部初始化为0，即未访问状态 int m; for (i=0;ivexnum;i+) if (G-adjlistsi.vertex=c)/根据字符查找序号 m=i; DFS(G,i,visit); break; /继续访问未被访问的结点 for(i=0;ivexnum
7、;i+) if(visiti=0) DFS(G,i,visit); coutfront=Q-rear=NULL; EnQueue(Q,v); while(Q-rear!=NULL) int e=0; DeQueue(Q,&e); coutadjlistse.vertexadjlistse.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,
8、char c) cout该图的广度优先遍历结果为:endl; int visitedMaxVerNum; for (int i=0;ivexnum;i+) visitedi=0; int m; for (i=0;ivexnum;i+) if (G-adjlistsi.vertex=c) m=i; BFS(G,i,visited); break; /继续访问未被访问的结点 for(i=0;ivexnum;i+) if(visitedi=0) BFS(G,i,visited); coutendl; void main system(color 75); /设置颜色以美观 Graph * G=new Graph; CreatAdjList(G); char ch; coutch; DFStraversal(G,ch); BFStraversal(G,ch); 程序运行结果如下图：
