转:DFS搜索图中两点之间所有路径
https://blog.****.net/hackersuye/article/details/79044555
用DFS算法来求图中两点的所有的路径,在给出代码前,先给大家讲解清楚该算法的原理。
DFS本来被用作图的遍历,现在我们对它进行改造,成为求两点间的所有路径的工具。
先定义如下图:
如何从图中的v1找到到v4的所有路径呢?来看下面步骤:
1.从v1出发,将v1标记,并将其入栈。
2.找到v0,将其标记,将其入栈。
3.找到v4,将其标记,入栈。v4是终点,将栈中的元素从栈底往栈顶输出,即为一条路径。v4出栈,并取消标记,回溯到v0。
4.v0除v4外无其它出度,将v0出栈,并取消标记,回溯到v1。
5.找到v2,将其标记并入栈。
6.找到v0,将其标记并入栈。
7.找到v4,将其标记,入栈。v4是终点,将栈中的元素从栈底往栈顶输出,即为一条路径。v4出栈,并取消标记,回溯到v0。
8.v0除v4外无其它出度,将v0出栈,并取消标记,回溯到v2。
9.找到v3,将其标记并入栈。
10.找到v4,将其标记,入栈。v4是终点,将栈中的元素从栈底往栈顶输出,即为一条路径。v4出栈,并取消标记,回溯到v3。
11.v3除v4外无其它出度,将v3出栈,并取消标记,回溯到v2。
12.v2除v0,v3外无其它出度,将v2出栈,并取消标记,回溯到v1。
13.v1除v0,v2外无其它出度,将v1出栈,栈空,结束遍历。
好,上述便是对v1到v4所有路径的遍历,相信大家也懂得了,下面便给出c++代码顺序结构图的实现,链式原理也一样:
void DFS(int start,int end)//深搜入栈查询所有路径 { visited[start] = true;//visited数组存储各定点的遍历情况,true为已遍历(标记) stack.Push(某个顶点);//入栈 for (int j = 0; j < list.Size(); j++) { if (start== end) {//找到终点 for (int i=0; i < stack.Size()-1; i++) { //输出从栈底到栈顶的元素,即为一条路径 } stack.Pop();//出栈 visited[start] = false; break; } if (!visited[j]) {//该顶点未被访问过 DFS(j,end); } if (j == list.Size() - 1 ) {//如果该顶点无其它出度 stack.Pop(); visited[start] = false; } } }
用DFS算法来求图中两点的所有的路径,在给出代码前,先给大家讲解清楚该算法的原理。
DFS本来被用作图的遍历,现在我们对它进行改造,成为求两点间的所有路径的工具。
先定义如下图:
如何从图中的v1找到到v4的所有路径呢?来看下面步骤:
1.从v1出发,将v1标记,并将其入栈。
2.找到v0,将其标记,将其入栈。
3.找到v4,将其标记,入栈。v4是终点,将栈中的元素从栈底往栈顶输出,即为一条路径。v4出栈,并取消标记,回溯到v0。
4.v0除v4外无其它出度,将v0出栈,并取消标记,回溯到v1。
5.找到v2,将其标记并入栈。
6.找到v0,将其标记并入栈。
7.找到v4,将其标记,入栈。v4是终点,将栈中的元素从栈底往栈顶输出,即为一条路径。v4出栈,并取消标记,回溯到v0。
8.v0除v4外无其它出度,将v0出栈,并取消标记,回溯到v2。
9.找到v3,将其标记并入栈。
10.找到v4,将其标记,入栈。v4是终点,将栈中的元素从栈底往栈顶输出,即为一条路径。v4出栈,并取消标记,回溯到v3。
11.v3除v4外无其它出度,将v3出栈,并取消标记,回溯到v2。
12.v2除v0,v3外无其它出度,将v2出栈,并取消标记,回溯到v1。
13.v1除v0,v2外无其它出度,将v1出栈,栈空,结束遍历。
好,上述便是对v1到v4所有路径的遍历,相信大家也懂得了,下面便给出c++代码顺序结构图的实现,链式原理也一样:
void DFS(int start,int end)//深搜入栈查询所有路径 { visited[start] = true;//visited数组存储各定点的遍历情况,true为已遍历(标记) stack.Push(某个顶点);//入栈 for (int j = 0; j < list.Size(); j++) { if (start== end) {//找到终点 for (int i=0; i < stack.Size()-1; i++) { //输出从栈底到栈顶的元素,即为一条路径 } stack.Pop();//出栈 visited[start] = false; break; } if (!visited[j]) {//该顶点未被访问过 DFS(j,end); } if (j == list.Size() - 1 ) {//如果该顶点无其它出度 stack.Pop(); visited[start] = false; } } }