w*****k
发帖数: 42 | 1 给定一个图，一个source，一个destination，要找这两点之间的所有路径。
要求算法的scalability要好，当这个图的节点数较多时，时间复杂度和空间复杂度都
不能太高。 |
s********y
发帖数: 58 | 2 都尼玛所有路径了, 时间复杂度能不高吗... 完全图的话尼玛不就是指数级别吗. |
d**e
发帖数: 6098 | 3 DFS吧?
【在 w*****k 的大作中提到】
: 给定一个图，一个source，一个destination，要找这两点之间的所有路径。
: 要求算法的scalability要好，当这个图的节点数较多时，时间复杂度和空间复杂度都
: 不能太高。
|
w*****k
发帖数: 42 | 4 这个我试过，当节点多的时候，recursive stack数目非常大，效率太低
【在 d**e 的大作中提到】
: DFS吧?
|
d**e
发帖数: 6098 | 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*****k
发帖数: 42 | 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)
|
