强连通分量怎么写 _连通

1.请问数据结构中图的强连通分量是什么有向图的极大强连通子图，称为强连通分量（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]更小的值。
至于拿出强连通分量，如果当前节点为一个强连通分量的根，那么它的强连通分量一定是以该根为根节点的（剩下节点）子树。在深度优先遍历的时候维护一个堆栈，每次访问一个新节点，就压入堆栈。
这样，由于当前节点是这个强连通分量中最先被压入堆栈的，那么在当前节点以后压入堆栈的并且仍在堆栈中的节点都属于这个强连通分量。
可以用反证法证明这个做法的正确性。假设一个节点在当前节点压入堆栈以后压入并且还存在，同时它不属于该强连通分量，那么它一定属于另一个强连通分量，但当前节点是它的根的祖宗，那么这个强连通分量应该在此之前已经被拿出。
参考资料来源：百度百科-强连通分量
2.强连通分量的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]更小的值。
至于如何拿出强连通分量，这个其实很简单，如果当前节点为一个强连通分量的根，那么它的强连通分量一定是以该根为根节点的（剩下节点）子树。在深度优先遍历的时候维护一个堆栈，每次访问一个新节点，就压入堆栈。现在知道如何拿出了强连通分量了吧？是的，因为当前节点是这个强连通分量中最先被压入堆栈的，那么在当前节点以后压入堆栈的并且仍在堆栈中的节点都属于这个强连通分量。当然有人会问真的吗？假设一个节点在当前节点压入堆栈以后压入并且还存在，同时它不属于该强连通分量，那么它一定属于另一个强连通分量，但当前节点是它的根的祖宗，那么这个强连通分量应该在此之前已经被拿出。现在没有疑问了吧，那么算法介绍就完了。