数据结构实践项目——图的基本运算及遍历操作

本文是针对[数据结构基础系列(7)：图]中第1-9课时的实践项目。
0701 图结构导学
0702 图的定义
0703 图的基本术语
0704 图的邻接矩阵存储结构及算法
0705 图的邻接表存储结构及算法
0706 图的遍历
0707 非连通图的遍历
0708 DFS的应用
0709 BFS的应用

【项目1 - 图基本算法库】
定义图的邻接矩阵和邻接表存储结构，实现其基本运算，并完成测试。
要求：
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);//输出邻接表G

2、在graph.cpp中实现这些函数
3、用main.cpp中的main函数中完成测试。
[参考解答]

【项目2 - 操作用邻接表存储的图】
　　假设图G采用邻接表存储，分别设计实现以下要求的算法：
　　（1）输出出图G中每个顶点的出度；
　　（2）求出图G中出度最大的一个顶点，输出该顶点编号；
　　（3）计算图G中出度为0的顶点数；
　　（4）判断图G中是否存在边$<i,j>$。
　　利用下图作为测试用图，输出结果。

　　
　　提示：（1）分别设计函数实现算法；（2）不要全部实现完再测试，而是实现一个，测试一个；（3）请利用图算法库；（４）若将本项目中图G的存储结构改为邻接矩阵，相关操作又如何实现？
参考解答

【项目3 - 图遍历算法实现】
　　实现图遍历算法，分别输出如下图结构的深度优先(DFS)遍历序列和广度优先遍历(BFS)序列。

　　请利用图算法库。
　　[参考解答]

【项目4 - 利用遍历思想求解图问题】
　　假设图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参考解答]

【项目5 - 迷宫问题之图深度优先遍历解法】
　　设计一个程序，采用深度优先遍历算法的思路，解决迷宫问题。
　　（1）建立迷宫对应的图数据结构，并建立其邻接表表示。
　　（2）采用深度优先遍历的思路设计算法，输出从入口(1,1)点到出口(M,N)的所有迷宫路径。
　　[参考解答]