强连通图

强连通图(带底构Strongly Connected Graph)是指在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都来自存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。

• 中文名 强连通图
• 外文名 Strongly Connected Graph
• 领域 数学
• 对象 有向图
• 释义 有向图中任意两点间都存在路径

定理及其证明

　　定理:一个有向图是强连通来自的，当且仅当G中有一360百科个回路，它至少包含每个节点一次。

　　证明:

　　(1)充分性:如果G中有一个回路，它至局两含东受历好钢城殖洋少包含每个节点一次，则G中任两个节点都是互相可达的，故G是强连通图。

　　(2)必要性:如果有向图是强连通的，则任两个节点都是相互可达。故必可做一回路经过图中所队际并有有各点。若不然则必有一回路不包含某一结点v，并且v与回路上的个节点就不是班协客政掉千难头相互可达，与强连通条件矛盾 。

强连通图的边问题

　　有n个顶点的强连通图最多有n(n-1)条边，最少有n条边。

图1

　　(1)最多的情况:即n个顶点中两两相连，若不计方向，n个点两两相连有n(n-1)/2条边，而由于强连通图是有向图，故每条边有两个方向，n(间吗n-1)/2×2=n(n-1)，故有n个顶点的强连通图最多有n燃轻营存乐须治(n-1)条边。

　　(边压旧格挥得须艺2)最少的情况:即n个顶点围成一个圈，且圈上各边方向一致，即均为顺时针或者逆时针范确住，此时有n条边。

　　下面举例说明:如图1所示，设ABCD四个点构成强连通图，则:

　　(1)边数最多有4×3=12条，如图1所示。

试告万扬　　(2)边数最少有4何始向上条，如图2所示。

图2

强连通图的判断

　　问题:给一个有向图，判断给图是否是强连通的。

　　如图3所示，则是一个强连通图。

　　对于无向图则比较简单，只需要从某一个顶点出发，使用BFS或DFS搜索，如果可以遍历到所有的顶点，则给定的图是连通的。

　　但这种方法对有向图并不适用，例如 : 1 -> 2 -> 3 -> 4，并不是强连通图。

方法一

　　可以调用D来自FS搜索 V 次，V是顶点的个数，就是对每个顶点都做一次DFS搜索，判断360百科是否可达。这样的复杂度为O(V*(V+E))。

方法二

　　可以参考环营几银求解连通分量的算法Tar少磁新吧jan算法，我们可以在O(V掌+E) 的时间内找到所有的连通分量，如果连通分量的个数为1，则说明该图是强连通的。