问个算法题：寻找两个点之间的所有路径# JobHunting - 待字闺中
w*k
1 楼
给定一个图，一个source，一个destination，要找这两点之间的所有路径。
要求算法的scalability要好，当这个图的节点数较多时，时间复杂度和空间复杂度都
不能太高。
要求算法的scalability要好，当这个图的节点数较多时，时间复杂度和空间复杂度都
不能太高。
s*y
2 楼
都尼玛所有路径了, 时间复杂度能不高吗... 完全图的话尼玛不就是指数级别吗.
d*e
3 楼
DFS吧?
【在 w*****k 的大作中提到】
: 给定一个图，一个source，一个destination，要找这两点之间的所有路径。
: 要求算法的scalability要好，当这个图的节点数较多时，时间复杂度和空间复杂度都
: 不能太高。
【在 w*****k 的大作中提到】
: 给定一个图，一个source，一个destination，要找这两点之间的所有路径。
: 要求算法的scalability要好，当这个图的节点数较多时，时间复杂度和空间复杂度都
: 不能太高。
w*k
4 楼
这个我试过，当节点多的时候，recursive stack数目非常大，效率太低
【在 d**e 的大作中提到】
: DFS吧?
【在 d**e 的大作中提到】
: DFS吧?
d*e
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数目非常大，效率太低
要用一个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
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)
，到最后这个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)
相关阅读
有第一轮HR电面就刷下来的吗？西雅图的Pre-IPO大家说说看还有啥在IBM工作的说说怎样才能进IBM快绝望了一个design题大妈想工作请问各位啥时候辞职比较好水果家的Test Stability QA位置，会面些什么有没有在等着G家team match的啊看了下freelancer.comthanks for some tips on pure storage onsite interivew金融专业无身份找工作H4转H1期间可以回国嘛G家如何通知面试结果的这个怎么回？请问半导体专业博士，夏天毕业好找工作还是冬天毕业好找？问一下关于Leetcode复习的方法amazon 的 "senior software development manager" 是什么level?FEA方向fresh PhD求refer (转载)H1B Transfer 被RFE