数据结构与算法问题分析及源代码之图的遍历

《数据结构与算法问题分析及源代码之图的遍历》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、图的遍历1题目题目:编写一个程序，实现图的遍历运算，并在此基础上设计一个主程序完成如下功能：输出如图的有向图G从顶点0开始的深度优先遍历序列（递归算法）。输出如图的有项图G从顶点0开始的深度优先遍历序列（非递归算法）。输出如图的有向图G从顶点0开始的广度优先遍历序列01234554319765582目标熟悉图的定义及其基本操作的实现。3设计思想图的输入采用邻接矩阵的形式，在程序内部以邻接表形式进行操作。将上图进行深度优先遍历和广度优先遍历。4算法描述（1）邻接矩阵转换为邻接表：邻接表的结点元素是由结点组成的矩阵两个计数量。把邻接矩阵的结点数据值赋值给邻接表元素结点的数据变量，并初始化其元素

2、结点指针为空；测试邻接矩阵的非零位，若为1则在邻接表中使前一个结点指向后一个结点。（2）广度优先遍历：数组visited[]标记结点是否被访问，初始化为全零；从结点Vi开始访问，访问此顶点后，依次访问Vi的各个未曾访问过的邻接点，然后分别从这些邻接点出发，直至图中所有已有已被访问的顶点的邻接点都被访问到。（3）深度优先遍历：深度优先遍历可有两种方式，递归和非递归。其中递归的深度优先遍历的思想是首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已

3、被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。5程序结构图开始main()初始化图转换邻接矩阵为邻接表广度优先遍历深度优先遍历（递归）深度优先遍历（非递归）结束6源程序#include#include#include#defineMAXVEX100typedefcharVertexType[3];typedefstructedgenode{intadjvex;intvalue;structedgenode*next;}ArcNode;typedefstruc

4、tvexnode{VertexTypedata;ArcNode*firstarc;}VHeadNode;typedefstructvertex{intadjvex;VertexTypedata;}VType;typedefstructgraph{intn,e;VTypevexs[MAXVEX];intedges[MAXVEX][MAXVEX];}AdjMatix;typedefstruct{intn,e;VHeadNodeadjlist[MAXVEX];}AdjList;//将邻接矩阵g转化成邻接表G:voidMatToList(AdjMatixg,AdjList*&G){inti,j;A

5、rcNode*p;G=(AdjList*)malloc(sizeof(AdjList));for(i=0;iadjlist[i].firstarc=NULL;strcpy(G->adjlist[i].data,g.vexs[i].data);}for(i=0;i=0;j--)if(g.edges[i][j]!=0){p=(ArcNode*)malloc(sizeof(ArcNode));p->value=g.edges[i][j];p->adjvex=j;p->next=G->adjlist[i].firstarc;G

6、->adjlist[i].firstarc=p;}G->n=g.n;G->e=g.e;}//广度优先：voidBFS(AdjList*G,intvi){inti,v,visited[MAXVEX];intQu[MAXVEX],front=0,rear=0;ArcNode*p;for(i=0;in;i++)visited[i]=0;printf("%d",vi);visited[vi]=1;rear=(rear+1)%MAXVEX;Qu[rear]=vi;while(front!=rear){front=(front+1)%MAXVEX;v=Qu[front];p=G->adjlis

7、t[v].firstarc;while(p!=NULL){if(visited[p->adjvex]==0){visited[p->adjvex]=1;printf("%d",p->adjvex);rear=(rear+1)%MAXVEX;Qu[rear]=p->adjvex;}p=p->next;}}}//深度优先递归：intvisited[MAXVEX];voidDFS(AdjList*g,intvi){ArcNod