基于连通图,邻接矩阵实现的图,非递归实现。
算法思想:
设置两个标志位,①该顶点是否入栈,②与该顶点相邻的顶点是否已经访问。
,一个将始点标志位①置1,将其入栈
,V B查看栈顶节点在图中,有没有可以到达,且没有入栈,且没有从这个节点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++代码实现
图类,基于邻接矩阵,不详细的写了==
首先自己写一个简单的“栈类”,由于新增了些方法所以不完全叫栈
