问个算法题：寻找两个点之间的所有路径 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个算法题：寻找两个点之间的所有路径

问个算法题：寻找两个点之间的所有路径# JobHunting - 待字闺中

w*k2011-03-12 08:03

1 楼

给定一个图，一个source，一个destination，要找这两点之间的所有路径。
要求算法的scalability要好，当这个图的节点数较多时，时间复杂度和空间复杂度都
不能太高。

s*y2011-03-12 08:03

2 楼

都尼玛所有路径了, 时间复杂度能不高吗... 完全图的话尼玛不就是指数级别吗.

d*e2011-03-12 08:03

3 楼

DFS吧?

【在 w*****k 的大作中提到】

: 给定一个图，一个source，一个destination，要找这两点之间的所有路径。
: 要求算法的scalability要好，当这个图的节点数较多时，时间复杂度和空间复杂度都
: 不能太高。

w*k2011-03-12 08:03

4 楼

这个我试过，当节点多的时候，recursive stack数目非常大，效率太低

【在 d**e 的大作中提到】

: DFS吧?

d*e2011-03-12 08:03

5 楼

不知写个non-recursive的DFS会不会好点,减少system stack call.
要用一个stack，但因为我想打印出路径，所以觉得用一个deque来保存各个点比较好点。
void FindAllPath(G, source, dest)
deque d;
d.push_back(source);
//这里还要一个数据结构visit表示点是否访问过，跟DFS那里一样。
while(!d.empty())
u = d.back();
for(each v in u's neighbor)
if( v == dest)
print path (that is from d's front to end)
else if v has been visited
continue;
else
d.push_back(v);
end if
u = d.back();
end for
u = d.back();
mark u visited;
d.pop_back();
end while

【在 w*****k 的大作中提到】

: 这个我试过，当节点多的时候，recursive stack数目非常大，效率太低

w*k2011-03-12 08:03

6 楼

呵呵，这个我也试过了，这相当于BFS。这个算法的缺点是如果两个点之间的距离较远
，到最后这个queue会非常大，内存受不了。我用java在4G memeory的机器上跑过，最
后都memory overflow。当然我这个图比较大，有几千个点。对于small scale的这个算
法没问题。

点。

【在 d**e 的大作中提到】

: 不知写个non-recursive的DFS会不会好点,减少system stack call.
: 要用一个stack，但因为我想打印出路径，所以觉得用一个deque来保存各个点比较好点。
: void FindAllPath(G, source, dest)
: deque d;
: d.push_back(source);
: //这里还要一个数据结构visit表示点是否访问过，跟DFS那里一样。
: while(!d.empty())
: u = d.back();
: for(each v in u's neighbor)
: if( v == dest)