Tarjan演算法求割點

定義

如果在一個圖中，洗掉某個節點連同與之關聯的邊，會導致整個圖的連通分支數增加，那么這個節點叫做 割點（Articulation Point, Cut Vertex）

如下圖：

整個圖的連通分支數為1，但是洗掉節點3后，整個圖就“分裂”成了2個連通分支：

因此，節點3是整個圖的割點，

方法

一個很容易想到的方法是，依次洗掉圖中的每一個節點，看剩下部分的連通分支數增沒增加，但是那樣顯然太浪費時間了！有沒有一種辦法，能夠快速的找出整個圖的割點呢？

Tarjan演算法的核心思想：深度優先遍歷(DFS)這張圖，得到的DFS樹（由遍歷路徑和節點構成的樹）中，當某個節點u滿足以下條件之一時，它就是割點：

1. u為DFS樹的樹根，且u有2棵及以上的子樹，如圖（三角形代表子樹）：
   
2. u不為DFS樹的樹根，且對于u在DFS樹中的任意一個后代v，都必須先經過u才能通往u的祖先，如圖（藍綠色箭頭代表DFS路徑）：
   

注意第一點并不等價于u有2個及以上的鄰居，因為這些鄰居有可能處于同一個DFS樹，比如下面這張圖，u有2個鄰居，但卻只有一個子樹，因此u不是整個圖的割點，

第二點也不難理解，如果v必須先經過u才能到達u的祖先的話，那么去掉u就無路可走了，連通分支數會增加，u就是割點，

DFS

我們可以維護兩個陣列：dfn和low，其中：

• dfn[u]代表u被遍歷到的次序（時間戳），如果節點u先于節點v被訪問，那么dfn[u] < dfn[v]，規定根節點的dfn為1，
• low[u]代表從u的后代出發，在不經過父節點的情況下能夠“另辟蹊徑”回溯到的最先遍歷到的祖先的dfn，（每一步都不能走到當前走到的節點的父節點，且走到某個祖先就馬上記錄low）

設u、v分別為DFS樹中的兩個節點，且v是u的后代，那么如果low[v] >= dfn[u]，那么從v不經過父節點是走不到u的祖先的，則u就是割點，如圖所示，（藍綠色箭頭表示DFS路徑，黃綠色箭頭表示回溯路徑）

舉個栗子吧，以下面這張圖為例：

從節點0開始DFS，因為節點0是最開始遍歷的節點，因此它的dfn和low均為1，

節點0有兩個子節點，不妨先從1開始，因為我們還沒有走到3和2，所以我們將1的low暫定為2，

繼續走下去：

節點3有3個子節點，先從節點4開始DFS，中間程序省略，直接一步到位走到5：

因為從5開始可以不經過父節點直接走到祖先3，將5的low更新為3，回溯到4，因為5是4和6的后代，按照low的定義，同樣的可以將low更新為3，

繼續回溯到3，由于4和5都已經訪問過了，還剩2沒訪問，先走到2，

從2可以不經過父節點直接走到0，更新2的low為1；回溯的時候也將相應節點的low更新為1，

由此可以得到一個所有節點的dfn和low的表格（按dfn由小到大排序）：

對于節點3來說，因為它的所有后代4、6、5的low均等于3的dfn，所以從這些節點出發不經過父節點是不能走到3的祖先的，因此3是整幅圖的割點，

代碼實作

首先給出兩個型別別名：node_t和order_t，用以使語意更加明確：

using node_t = unsigned long long;
using order_t = unsigned long long;

因為這里主要利用兩個頂點之間的鄰接關系，這里圖使用鄰接表來表示：

class Graph {
    unsigned long long n;
    vector<vector<node_t>> adj;

protected:
    void dfs(node_t cur, node_t parent, vector<order_t> &dfn, vector<order_t> &low, order_t &order, unordered_set<node_t> &aps);

public:
    Graph(initializer_list<initializer_list<node_t>> list) : n(list.size()), adj({}) {
        for (auto &l : list) {
            adj.emplace_back(l);
        }
    }

    unordered_set<node_t> findAP();
};

“尋找割點”的代碼整體框架：

unordered_set<node_t> Graph::findAP() {
    vector<order_t> dfn(n, 0); // 未被訪問過的節點的dfn和low初始化為0
    vector<order_t> low(n, 0);
    order_t order = 0;
    unordered_set<node_t> aps;
    node_t root = 0;
    dfs(root, -1, dfn, low, order, aps);
    return aps;
}

DFS的大體框架：

void Graph::dfs(node_t cur, node_t parent, vector<order_t> &dfn, vector<order_t> &low, order_t &order, unordered_set<node_t> &aps) {
    size_t children = 0; // 當前節點的子樹數量
    dfn[cur] = low[cur] = ++order;
    for (node_t neighbor: adj[cur]) {
        if (dfn[neighbor] == 0) {
            children++;
            dfs(neighbor, cur, dfn, low, order, aps);
            // ...
        } else {
            // ...
        }
    }
}

其中部分形參代表的意義：

• cur：當前遍歷到的節點，
• parent：當前節點的父節點（根節點的父節點規定為-1）
• order：遍歷到的次序，
• aps：儲存割點的集合，

問題來了，low怎么計算，

假設當前遍歷到的節點u的某一個鄰居為v：

1. 若v為u的子節點，則low[u]更新為low[u]與low[v]取最小值，
2. 若v不為u的子節點，也不是u的父節點，則說明從u出發可以不經過父節點直接到達v，此時low[u]更新為low[u]與dfn[v]的最小值，

代碼實作如下：

if (dfn[neighbor] == 0) {
    // ...
    low[cur] = min(low[cur], low[neighbor]);
    // ...
} else if (neighbor != parent) {
    low[cur] = min(low[cur], dfn[neighbor]);
}

割點的判定，上文已有提及，直接上代碼：

if (dfn[cur] == 1 && children > 1 || dfn[cur] > 1 && low[neighbor] >= dfn[cur]) {
    aps.insert(cur);
}

完整代碼：

void Graph::dfs(node_t cur, vector<order_t> &dfn, vector<order_t> &low, order_t &order, unordered_set<node_t> &aps) {
    size_t children = 0;
    dfn[cur] = low[cur] = ++order;
    for (node_t neighbor: adj[cur]) {
        if (dfn[neighbor] == 0) {
            children++;
            dfs(neighbor, dfn, low, order, aps);
            low[cur] = min(low[cur], low[neighbor]);
            if (dfn[cur] == 1 && children > 1 || dfn[cur] > 1 && low[neighbor] >= dfn[cur]) {
                aps.insert(cur);
            }
        } else if (neighbor != parent) {
            low[cur] = min(low[cur], dfn[neighbor]);
        }
    }
}

測驗：

int main() {
    Graph graph{{1, 2},
                {0, 3},
                {0, 3},
                {1, 2, 4, 5},
                {3, 6},
                {3, 6},
                {4, 5}};
    auto aps = graph.findAP();
    cout << "The articulation points are:" << endl;
    for (node_t ap: aps) {
        cout << ap << ' ';
    }
    cout << endl;
    return 0;
}

輸出：

The articulation points are:
3

復雜度分析

• 時間復雜度：\(O(n+e)\)，其中 \(n\) 代表節點數，\(e\) 代表邊數，DFS的時間復雜度為\(O(n+e)\)，
• 空間復雜度：\(O(n+e)\)，其中 \(n\) 代表節點數，\(e\) 代表邊數，鄰接表的空間復雜度為 \(O(n+e)\)，維護的陣列的空間復雜度為 \(O(n)\)，加起來為 \(O(n+e)\)，

本文來自博客園，作者：YVVT_Real，轉載請注明原文鏈接：https://www.cnblogs.com/YWT-Real/p/16992625.html

標籤：其他

上一篇：二分的邊界問題

下一篇：二叉樹的最大/最小深度