图的遍历操作实验报告

《图的遍历操作实验报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验三、图的遍历操作一、目的掌握冇向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。二、要求采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。三、DFS和BFS的基本思想深度优先搜索法DFS的基本思想：从阁G中某个顶点Vo出发，首先访问Vo,然后选择一个与Vo和邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问，依次继续。如果当前被访问过的顶点的所冇邻接顶

2、点都已被访问，则冋退到己被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W,从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。广度优先算法BFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo,然后访问与Vo相邻的所有未被访问过的顶点VI,V2,……，Vt;再依次访问与VI,V2,……，Vt相邻的起且未被访问过的的所冇顶点。如此继续，直到访问完图屮的所有顶点。四、示例程序1.邻接矩阵作为存储结构的程序示例#include"stdio.h"#inc1ude，zstd1ib.hz，#dcfineM

3、axVcrtexNum100//定义最大顶点数typedefstruct{charvexs[MaxVertexNum];//顶点表intedges[MaxVertexNum][MaxVertexNum];//邻接矩阵，可看作边表intn，e;//图中的顶点数n和边数e}MGraph;//用邻接矩阵表示的图的类型//=========建立邻接矩阵=======voidCreatMGraph(MGraph*G){inti，j，k;chara;printf(〃JLnputVertexNum(n)andEdgesN

4、um(e):〃)；scanf(〃％d,%d〃，&G->n,&G->e);//输入顶点数和边数scanf(〃%c〃,&a);printf(〃T叩utVertexstring:’’)；for(i=0;in;i++)//读入顶点信息，建立顶点表scanf（〃%c〃,&a）;G-〉vexs[i]=a;for(i=0;in;j++)G-〉edges[i][j]=0;//初始化邻接矩阵printf(’’Tnputedges,CreatAdjacencyMatrix

5、n，z);for(k=0;kc;k++){//读入e条边，建立邻接矩阵scanf(〃％d%d〃，&i，&j);//输入边(Vi,Vj)的顶点序号G->edges[i][j]=l;G->edges[j][i]=l;//若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句}}//=========定义标志向量，为全局变量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度优先遍历的递归算法

6、======voidDFSM(MGraph*G，inti){//以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0,1矩阵//访问顶点Vi//置已访问标志//依次搜索Vi的邻接点visitedtj])//(Vi,Vj)eE,KVj未访问过，故Vjmtj;printf("%c"，G-〉vexs[i]);visited[i]=TRUE;for(j=0;jedges[i][j]==l&&!DFSM(G,j);为新出发点}voidDFS(MGraph*G){inti;//

7、标志向量初始化//Vi未访问过//以Vi为源点开始DFS搜索for(i=0;i〈G-〉n;i++)visited[i]=FALSE;for(i=0;in;i++)visited[i]=FALSE;f

8、or(i=0;ivexs[k]);//定义队列//标志向量初始化//队列初始化//访问源点Vkvisited[k]=TRUE;cq[r]=k;//Vk已访问，将其入队。注意，实际上是将其序号入队while(cq[f]!=~1){//队非空则执行i=cq[f];f=f+l；//Vf出队for(j=0;jn;j++)//依次Vi的邻接点Vji