无向图求割点和割边——Tarjan算法

- 无向图中求割点集和割边集——Tarjan算法
  
  割点和割边
  
  定义
  - 在一个无向图中，如果删除了某个顶点及与之相连的所有边，产生了一更大连通分量的子图，这样的顶点被称为割点或关节点。对于一个图的所有割点的集合被称为割点集。
  - 同理，在无向图中，如果删除了某条边而产生了一个更大连通分量的子图，这样的边被称为割边或桥。对于一个图中所有割边的集合被称为割边集。
  意义
  
  几乎所有的问题都可以转化成图论相关的问题，而割点和割边作为无向图中不可或缺的属性，自然也有很重要的意义。比如在设计交通道路网的时候，设计者必须考虑问题就是如何尽量减少道路图中割点或割边的个数，因为如果存在割点或割边，此处的交通压力自然非常大，显然是设计的时候需要规避的。此外还有很多的应用。
  
  如何求解割点和割边
  
  对于图 $G(V,E)$ ，根据定义，如果要求解割点则需要三步：
  1. BFS跑一遍图，记录下 $G(V,E)$ 的连通分量为 $C$ 。
  2. 枚举所有顶点 $v_i$ 并删除，再用BFS跑一边删除顶点后的子图，求出子图的连通分量 $C_i$ 。
  3. 比较 $C$ 和 $C_i$ ，如果 $C_i < C$ 则说明 $v_i$ 是割点，反之不是。
  由于要枚举所有顶点，而且对于每个结点都要遍历一遍子图，所以该算法的时间复杂度为
  $T = \begin{cases} O(|V|^3) & 邻接矩阵\\[2ex] O((|V| + |E|)\cdot |V|) & 邻接表 \end{cases}$
  同理，根据定义求割边的算法时间复杂度为
  $T = \begin{cases} O(|E|\cdot|V|^2) & 邻接矩阵 \\[2ex] O((|V|+|E|)\cdot|E|) & 邻接表 \end{cases}$
  
  Tarjan算法
  
  算法提出者
  
  割点和割边如此重要，如何利用计算机高效计算无向图的割点集和割边集也是计算机科学家们需要解决的问题。
  
  Robert Tarjan，1986年图灵奖获得者提出了一种利用DFS回溯法解决无向图的割点割边问题的算法，故被称为Tarjan算法。顺便一提此，此人也对并查集的分析与应用做出了很大的贡献。
  
  需要注意的是，Tarjan算法最初提出是为了解决强连通图中强连通分量问题的，这里也可以用它来解决无向图的割点和割边问题。
  
  算法理论介绍
  - 思考
    
    在介绍理论之前我们先思考，除了定义之外，我们还能用什么方法判断割点和割边。可以这么想，如果一个顶点是割点，它或它的邻结点会有什么特殊的性质。
    
    可以假 $v_i$ 不是割点，其邻结点为 $v_{i1},v_{i2},\dots,v_{ik} \text{ ,k}$ 是 $v_i$ 邻结点的总数，设 $Path(v_m,v_k,v_n) = 1$ 表示 $v_m$ 和 $v_n$ 之前存在至少一条不经过 $v_k$ 的简单道路， $Path(v_m,v_k,v_n)=0$ 表示不存在这样的简单道路。则很容易得出 $\forall m \in[1,k]\forall n \in[1,k]Path(v_{im},v_i,v_{in})=1$ 。
    
    则对这个问题的逆否命题为如果 $\text{存在 }m \in[1,k]\text{存在 } n\in[1,k]Path(v_{im},v_i,v_{in})=0$ ，那么 $v_i$ 为割点且二者互为充要。同理，设 $PathEdge(v_m,e_{m-n},v_n) = 1$ 表示 $v_m$ 和 $v_n$ 是邻结点，且这两点之间存在至少一条不经过其直接相连的边 $e_{m-n}$ 而相连的简单道路， $PathEdge(v_m,e_{m-n},v_n) = 0$ 表示 $v_m,v_n$ 间不存在这样的一条道路。则类似可以推理出如果 $\text{存在 } m \in [1,k] PathEdge(v_i, e_{i-im},v_{im})=0$ ，那么 $e_{i-im}$ 为割边。
  - 图的表示
    
    在设计图论算法之前，我们需要考虑的就是如何在程序中表示一份图 $G(V,E)$ 。结合算法的内容，我在这里用邻接表的方法存储一份无向图。
  - 顶点的孩子，父亲和祖先
    
    以任意顶点为根结点，采用DFS的策略从根结点遍历图。
    - 一个顶点的孩子为在这种遍历方式下当前顶点的下一个顶点。
    - 一个顶点的父亲为在这种遍历方式下当前顶点的上一个顶点，根结点没有父亲。
    - 一个顶点的祖先为在这种遍历方式下当前顶点之前除了父亲的所有顶点，同理根结点没有祖先。
  - dfn数组和low数组
    
    两个数组的空间大小为顶点个数 $|V|$ ，分别表示每一个顶点的属性，假设所有顶点编号 $[0,|V| - 1]$ 。
    - $dfn[i]$ 表示在DFS回溯的前提下，该结点 $v_i$ 被遍历的时间先后顺序，也就是时间戳，顺序递增。
    - $low[i]$ 表示在DFS回溯的前提下，该结点 $v_i$ 不通过父亲到 $v_i$ 这条边所能连通的顶点时间戳的最小值。初始 $low[i]=dfn[i]$ 。
    示例
    
    无向图
    
    我们以为根结点进行DFS回溯维护和。时间戳从1开始。
    
    顶点v0
    
    顶点如果有多个孩子，这里优先选择顶点编号较小的遍历。
    
    顶点v1
  顶点v3
  
  顶点v4
  
  这里注意，顶点下一个遍历的顶点是，而，所以。
  
  重置顶点v4
  
  顶点v5
  
  DFS处理到末尾后向前回溯，同时维护，这里回溯到顶点，重置。
  
  重置顶点v3
  
  顶点v2
  
  DFS回溯结束，和都处理完毕。
  - 割点与割边的判断
    
    $dfn$ 和 $low$ 都处理完毕之后，根据我们之前的分析，很容易得出，如果一个父亲 $v_f$ 的所有孩子 $v_{ci}，i\in[0,k]$ 。 $k$ 是 $v_f$ 子结点总数。
    
    如果 $\text{存在 } i \in[0,k](low[ci] >= dfn[v_f])$ ，则 $v_f$ 为割点。
    
    如果 $\text{存在 }i \in[0,k](low[ci] > dfn[v_f])$ ，则 $e_{f-ci}$ 为割边。
    
    这也正说明了一个图中割边的数量永远不会超过割点的数量。
  - 复杂度分析
    $Tarjan$ 算法仅用两次DFS回溯就可以得到所有割点和割边，不必暴力枚举，所以对于无向图 $G(V,E)$ 在这种条件下时间复杂度为 $O(|V|+|E|)$ 。

程序展示(c++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const int maxn = 1e3 + 10;
const int maxm = 1e6 + 10;

int tst;    // timestamp
int N, M;   // 顶点数N，边数M

struct Edge {
    int from, to;
    Edge(int f = 0, int t = 0):
        from(f), to(t) { }
    ~Edge() { }
};

// adj-list undirected graph
// idx -> even with compone idx + 1.
vector<Edge> edges;    //所有边的集合
vector<int> ver[maxn]; //记录每一个顶点出发的边在edges中的索引
int dfn[maxn];
int low[maxn];

vector<int> verCut;    //割点集
vector<Edge> edgeCut;  //割边集

/**
 * @brief 读取数据，以邻接表方式储存，因为是无向图需要一条边存两次
 *        第1行输入N和M表示图的顶点数和边数
 *        接下来第2到第M + 1行输入from和to表示无向图的一条边的两个顶点.
 */
void readData() {
    cin >> N >> M;
    for (int inc = 0; inc < M; inc ++) {
        int from = 0, to = 0;
        cin >> from >> to;
        ver[from].push_back(edges.size());
        edges.push_back(Edge(from, to));
        ver[to].push_back(edges.size());
        edges.push_back(Edge(to, from));
    }
}

/**
 * @brief DFS回溯上标签
 * @param curr_ver 当前顶点的编号
 * @param fa_ver   当前顶点的父亲编号，根节点父亲设为-1
 */
void labelling(int curr_ver = 0, int fa_ver = -1) {
    dfn[curr_ver] = low[curr_ver] = ++tst;  //初始化dfn和low
    for (vector<int>::iterator iter = ver[curr_ver].begin();
        iter != ver[curr_ver].end(); iter ++) {
        if (edges[*iter].to == fa_ver)
            continue;
        if (!low[edges[*iter].to]) {
            labelling(edges[*iter].to, curr_ver);
        }
        low[curr_ver] = min(low[curr_ver], low[edges[*iter].to]);
    }
}

/**
 * @brief 收集统计割点及割边
 */
void collect(int curr_ver = 0, int fa_ver = -1) {
    tst++;
    bool is_vercut = false;
    for (vector<int>::iterator iter = ver[curr_ver].begin();
         iter != ver[curr_ver].end(); iter++) {
        if (edges[*iter].to == fa_ver || dfn[edges[*iter].to] != tst + 1)
            continue;
        collect(edges[*iter].to, curr_ver);
        int sub = low[edges[*iter].to] - dfn[curr_ver];
        is_vercut = (sub >= 0);
        if (sub > 0) {
            edgeCut.push_back(Edge(curr_ver, edges[*iter].to));
        }
    }
    if (is_vercut) {
        verCut.push_back(curr_ver);
    }
}

/**
 * @brief tarjan算法，包含两个子函数，调用函数前需要将时间戳重置
 */
void tarjan() {
    tst = 0;
    labelling();

    tst = 0;
    collect();
}

void show() {
    cout << "vertex cut(s):" << endl;
    cout << "total: " << verCut.size() << endl;
    for (vector<int>::iterator iter = verCut.begin();
        iter != verCut.end(); iter ++) {
        cout << (*iter) << endl;
    }

    cout << "edge cut(s):" << endl;
    cout << "total: " << edgeCut.size() << endl;
    for (vector<Edge>::iterator iter = edgeCut.begin();
         iter != edgeCut.end(); iter ++) {
        cout << (*iter).from << " to " << (*iter).to << endl;
    }
}

int main() {
    //freopen("Tarjan.txt", "r", stdin);

    readData();

    tarjan();

    show();

    return 0;
}

/*****测试数据******
6 6
0 1
1 3
3 4
4 5
1 4
1 2
*******************/

无向图求割点和割边——Tarjan算法

无向图中求割点集和割边集——Tarjan算法

割点和割边

如何求解割点和割边

Tarjan算法

示例

程序展示(c++)