【数据结构与算法基础】代码仓库：https://github.com/jinrunheng/datastructure-and-algorithm

一：桥

什么是桥？
image.png
对于这个无向图来说，如果删除了一条边（图中红色的边），整个图的联通分量数量就会发生了变化，则这条边称为桥（Bridge）。桥也意味着图中最脆弱的关系。

举个例子，如果上面的图对应的是一个城市的交通系统，那么连接 3 和 5 这两个顶点的桥就是图中最脆弱的那条边，如果这个边发生了交通堵塞 ，那么整个城市的交通都有可能出现瘫痪。

对于一个图来说，可以有多条桥

image.png
并且，我们知道，树也是一种特殊的图，一棵树的每一条边都是一条桥

image.png

二：寻找桥的算法

代码链接🔗

寻找桥的算法相对来说比较难，往往在算法竞赛中会涉及，而一般的面试中并不会涉及。

寻找桥的算法思路

image.png
首先，桥的本质是图中的一条边。我们如果要寻找图中的桥，必然要遍历图的每一条边，这个过程仍然是在图的遍历中发生的。

那么如何判断顶点 v 和顶点 w 对应的边 v-w 是否是一条桥呢？

我们只需要看通过顶点 w ，能否从另一条路回到顶点 v 或者 v 之前的顶点。

对于上图而言，我们知道顶点 2 是通过遍历顶点 3 而来的。所以，如果我们要判断顶点 2 和 顶点 3 之间的边是否是一条桥，我们只需要判断，对于顶点 2 是否有另一条路回到顶点 3 或者是 3 之前的顶点，如果存在，则意味着顶点 2 和 3 之间的边不是一条桥。

那么，具体该如何实现呢？

首先，我们需要使用一个数组 ord 来记录对于每一个顶点 DFS 遍历的顺序。

除了要记录 ord 数组，我们还要记录一个信息：对于每一个顶点，记录能到达的最小的 ord 的值。

这个信息我们使用数组 low 来表示，low[v] 表 DFS 过程中，顶点 v 能到达的最小 ord 值。

对于上面的这个图，模拟过程如下所示：

find bridge.key
算法的伪代码如下：

  1. visited[0...V-1] = false;
  2. ord[0...V-1] = 0;
  3. low[0...V-1] = 0;
  4. cnt = 0;
  6. for(int v = 0; v < V; v++)
  7.     if(!visited[v])
  8.         dfs(v,v);
  10. dfs(int v,int parent) {
  11.     visited[v] = true;
  12.     ord[v] = cnt;
  13.     low[v] = ord[v];
  14.     cnt++;
  16.     for(int w : adj(v))
  17.         if(!visited[w]){
  18.             dfs(w,v);
  19.             low[v] = min(low[v],low[w]);
  20.             if(low[w] > ord[v])
  21.                 // v-w is a bridge
  22.                 list.add(v-w);
  24.         }else if(w != parent) {
  25.             // find loop, v-w is not a bridge
  26.             low[v] = min(low[v],low[w]);
  27.         }
  28. }

对于上面给出示例的图，我们编写的算法类运行的结果如下：

  1. [3-5]

三：图的遍历树

DFS 遍历树

image.png
对于上面的图，我们从顶点 0 开始，使用 DFS 进行遍历，结果为：0，1，3，2，5，4，6，按照顶点遍历的顺序走过的边依次连接，在示意图中，我已经用蓝色进行标明了，将其展开后，就形成了一棵 DFS 遍历树，如右侧所示。

0-2 和 5-6 这两条边，我没有标蓝的原因在于，DFS 遍历时，从顶点 2 看向顶点 0，发现顶点 0 已经被遍历过了。同理，从顶点 6 看向顶点 5，顶点 5 已经被遍历过了。如果我们将 0-2 这条边与 5-6 这条边连接上，DFS 遍历树就可以还原成图了：

image.png
在右侧的图中，我特意加上了指向符号，意义就在于，我们可以看清每一个节点的父节点是谁。我们可以清晰地看到每个节点的祖先节点是什么，0，5 这两个节点是图中两个环的祖先节点。求解桥的算法就是利用 DFS 的这一点来完成的。

BFS 遍历树

image.png
对于上面的图，我们从顶点 0 开始，使用 BFS 进行遍历，结果为：0，1，2，3，5，4，6，按照顶点遍历的顺序走过的边依次连接，在示意图中，我已经用蓝色进行标明了，将其展开后，就形成了一棵 BFS 遍历树，如右侧所示。

如果像 DFS 一样，将 BFS 遍历树还原成图：
image.png
我们就会发现，通过 BFS 遍历是无法求解寻找桥的算法的。

四：寻找割点的算法

什么是割点

image.png
对于无向图，如果删除了一个顶点（顶点的邻边也删除），整个图点联通分量的数量发生了变化，则这个顶点被称为割点（Cut Pints/Articulation Points）。

我们知道，桥反映的是图中最脆弱的边，那么割点反映的就是图中最脆弱的点。

寻找割点的算法

代码链接🔗

寻找割点的算法和寻找桥的算法基本一致：

image.png
这里需要注意两点：

  1. 寻找桥的算法中，我们判断 low[w] > ord[v] ，在寻找割点的算法中，我们需要判断 low[w] >= ord[v]
  2. 如果采用上面的逻辑判断，那么根节点一定被判断为割点，所以我们要对根节点进行特殊处理

根节点的处理方法如下：
image.png

看根节点有多少个孩子，是要看图的遍历树的。而不是看这个图。

寻找割点的算法伪代码如下所示：

  1. visited[0...V-1] = false;
  2. ord[0...V-1] = 0;
  3. low[0...V-1] = 0;
  4. cnt = 0;
  6. for(int v = 0; v < V; v++)
  7.     if(!visited[v])
  8.         dfs(v,v);
  10. dfs(int v,int parent) {
  11.     visited[v] = true;
  12.     ord[v] = cnt;
  13.     low[v] = ord[v];
  14.     cnt++;
  16.     int child = 0;
  17.     for(int w : adj(v)){
  18.         if(!visited[w]){
  19.             dfs(w,v);
  20.             low[v] = min(low[w],low[v]);
  21.             if(v != parent && low[w] >= ord[v])
  22.                 res.add(v);
  24.             child++;    
  25.             if(v == parent && child > 1)
  26.                 res.add(v);
  28.         }else if (w != parent){
  29.             low[v] = min(low[w],low[V]);
  30.         }
  31.     }
  32. }