第1个回答 2022-07-22
首先先要明确概念：强连通图意为在该图中任意两点间都能够相互到达，而强连通分量即为一个强连通图中的子图，如图中{1,2,3,4}、{5}、{6}即为强连通分量
求强连通分量传统的算法有Kosaraju和Tarjan算法，在这里主要解释Tarjan算法。
Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。Tarjan算法有点类似于基于后序的深度遍历搜索和并查集的组合，充分利用回溯来解决问题。
在Tarjan当中，主要维护以下几个变量：
dfn[i]维护节点i在该图进行dfs时的次序；
low[i]维护节点i最早能回溯到的节点的编号；
vis[i]维护节点i是否已被访问过；
在Tarjan算法运行时，在我们对图进行dfs的过程中，对于每一个节点u和与它相连的节点v，我们进行如下操作：
如果节点v还未被访问过，那么我们就对v进行dfs，通多定义我们就能够得知，这时low[u]=min(low[u],low[v])；
如果说v已被访问过，即v节点已在栈中，那么这时我们就需要用v的dfn值来更新u的low值，有定义可知low[u]=min(low[u],dfn[v])；
对于一个连通图，我们很容易想到，在该连通图中有且仅有一个节点u的DFN值和low值相等，所以我们在回溯的过程中就能够通过判断节点的low值和DFN值是否相等来判断是否已经找到一个子连通图。由于该连通图中 的DFN值和low值相等的节点是该连通图中第一个被访问到的节点，又根据栈的特性，则该节点在最里面。所以能够通过不停 的弹栈，直到弹出该DFN值和low值相同的节点来弹出该连通图中所有的节点。
另外附上一张其他神犇推演Tarjan的演算图：