数据结构,无向图问题,想了两天,求助
怎么寻找无向图中一个节点到另一个节点的所有路径
这边不好贴图,我只好用符号把图表示出来
例如:
1--2
|/ |
3--4
| |
5--6 (其中2和3有一条连线)
要求程序能够输出从1到6的所有路径
如:
1 2 3 4 6
1 2 3 5 6
1 2 4 3 5 6
1 2 4 6
1 3 2 4 6
1 3 4 6
1 3 5 6
目前我做了一个无向图的类和一个栈
不知道怎么控制这个栈
什么时候进栈,什么条件出栈
怎么循环
或者怎么递归?
希望大家能帮我想一想,万分感谢……
[解决办法]
提供一种方法：
假设我们要找的是从u到v的所有路径，建立一个数组，比如说reach[N](其中N是图中节点数目），用reach[i]表示从u到i有多少条路径。很显然，reach[v]就是u到v的路径数目。下面的伪码表示了如何求reach[i]
//init
for (int i = 0; i < N; i++)
reach[i] = -1;
reach[u] = 1;
/*
call path (u, reach)
*/
void path (int v, int reach[])
{
reach[v] = 0;
for each vertex x adjacent to v
{
if (reach[x] == -1)//x has not been visited yet
path (x, reach);
reach[v] += reach[x];
}
}
如上的递归算法求得了reach的值，只需要对这个算法作一点修改就可以打印出路径，这个问题就留给lz了：）
