google面试题:如何判断图是强连通的

原创
2013/04/09 16:47
阅读数 965

这也是我们

解答:(参考introduction to algrithms)

1,从任意节点s出发用深度优先遍历(或宽度优先遍历)遍历该图,若生成多棵树,则不是连通的。
2,反向图中所有的边。
3,   从节点s出发用深度优先遍历(或宽度优先遍历)遍历该图,若生成多棵树,则不是连通的,否则是强连通图。
理由:1保证了从s可以到达所有的节点。2,3说明从任意节点都可以到达s。任意节点i,j都是连通的因为

i~s,s~j。

这个见地不错:如果图能从节点1出发寻找到所有的点,然后现在将有向边反向,如果还能搜到所有的点的话,就是一个强连通图,因为能够通过1搜索所有点,然后反边就说明能够从任一点到达1点。。


展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部