[转] 强连通分量的DFS求解算法

作者：___Blue_H
来源：CSDN
原文：https://blog.csdn.net/qq_37653144/article/details/83276040

强连通分量

在有向图中，如果顶点v和w相互可达，则称这两个顶点之间强连通。一幅图中任意两点之间强连通则称这幅图为强连通图。有向图的极大强连通子图就是有向图的 强连通分量（Strongly Conneted Component）。

强连通有如下性质：

（1）自反性：任意顶点v和自身是强连通的。

（2）对称性：如果v和w是强连通的，那么w和v也是强连通的。

（3）传递性：如果v和w是强连通的且w和x也是强连通的，那么v和x也是强连通的。

强连通分量即是基于强连通的性质，将相互均为强连通的顶点划分在一起构成的最大子集。强连通性是非常重要的抽象，它突出了相互关联的几组顶点（强连通分量），对事物的分类有很大帮助。

Kosaraju算法

Kosaraju算法是求解有向图连通分量较简单的算法，它需要用到原图及其转置图（转置图即所有边的方向与原图一一对应且相反）来进行深度优先搜索。既然强连通是指顶点之间相互可达，那么我们只需要求出原图的连通分量（求解图的连通分量），然后在其转置图中再执行搜寻，原图和转置图对应的每一个连通分量的交集就是我们要求的强连通分量。

在对转置图进行搜寻的过程中，起始顶点的选择需要有所限制，否则可能搜寻到其他连通分量中，这是不允许的（强连通分量只能存在于单个强连通图，即单棵树中）。Kosaraju算法巧妙地选择了“最晚离开的”顶点，因为对任意顶点v和w假设是强连通的，在第一次搜寻过程中已经得到了v→w，那么就需要证明存在路径使得w→v，即证明转置图中存在路径使得v→w。在对转置图进行深度优先搜索的过程中，dfs(w)肯定在dfs(v)之前就结束了，且在原图中存在v→w即转置图中存在w→v，所以只可能有唯一一种情况——在转置图中对dfs(w)的调用必然在dfs(v)之前结束，因此可以证明该算法思想的正确性。

对于“最晚离开的”顶点，我们联想栈调用的特性就可以知道，对原图的逆后序遍历得到的顶点顺序就是要对转置图进行深度优先搜索时应遵循的起始顶点顺序。再结合拓扑排序的特点，如果我们把求出来的每个强连通分量收缩成一个点，并且用求出每个强连通分量的顺序来标记收缩后的节点，那么这个顺序其实就是强连通分量收缩成点后形成的有向无环图的拓扑序列。

综上，Kosaraju算法的执行流程主要是以下两步：

• （1）对原图进行深度优先搜索，得到原图的逆后序遍历的顶点顺序。

• （2）以（1）中的顶点顺序作为对转置图进行深度优先搜索的起始顶点选择顺序，对转置图进行遍历，删除（或标记）能够遍历到的顶点，这些顶点构成一个强连通分量。当还有顶点没有删除或标记时回到（1）继续执行，否则结束。

该算法需要进行两次DFS，效率并不算高。对于比较庞大的有向图来说，递归调用容易导致栈溢出，可以将DFS部分用非递归代码来实现。

/*
 
struct UndirectedGraph
{
    size_t V, E; //V表示顶点数，E表示边数
    map<int, forward_list<int>> adj;
};
*/
 
void get_post_dfs(const DirectedGraph &g, vector<int> &visited, vector<int> &post_order, int v)
{
    visited.at(v) = 1;
    for (const int &i : g.adj.at(v).second)
    {
        if (visited.at(i) == 0)
        {
            dfs(g, visited, post_reverse_order, i);
        }
    }
    post_reverse_order.push_back(v);
}
 
void dfs(const DirectedGraph &g, vector<int> &visited, vector<pair<int, int>> &cc, int v)
{
    if (visited.at(v) == 1)
    {
        continue;
    }
    g.adj.at(v) = 1;
    for (const int &i : g.adj.at(v))
    {
        if (visited.at(i) == 0)
        {
            cc.push_back(make_pair(v, i));
            dfs(g, visited, cc, i);
        }
    }
}
 
vector<vector<pair<int, int>>> FindStronglyConnectedComponent(const DirectedGraph &g, const DirectedGraph &gt) //gt是g的转置图
{
    vector<vector<pair<int, int>>> ans;
    vector<int> visited(g.V);
    vector<int> post_order;
    get_post_dfs(g, visited, post_order, (*g.adj.cbegin()).first); //得到原图的后序遍历序列（反向即为逆后序）
 
    //标记数组初始化
    for (int &i : visited)
    {
        i = 0;
    }
 
    //对转置图DFS得到强连通分量
    for (auto ite = post_order.crbegin(); ite != post_order.crend(); ++ite)
    {
        vector<pair<int, int>> cc;
        dfs(gt, visited, cc, *ite);
        ans.push_back(move(cc));
    }
    return ans;
}

---

Tarjan算法

Tarjan算法基于强连通分量的一个性质：任何一个强连通分量，必定是对原图进行深度优先搜索得到的子树。所以我们只需要找出每个子树（强连通分量）的根，然后从这棵子树的最底层开始一个一个拿出强连通分量的顶点即可。

现在关键在于如何找出连通分量的根,以及找到根后如何拿出强连通分量的顶点。

根与其所在连通分量不同之处在于它能够到达其所在连通分量的其他顶点，反之也可达，但不在这个连通分量的顶点到达不了这个根。Tarjan算法的思想是维护两个数组来寻找连通分量的根，其中一个数组dfn用来记录深度优先搜索访问顶点的顺序，另一个数组low则记录一个顶点能到达的最大子树的根（即dfn值最小的顶点）。当一个顶点的dfn值与low值相等时即说明它就是一个连通分量的根。因为如果它不是强连通分量的根，那么它一定是属于另一个强连通分量，而且不是根，那么就存在包含当前顶点的到根的回路，可知low一定会被更改为一个比dfn更小的值，而不是相等。

至于如何拿出强连通分量，如果当前节点为一个强连通分量的根，那么它的强连通分量一定是以该根为根节点的(剩下节点)子树。在深度优先遍历的时候维护一个栈，每次访问一个新节点，就压入栈。这样，由于当前节点是这个强连通分量中最先被压入堆栈的，那么在当前节点以后压入堆栈的并且仍在堆栈中的节点都属于这个强连通分量。可以用反证法证明这个做法的正确性：假设一个节点在当前节点压入堆栈以后压入并且还存在，同时它不属于该强连通分量，那么它一定属于另一个强连通分量，但当前节点是它的根的祖宗，那么这个强连通分量应该在此之前已经被拿出。

综上，Tarjan算法的整体流程如下：

对图进行深度优先遍历，用序号标记遍历到的顶点的先后顺序（对dfn数组赋值）并将新顶点压入栈中，在回溯过程中维护low数组，标记当前顶点能到达的最大子树的根（即dfn值最小的顶点）。在回溯过程中遇到dfn值与low值相等的即为当前连通分量的根。找到根后，此时栈中元素就是该连通分量的顶点，将其一个个拿出即可。

运行Tarjan算法的过程中，每个顶点都被访问了一次，且只进出了一次栈，每条边也只被访问了一次，所以该算法的时间复杂度为O(V+E)。在大型连通图中，为了避免递归深度过大而导致效率降低和栈溢出，可以将第一个DFS也改为栈来实现。

同时在分析Tarjan算法的过程中我们也可以发现，这个算法还可以用于求解无向图的割边桥，已经求解最近公共祖先（LCA）。

 
void Tarjan(DirectedGraph &g, vector<vector<int>> &scc_set, vector<int> &visited, vector<int> &dfn, vector<int> &low, vector<int> &in_stack, stack<int> &st)
{
    dfn[u] = low[u] = ++cnt;
    st.push(u);
    in_stack[u] = 1;
    for (const auto &v : g.adj.at(u))
    {
        if (!visited[v])
        {
            Tarjan(g, v);
            low[v] = min(low[u], low[v]);
        }
        else if (in_stack[v])
        {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u])
    {
        vector<int> scc;
        do
        {
            v = st.top();
            st.pop();
            scc.push_back(v);
            in_stack[v] = 0;
        } while (u != v);
        scc_set.push_back(move(scc));
    }
}
 
vector<vector<int>> FindStronglyConnectedComponent(DirectedGraph &g)
{
    static int cnt = 0;
    vector<int> dfn(g.V);    //DFS访问顶点的顺序
    vector<int> low(g.V);    //当前顶点能到达的最大子树的根
    vector<int> visited(g.V);    //访问标记
    stack<int> st;    //存放强连通分量顶点的栈
    vector<int> in_stack(g.V);    //判断顶点是否在栈中
    vector<vector<int>> scc_set;
    for (auto ite = g.adj.cbegin(); ite != g.adj.cend(); ++ite)
    {
        Tarjan(g, scc_set, visited, dfn, low, in_stack, st);
    }
    return scc_set;
}