内容概要：
- 图中的桥
- 图的DFS遍历树和BFS遍历树及其与寻桥算法的关系
- 图的割点
- DFS和BFS的对比小结
桥(割边)
对于无向图，如果删除了一条边，整个图的连通分量数量发生变化，则称这条边为桥(bridge)。
bridge
如在上图中，1-4和2-3的边都是桥。
桥反应的是图中最脆弱的关系，一旦删除桥整个图就断裂了。因此识别图中的桥是很有意义的，比如在一个交通系统中，桥是连接两个城市群的最关键道路，一旦桥发生拥堵或故障，影响的直接是两个城市间的交通。
一个图中的桥可以有多个，如上图就有两个桥；再比如若图是一棵树，那么图中的每条边都是桥。
寻桥算法
方案1：删除图中每条边，对删除后的图求连通分量，判定边是不是桥，此方案时间代价较高；(抛弃)
方案2：DFS遍历过程中维护更多信息，用于判定某条边是否是桥。
DFS寻桥过程
寻桥是要判定边，回顾DFS的过程，在循环中访问顶点之前其实就可以看做对边的访问。
visited[0...V-1] = false;
dfs(0);
dfs(int v){
visited[v] = true;
visit(v);
for(int w: adj(v)){ // 对点的操作
// 对边的操作过程
if(!visited[w])
dfs(w); // 对点的操作
}
}
深度优先遍历序列中w排在v前(不必要相邻)，则w称为v之前的顶点。判断某条边v-w是否是桥，就是看通过w能否找到另一条路回到v或v之前的顶点，如果不能回到，则这条边是桥。
如在上图中，假设访问序列是0,1,4,3,2,5,6，要判定0-1边是否是桥，就要看通过顶点1能否从另一条路回到0；
来到1，判断1-4是否是桥，就要看通过顶点4能否从另一条路回到1或回到0；
......
为此可以定义一个访问顺序数组ord，如上例中，ord[0]=0，ord[1]=1，ord[4]=2，ord[3]=3，ord[2]=4......，同时再记录对于每个顶点，能到达的最小ord值，这个信息用数组low记录，low[v]表示DFS过程中，通过另外一条路，顶点v能到达的最小ord值，如上例中，low[3]=0，2与3相邻，那么就知道从2也能到达ord值为0的点，即low[2]=0，以此类推。这样一来判断某条边v-w是否是桥，就是看通过w能否找到另一条路回到ord值小于等于ord[v]的顶点，如果不能回到，则这条边是桥。
DFS寻桥算法类
边类Edge
public class Edge {
private int v, w;
public Edge(int v, int w){
this.v = v;
this.w = w;
}
@Override
public String toString(){
return String.format("%d-%d", v, w);
}
}
寻桥算法类
import java.util.ArrayList;
// 无向无权图
public class FindBridges {
private Graph G;
private boolean[] visited;
private int ord[];
private int low[];
private ArrayList<Edge> res; // 存储桥边
private int cnt; // 记录顶点的访问顺序值，其实就是当前已经遍历的顶点数(0开始)
public FindBridges(Graph G){
this.G = G;
visited = new boolean[G.V()];
res = new ArrayList<>();
ord = new int[G.V()];
low = new int[G.V()];
cnt = 0;
for(int v = 0; v < G.V(); v ++)
if(!visited[v])// 在各个连通分量中寻找桥
dfs(v, v);
}
private void dfs(int v, int parent){
visited[v] = true;
ord[v] = cnt ++;// ord[v] = cnt; cnt ++;
low[v] = ord[v];
for(int w: G.adj(v))
if(!visited[w]) {
dfs(w, v);
low[v] = Math.min(low[v], low[w]);
// w 没有被访问过，v-w是 条新边，判定它是否是桥
if(low[w] > ord[v])
// v-w 是桥
res.add(new Edge(v, w));
}else if (w != parent){// w 被访问过但不是它的parent节点
// 如果 w == parent,意味着出现了环
low[v] = Math.min(low[v], low[w]);// 由于v和w相邻，故w能到达的最小ord，v也能到达
}
}
public ArrayList<Edge> result(){
return res;
}
public static void main(String args[]){
Graph g = new Graph("g.txt");
FindBridges fb = new FindBridges(g);
System.out.println(fb.result());
}
}
图的DFS遍历树和BFS遍历树
很多图论算法都可以即由DFS解决又由BFS解决，那么寻找桥能否用BFS解决呢，答案是不能。这一点可以由DFS和BFS的遍历树的特点来解释。
遍历的过程中其实相当于生成了一棵树，这棵树就叫遍历树，DFS的遍历树如下图：
DFS
将遍历顺序看做边的指向的话，得到下图：
DFStree
(注意：蓝色边生成树中并没有，但是在DFS遍历过程中是有这样方向的检查的。)
原图中不在在DFS遍历树中边叫后向边，如3-0，6-2都是后向边，最终生成的遍历树上的边叫前向边。DFS遍历树的特点是，后向边可以指向自己的祖先节点。而恰恰是利用这一点我们才能找到图中的桥。如在上图中，由于3能到0，low[3]=0，当DFS遍历回到1和0(3的祖先)时，会把low[0]以及low[1]的值都更新为0，这也就意味着0-1，1-3，3-0都不可能是桥。
但是BFS相当于层次遍历，所以BFS的遍历树就没有DFS遍历树的后向边指向祖先节点的性质，BFS遍历树：
BFStree
原图中不在BFS遍历树中边叫横叉边，BFS的横叉边指向的或者是自己的兄弟节点或者是自己兄弟节点的子节点。而寻找桥要依靠后向边的性质来更新顶点的low值，所以BFS无法完成寻找桥的算法。
割点
对于无向图，如果删除了一个顶点，整个图的连通分量数量发生变化，则称这个点为割点(cut points)。
割点反应的同样是图中最脆弱的关系，割点是图中最脆弱的点。一旦删除桥整个图就断裂了。因此识别图中的割点也是很有意义的，在一个城市交通系统中，割点就是交通枢纽城市。
寻找割点的算法和寻找桥的算法是非常相似的，维护的信息ord和low也相同，
桥的判定：如果v有一个孩子节点w(相对于遍历树)，满足low[w]>ord[v]，则v-w是桥。
割点的判定：如果v有一个孩子节点w(相对于遍历树)，满足low[w]>=ord[v]，则v是割点。
相比于桥的判定，只是多了个等号，这也很好理解，low[w]=low[v]意味着从顶点w最多返回到顶点v，如果把顶点v删除，则与v相邻的边都没有了，w连v都到不了，更不会到达low值比low[v]更小的顶点了。
cut points
但是如果直接将桥代码的>改为>=对于根节点会出问题，因为其他节点的low值不可能比根节点low值小，于是根节点会被永远判定为割点了。所以要对根节点做单独讨论。对于根节点，如果它有一个以上的孩子(DFS遍历树中)，则它是割点。这也很好理解，删除根节点后，如果它的孩子在同一个连通分量，由DFS的性质，他们不可能是兄弟节点，矛盾，故删除根节点后它的多个孩子节点一定隶属于不同的连通分量。
寻找割点算法类
import java.util.ArrayList;
import java.util.HashSet;
// 无向无权图
public class FindCutPoints {
private Graph G;
private boolean[] visited;
private int ord[];
private int low[];
private HashSet<Integer> res; // 存储桥边
private int cnt; // 记录顶点的访问顺序值，其实就是当前已经遍历的顶点数(0开始)
public FindCutPoints(Graph G){
this.G = G;
visited = new boolean[G.V()];
res = new HashSet<>();
ord = new int[G.V()];
low = new int[G.V()];
cnt = 0;
for(int v = 0; v < G.V(); v ++)
if(!visited[v])// 在各个连通分量中寻找桥
dfs(v, v); // 根节点的parent是自己
}
private void dfs(int v, int parent){
visited[v] = true;
ord[v] = cnt ++;// ord[v] = cnt; cnt ++;
low[v] = ord[v];
int rootchild = 0; // 根节点孩子数量
for(int w: G.adj(v))
if(!visited[w]) {
dfs(w, v);
low[v] = Math.min(low[v], low[w]);
rootchild ++;
if(v == parent && rootchild > 1) // 根节点的单独处理
res.add(v);
if(v != parent && low[w] >= ord[v])// v 不是根节点
res.add(v);// v是割点
}else if (w != parent){// w 被访问过但不是它的parent节点
low[v] = Math.min(low[v], low[w]);// 由于v和w相邻，故w能到达的最小ord，v也能到达
}
}
public HashSet<Integer> result(){
return res;
}
public static void main(String args[]){
Graph g = new Graph("g1.txt");
FindCutPoints fc = new FindCutPoints(g);
System.out.println(fc.result());
}
}
注意：为了避免某个割点由多个邻点都可判定而被添加多次，res使用HashSet。
DFS、BFS小结
可以看到，虽然对于很多图论问题使用DFS和BFS都可以解决，但DFS和BFS又都有其特定的用处，BFS的性质可以求无权图最短路径但DFS做不到；DFS可以求图的桥和割点而BFS做不到。
网友评论