图的遍历操作实验报告.pdfVIP

图的遍历操作实验报告--第1页 实验三、图的遍历操作 一、 目的 掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结 构；掌握DFS 及 BFS 对图的遍历操作；了解图结构在人工智能、工程等领域的 广泛应用。 二、 要求 采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的 DFS 和 BFS 操作。 三、 DFS 和 BFS 的基本思想 深度优先有哪些信誉好的足球投注网站法 DFS 的基本思想：从图 G 中某个顶点 Vo 出发，首先访问 Vo，然后选择一个与 Vo 相邻且没被访问过的顶点 Vi 访问，再从 Vi 出发选择 一个与 Vi 相邻且没被访问过的顶点 Vj 访问，……依次继续。如果当前被访问 过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一 个拥有未被访问的相邻顶点的顶点 W，从W 出发按同样方法向前遍历。直到图 中所有的顶点都被访问。 广度优先算法 BFS 的基本思想：从图 G 中某个顶点 Vo 出发，首先访问 Vo，然后访问与Vo 相邻的所有未被访问过的顶点 V1，V2，……，Vt；再依次访 问与V1，V2，……，Vt 相邻的起且未被访问过的的所有顶点。如此继续，直到 访问完图中的所有顶点。 四、 示例程序 1． 邻接矩阵作为存储结构的程序示例 #includestdio.h #includestdlib.h #define MaxVertexNum 100 //定义最大顶点数 typedef struct{ char vexs[MaxVertexNum]; //顶点表 int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表 int n,e; //图中的顶点数n 和边数 e }MGraph; //用邻接矩阵表示的图的类型 //=========建立邻接矩阵======= void CreatMGraph(MGraph *G) { int i,j,k; char a; printf(Input VertexNum(n) and EdgesNum(e): ); scanf(%d,%d,G-n,G-e); //输入顶点数和边数 scanf(%c,a); printf(Input Vertex string:); for(i=0;iG-n;i++) { scanf(%c,a); G-vexs[i]=a; //读入顶点信息，建立顶点表 } 图的遍历操作实验报告--第1页 图的遍历操作实验报告--第2页 for(i=0;iG-n;i++) for(j=0;jG-n;j++) G-edges[i][j]=0; //初始化邻接矩阵 printf(Input edges,Creat Adjacency Matrix\n); for(k=0;kG-e;k++) { //读入 e 条边，建立邻接矩阵 scanf(%d%d,i,j); //输入边（Vi，Vj）的顶点序号 G-edges[i][j]=1; G-edges