在使用图的邻接表ADT的基础上,设计一个算法,按照深度优先搜索的思想找出从指定结点出发且长度为m的所有简单路径。并将此算法加入到邻接表ADT中,在邻接表ADT中提供一个公有的成员函数FindPath(start, m)。
提示:
(1)这个问题相当于从指定结点开始深度优先遍历,而且遍历的深度正好为m。为此,在遍历时需要记住遍历的深度,当深度达到m时,就不需要递归了。此时需要输出这条路径,因此在遍历的过程中还需要记住整条路径。
(2)由于深度优先遍历是用递归实现的,所以FindPath函数最好也设计两个。一个是共有的FindPath函数,供用户使用(外壳);另一个是私有的FindPath函数,实现递归的遍历。公有的FingPath函数调用私有的FindPath函数找出这些路径。
(3)在调用递归的FindPath函数前,外壳函数还需要做一些辅助工作:
1)要找的是长度为m的简单路径,因此路径上不能有相同的结点,于是定义了一个数组visited记录结点是否在路径上。
2)当路径长度等于m时要输出这条路径,于是定义了一个数组stack保存这条路径。每访问一个结点,都要把结点记录在stack中。
3)递归的FindPath函数有6个参数。第1个参数是遍历的起点的序号;第2个参数是要求的路径长度;第3个参数是符合要求的路径数目;第4个参数是当前路径中的结点数,当前路径的长度是结点数减1;第5个参数是visited数组,记录结点是否在路径上;第6个参数是一个用于记录路径上结点序号的数组,作用和栈类似。
4)调用FindPath函数时要指出从哪一个结点出发,而递归的FingPath函数的参数是起点的序号。递归的FindPath函数首先将起点放入这条路径,并标记这个结点已被访问,然后判断路径长度是否是m。如果长度已达到m,则输出这条路径,并将最后一个结点从路径上删除,返回上一层调用,检查是否还有其它的途径;否则逐个检查起点的后继结点。如果该后继结点没有被访问过,则对该结点调用递归的FindPath函数继续寻找。在所有的后继都检查后,表示这条路径处理完毕。将起始结点从这条路径上删除,返回上一层调用。
参考函数原型:
(1)//找出从指定结点出发且长度为m的所有简单路径(外壳部分)
template<class TypeOfVer, class TypeOfEdge>
void adjlist_graph<TypeOfVer, TypeOfEdge>::FindPath(int start, int m);
(2)//找出从指定结点出发且长度为m的所有简单路径(递归部分)
template<class TypeOfVer, class TypeOfEdge>
void adjlist_graph<TypeOfVer, TypeOfEdge>::FindPath(int start, int m, int &count, int top, int visited[], int stack[]);
输入说明 :
第一行:图的类型
第二行:结点数
第三行:结点集
第四行:边数
第五行:边集
第六行:起点start
第七行:路径长度m
输出说明 :
第一行:顶点集
第二行:邻接表
空行
如无符合要求的路径:输出 0
否则: 路径输出(一条路径占一行)
路径数目
输入:DG
8
1 2 3 4 5 6 7 8
8
0 1
0 2
1 3
1 4
2 5
2 6
3 7
4 7
0
2
输出:
1 2 3 4 5 6 7 8
1->2->1
2->4->3
3->6->5
4->7
5->7
6
7
8
1->3->7
1->3->6
1->2->5
1->2->4
4