本文是针对[数据结构基础系列(7)：图]中第1-9课时的实践项目。 0701 图结构导学 0702 图的定义 0703 图的基本术语 0704 图的邻接矩阵存储结构及算法 0705 图的邻接表存储结构及算法 0706 图的遍历 0707 非连通图的遍历 0708 DFS的应用 0709 BFS的应用
定义图的邻接矩阵和邻接表存储结构，实现其基本运算，并完成测试。 要求： 1、头文件graph.h中定义相关的数据结构并声明用于完成基本运算的函数。对应基本运算的函数包括：
void ArrayToMat(int *Arr, int n, MGraph &g); //用普通数组构造图的邻接矩阵 void ArrayToList(int *Arr, int n, ALGraph *&); //用普通数组构造图的邻接表 void MatToList(MGraph g,ALGraph *&G);//将邻接矩阵g转换成邻接表G void ListToMat(ALGraph *G,MGraph &g);//将邻接表G转换成邻接矩阵g void DispMat(MGraph g);//输出邻接矩阵g void DispAdj(ALGraph *G);//输出邻接表G2、在graph.cpp中实现这些函数 3、用main.cpp中的main函数中完成测试。 [参考解答]
假设图G采用邻接表存储，分别设计实现以下要求的算法： （1）输出出图G中每个顶点的出度； （2）求出图G中出度最大的一个顶点，输出该顶点编号； （3）计算图G中出度为0的顶点数； （4）判断图G中是否存在边<i,j>。 利用下图作为测试用图，输出结果。
提示：（1）分别设计函数实现算法；（2）不要全部实现完再测试，而是实现一个，测试一个；（3）请利用图算法库；（４）若将本项目中图G的存储结构改为邻接矩阵，相关操作又如何实现？ 参考解答
实现图遍历算法，分别输出如下图结构的深度优先(DFS)遍历序列和广度优先遍历(BFS)序列。 请利用图算法库。 [参考解答]
假设图G采用邻接表存储，分别设计实现以下要求的算法，要求用区别于示例中的图进行多次测试，通过观察输出值，掌握相关问题的处理方法。 （1）设计一个算法，判断顶点u到v是否有简单路径 （2）设计一个算法输出图G中从顶点u到v的一条简单路径（设计测试图时，保证图G中从顶点u到v至少有一条简单路径）。 （3）输出从顶点u到v的所有简单路径。 （4）输出图G中从顶点u到v的长度为s的所有简单路径。 （5）求图中通过某顶点k的所有简单回路（若存在） [1-5参考解答] （6）求不带权连通图G中从顶点u到顶点v的一条最短路径。 （7）求不带权连通图G中，距离顶点v最远的顶点k [6-7参考解答]
设计一个程序，采用深度优先遍历算法的思路，解决迷宫问题。 （1）建立迷宫对应的图数据结构，并建立其邻接表表示。 （2）采用深度优先遍历的思路设计算法，输出从入口(1,1)点到出口(M,N)的所有迷宫路径。 [参考解答]
[参考解答] 1、设图的邻接矩阵为，则该图为__。 A. 有向图 B. 无向图 C. 强连通图 D. 完全图 2、已知一个图，如图1所示，则从顶点a出发按深度优先遍历则可以得到的一种顶点序列为__。 A. a，b，e，c，d，f B. a，c，f，e，b，d C. a，e，b，c，f，d D. a，e，d，f，c，b （图1） 3、画出图1的邻接矩阵和邻接表存储的示意图。
4、已知图的邻接矩阵如图2所示，则从顶点0出发，按深度优先遍历的顶点序列是_。 （图2） A. 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 3 4 2 5 6
5、已知图的邻接矩阵如图2，根据算法，则从顶点0出发，按广度优先遍历的结点序列是_ A 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5 6
6、已知图的邻接表如图3所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是_ （图3） A. 0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3
7、已知图的邻接表如图3所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是_ A. 0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2
相关资源：图像的基本运算及应用研究