Algorithm

寻找连通图中的桥

算法学习笔记

Posted by Nicodechal on 2019-10-14

从概念上讲，连通图，就是任意两点都连通的无向图，连通，就是指两个点有路径相连。而桥，简单来讲就是图上的一条边，如果去掉这条边，原图就不再是连通图。本文考虑如何找出所有的这样的边。

算法思路

这里使用的方法思路来源于 Tarjan 算法，该算法用于求有向图中的强连通分量，这里借用其思路来寻找无向图中的桥。

该算法的基本思路是，

  1. 首先对图进行一次 DFS 搜索，并对节点按照遍历到的顺序进行编号存放在 dfn 数组 dfn[i] 是第 i 个节点的遍历顺序。
  2. 然后，对于每个节点，计算其在不经过其父节点时能够达到的编号最小值。父节点就是第一次 DFS 搜索时的进入该节点的前一个节点 (也即 DFS 搜索树上的父节点)，存放在 low 数组中，low[i] 是第 i 个节点不走父节点能到的最小的 dfn 值。
  3. 最后，对于每条边 ab (假设 a 节点先被遍历)，如果有 dfn[a] < low[b] 则 ab 边为桥。

这里的判断是指，如果一个节点 ( a ) 的子节点 ( b ) 无法不通过其父节点 ( a ) 达到父节点 (dfn[a] == low[b]，这里指不直接走父节点到父节点) 或达到父节点前面的节点 (dfn[a] > low[b]) 则说明如果没有 ab 这条边，b 节点无法和 dfn 编号小于等于 dfn[a] 的节点相关联，于是原图不再是连通图，所以 ab 是一个桥。以下图为例

1
2
3
4
5
6
7
8
9
 ------------
|            |
1 --- 2 ---- 3
      |
      |
      |
      4 --- 5
      |     |
      7---- 6

对于边 24，节点 4 不经过节点 2 能达到的 dfn 最小节点为 low[4] = 4 > dfn[2]( 自己 )。所以 24 为桥。

算法实现

下面对关键的部分进行实现，实际实现时，以上步骤可以在一次遍历中完成：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const dfn = Array(n).fill(-1), low = Array(n).fill(-1); 
let stp = 0;
const ans = [];
const dfs = (idx, fa) => {
    // 首先将当前节点的 dfn 和 low 都设为遍历序号
    dfn[idx] = low[idx] = stp++;

    for (const v of g[idx]) {
        // 通过 dfn 值判断是否已经遍历该点，默认值为 -1.
        if (dfn[v] < 0) {
            // 向下递归，传入节点和其父节点
            dfs(v, idx);
            // 到这里 low[v] 应该已经算好了
            // 当前节点的 low 值是子节点 low 值得最小值
            low[idx] = Math.min(low[idx], low[v]);
            // 到这里当前节点的 dfn 和 子节点 的 low 都更新好了，判断一下这条边是不是桥
            if (dfn[idx] < low[v]) ans.push([idx, v]);
        } 
    }
}

小结

本文使用 Tarjan 算法的思路，在连通图中对桥边进行了搜索，总体上基于 DFS 实现，使用两个数组记录每个节点的遍历编号 dfn 和不经过父节点的可达最小遍历编号 low 再通过比较边的两端点的 dfn 和 low 值了解该边是否为桥。

这个算法将条件改为 dfn[idx] <= low[v] 即可判断割点，等号表示一个节点不经过其父节点最多可以到达父节点 ( 即不直接走父节点，通过其他点到达，且只能到达父节点，不能到达父节点前面的节点 )，此时父节点就是一个割点，因为如果去掉父节点，子节点没法和父节点前面的节点连通了。

参考资料

Tarjan 算法
Critical Connections in a Network

FEATURED TAGS
Algorithm
FRIENDS