图的遍历源代码(c语言)

《图的遍历源代码(c语言)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图的遍历顺序有两种：深度优先搜索（DFS）和广度优先搜索（BFS）。深度优先遍历的基本思想是：首先从图中某个顶点v0出发，访问此顶点，然后依次从v0相邻的顶点出发深度优先遍历，直至图中所有与v0路径相通的顶点都被访问了；若此时尚有顶点未被访问，则从中选一个顶点作为起始点，重复该步骤直到所有的顶点都被访问。而广度优先遍历首先从图的某个顶点v0出发，访问了v0之后，依次访问与v0相邻的未被访问的顶点，然后分别从这些顶点出发，广度优先遍历，直至所有的顶点都被访问完。流程图如下：程序代码如下：#include#inclu

2、de#include#defineMaxVerNum50usingnamespacestd;structedgenode{intendver;intinform;edgenode*edgenext;};structvexnode{charvertex;edgenode*edgelink;};structGraph{vexnodeadjlists[MaxVerNum];intvexnum;intarcnum;};//队列的定义及相关函数的实现structQueueNode{intnData;Q

3、ueueNode*next;};structQueueList{QueueNode*front;QueueNode*rear;};voidEnQueue(QueueList*Q,inte){QueueNode*q=newQueueNode;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;}}voidDeQueue(QueueList*Q,in

4、t*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;}}//创建图voidCreatAdjList(Graph*G){inti,j,k;edgenode*p1;edgenode*p2;cout<<"请输入顶点数和边数:"<>G->vexnum>>G->arcnum;cout<<"开始输入顶点表:"<

5、vexnum;i++){cin>>G->adjlists[i].vertex;G->adjlists[i].edgelink=NULL;}cout<<"开始输入边表信息:"<arcnum;k++){cout<<"请输入各边对应的顶点:";cin>>i>>j;p1=newedgenode;p1->endver=j;p1->edgenext=G->adjlists[i].edgelink;G->adjlists[i].edgelink=p1;p2=

6、newedgenode;p2->endver=i;p2->edgenext=G->adjlists[j].edgelink;G->adjlists[j].edgelink=p2;//因为是无向图，所以有两次建立边表的过程}}//-------------------------------------------------------------深度优先遍历voidDFS(Graph*G,inti,intvisit[]){cout<adjlists[i].vertex<<"";visit[i]=1;edgenode*p=n

7、ewedgenode;p=G->adjlists[i].edgelink;if(G->adjlists[i].edgelink&&!visit[p->endver]){DFS(G,p->endver,visit);}}voidDFStraversal(Graph*G,charc)//深度优先遍历{cout<<"该图的深度优先遍历结果为:"<vexnum;i++){visit[i]=0;//全部初始化为0，即未访问状态}intm;for(i=0;i

8、->vexnum;i++){if(G->adjlists[i].vertex==c)//根据字符查找序号{m=i;DFS(G,i,visit);break;}}//继续访问未被访问的结点for(i=0;ivexnum;i++)