强连通分量算法

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

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

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

(1)强连通分量算法扩展阅读：

强连通分量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]更小的值。

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

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

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

‘贰’ tarjan算法详解--关于图的连通性 & 连通分量

Tarjan算法关于图的连通性和连通分量的详解如下：

有向图的强连通分量： 定义：在有向图中，如果存在一个子图，该子图中的任意两点间都存在双向可达路径，并且这个子图不能再扩大，则称这个子图为强连通分量。典型的例子是环。 时间戳和追溯值：在深度优先搜索过程中，为每个节点分配一个首次访问时间戳dfn，以及一个用于追踪子树中最早访问节点的low值。 计算方法：使用栈记录DFS路径，通过深度优先遍历更新low值。当发现某个节点的low值大于或等于其父节点的dfn值时，说明形成了一个强连通分量。

无向图的割点与桥： 割点：在无向图中，如果删除某个点后，图被分割成两个或更多个连通子图，则该点被称为割点。 桥：在无向图中，如果删除某条边后，图被分割成两个或更多个连通子图，则该边被称为桥。 判定桥：通过比较节点的dfn值和其子节点的low值来判断。如果边满足dfn[x] < low[y]，则说明没有其他路径可以从y到达x之前的节点，因此边是桥。

无向图的双连通分量： 点双连通分量：无割点的无向图中，极大且任意两点都在某个环中的连通子图。如果图中只有一个孤立点，它也构成一个点双连通分量。 边双连通分量：无桥的连通块，即每个连通块都是一个边双连通分量。

Tarjan算法通过深度优先搜索和栈等数据结构，高效地计算图的连通性和连通分量，对于理解图的结构和优化问题求解具有重要意义。