图的遍历操作实验报告材料.docx

《图的遍历操作实验报告材料.docx》由会员分享，可在线阅读，更多相关《图的遍历操作实验报告材料.docx（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图的遍历操作实验报告材料 好用文档 试验三、图的遍历操作 一、目的 驾驭有向图和无向图的概念；驾驭邻接矩阵和邻接链表建立图的存储结构；驾驭DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。 二、要求 采纳邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS 和BFS操作。 三、DFS和BFS 的基本思想 深度优先搜寻法DFS的基本思想：从图G中某个顶点Vo动身，首先访问Vo，然后选择一个与Vo相邻且没被访问过的顶点Vi访问，再从Vi动身选择一个与Vi相邻且没被访问过的顶点Vj访问，依次接着。假如当前被访问过的顶点的全部邻接顶点都已被访问，则回退到已被访问的顶点

2、序列中最终一个拥有未被访问的相邻顶点的顶点W，从W动身按同样方法向前遍历。直到图中全部的顶点都被访问。 广度优先算法BFS的基本思想：从图G中某个顶点Vo动身，首先访问Vo，然后访问与Vo相邻的全部未被访问过的顶点V1，V2，Vt；再依次访问与V1，V2，Vt相邻的起且未被访问过的的全部顶点。如此接着，直到访问完图中的全部顶点。 四、示例程序 1邻接矩阵作为存储结构的程序示例 #includestdio.h #includestdlib.h #define MaxVertexNum 100 /定义最大顶点数 typedef struct char vexsMaxVertexNum; /顶点表

3、int edgesMaxVertexNumMaxVertexNum; /邻接矩阵，可看作边表 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;in;i+) scanf(%c,&a); G-vexsi=a; /读入顶点信息，建立顶点表