请问数据结构中图的强连通分量是什么？能具体解释一下吗？

有向图的极大强连通子图，称为强连通分量(strongly connected components)。

在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。

扩展资料： 

强连通分量Tarjan算法

任何一个强连通分量，必定是对原图的深度优先搜索树的子树。那么只要确定每个强连通分量的子树的根，然后根据这些根从树的最低层开始，一个一个的拿出强连通分量即可。

维护两个数组，一个是indx[1..n]，一个是mlik[1..n]，其中indx[i]表示顶点i开始访问时间，mlik[i]为与顶点i邻接的顶点未删除顶点j的mlik[j]和mlik[i]的最小值(mlik[i]初始化为indx[i])。这样，在一次深搜的回溯过程中，如果发现mlik[i]==indx[i]那么，当前顶点就是一个强连通分量的根。

因为如果它不是强连通分量的根，那么它一定是属于另一个强连通分量，而且它的根是当前顶点的祖宗，那么存在包含当前顶点的到其祖宗的回路，可知mlik[i]一定被更改为一个比indx[i]更小的值。

至于拿出强连通分量，如果当前节点为一个强连通分量的根，那么它的强连通分量一定是以该根为根节点的(剩下节点)子树。在深度优先遍历的时候维护一个堆栈，每次访问一个新节点，就压入堆栈。

这样，由于当前节点是这个强连通分量中最先被压入堆栈的，那么在当前节点以后压入堆栈的并且仍在堆栈中的节点都属于这个强连通分量。

可以用反证法证明这个做法的正确性。假设一个节点在当前节点压入堆栈以后压入并且还存在，同时它不属于该强连通分量，那么它一定属于另一个强连通分量，但当前节点是它的根的祖宗，那么这个强连通分量应该在此之前已经被拿出。

参考资料来源：百度百科-强连通分量    

强连通分量是有向图中的概念，就是每一个顶点到其它点都由路径，注意有方向。

step1：对原图G进行深度优先遍历，记录每个节点的离开时间。

step2：选择具有最晚离开时间的顶点，对反图GT进行遍历，删除能够遍历到的顶点，这些顶点构成一个强连通分量。

step3：如果还有顶点没有删除，继续step2，否则算法结束。

如果把求出来的每个强连通分量收缩成一个点，并且用求出每个强连通分量的顺序来标记收缩后的节点，那么这个顺序其实就是强连通分量收缩成点后形成的有向无环图的拓扑序列。

扩展资料：

Kosaraju算法的第二次深搜隐藏了一个拓扑性质，而Tarjan算法和Gabow算法省略了第二次深搜，所以，它们不具有拓扑性质。

Tarjan算法用堆栈和标记，Gabow用两个堆栈（其中一个堆栈的实质是代替了Tarjan算法的标记部分）来代替Kosaraju算法的第二次深搜，所以只用一次深搜，效率比Kosaraju算法要高。

在这个节点访问之前，能够构成强连通分量的那些节点已经被弹出了，这个对Tarjan算法有了解的都应该清楚，那么Tarjan算法中的判断根我们用什么来代替呢？想想，其实就是看看第二个堆栈的顶元素是不是当前顶点就可以了。

参考资料来源：百度百科——强连通分量

强连通分量是有向图中的概念，就是每一个顶点到其它点都由路径，注意有方向

有向图的极大强连通子图，称为强连通分量（strongly connected components）。