C++计算图任意两点间的所有路径
57 浏览量
2020-08-29
00:25:12
上传
评论 2
收藏 87KB PDF 举报
C++计算图任意两点间的所有路径计算图任意两点间的所有路径
主要为大家详细介绍了C++求图任意两点间的所有路径，具有一定的参考价值，感兴趣的小伙伴们可以参考一下
基于连通图，邻接矩阵实现的图，非递归实现。
算法思想：
设置两个标志位，①该顶点是否入栈，②与该顶点相邻的顶点是否已经访问。
A 将始点标志位①置1，将其入栈
B 查看栈顶节点V在图中，有没有可以到达、且没有入栈、且没有从这个节点V出发访问过的节点
C 如果有，则将找到的这个节点入栈，这个顶点的标志位①置1，V的对应的此顶点的标志位②置1
D 如果没有，V出栈，并且将与v相邻的全部结点设为未访问，即全部的标志位②置0
E 当栈顶元素为终点时，设置终点没有被访问过，即①置0，打印栈中元素，弹出栈顶节点
F 重复执行B – E,直到栈中元素为空
先举一个例子吧
假设简单连通图如图1所示。假设我们要找出结点3到结点6的所有路径，那么，我们就设结点3为起点，结点6为终点。找到结
点3到结点6的所有路径步骤如下：
1、 我们建立一个存储结点的栈结构，将起点3入栈，将结点3标记为入栈状态；
2、 从结点3出发，找到结点3的第一个非入栈没有访问过的邻结点1，将结点1标记为入栈状态，并且将3到1标记为已访问；
3、 从结点1出发，找到结点1的第一个非入栈没有访问过的邻结点0，将结点0标记为入栈状态，并且将1到0标记为已访问；
4、 从结点0出发，找到结点0的第一个非入栈没有访问过的邻结点2，将结点2标记为入栈状态，并且将0到2标记为已访问；
5、 从结点2出发，找到结点2的第一个非入栈没有访问过的邻结点5，将结点5标记为入栈状态，并且将2到5标记为已访问；
6、 从结点5出发，找到结点5的第一个非入栈没有访问过的邻结点6，将结点6标记为入栈状态，并且将5到6标记为已访问；
7、 栈顶结点6是终点，那么，我们就找到了一条起点到终点的路径，输出这条路径；
8、 从栈顶弹出结点6，将6标记为非入栈状态；
9、 现在栈顶结点为5，结点5没有非入栈并且非访问的结点，所以从栈顶将结点5弹出，并且将5到6标记为未访问；
10、 现在栈顶结点为2，结点2的相邻节点5已访问，6满足非入栈，非访问，那么我们将结点6入栈；
11、 现在栈顶为结点6，即找到了第二条路径，输出整个栈，即为第二条路径
12、 重复步骤8-11，就可以找到从起点3到终点6的所有路径；
13、 栈为空，算法结束。
下面讲一下C++代码实现
图类，基于邻接矩阵，不详细的写了 ==
class Graph
{
private:
CArray<DataType,DataType> Vertices;
int Edge[MaxVertices][MaxVertices];
int numOfEdges;
评论0
最新资源