这也是我们
解答:(参考introduction to algrithms)
1,从任意节点s出发用深度优先遍历(或宽度优先遍历)遍历该图,若生成多棵树,则不是连通的。2,反向图中所有的边。
3, 从节点s出发用深度优先遍历(或宽度优先遍历)遍历该图,若生成多棵树,则不是连通的,否则是强连通图。
理由:1保证了从s可以到达所有的节点。2,3说明从任意节点都可以到达s。任意节点i,j都是连通的因为
i~s,s~j。
这个见地不错:如果图能从节点1出发寻找到所有的点,然后现在将有向边反向,如果还能搜到所有的点的话,就是一个强连通图,因为能够通过1搜索所有点,然后反边就说明能够从任一点到达1点。。