一、桥
1.1 定义
对于无向图，如果删除了一条边，整个图的联通分量数量变化，则这条边称为桥
如图，红色标注的线就是该图的一条桥(顶点3和顶点5的边)。
1.2 性质
- 一个图中可以有多条桥
如下图，红色的边都是图中的桥
- 一棵树的所有边都是桥
如下图，红色边都是图中的桥，一颗树中任意一条边的断开都会导致图中联通分量发生变化
1.3 寻找桥
- 设置两个数组，Order和Low，并将已访问过的顶点置为绿色
- Order表示当前顶点遍历的顺序
- Low表示当前顶点能访问到的顶点的最小值
- 递归遍历，给0-1-3-2顶点依次标上Order和Low，并且将已访问过的顶点置为绿色，如下图
- 在顶点2时，所有连接的顶点都已被访问，并且可以访问到的最小顶点为0，故将Low[2]置为0，并且将顶点置为绿色
- 回退到顶点3，将Low[3]的值置为min(Low(2)，Low(0))
- 访问顶点3的另一个连接的顶点5，并依次给5-4-6标上Order和Low，并且将已访问过的顶点置为绿色，如下图
- 到达顶点6时，其连接的顶点都被遍历过，此时将Low[6]置为min(Low(5)，Low(4))，并将节点置为绿色
- 回退到顶点4，其连接的顶点都被遍历过，此时将Low[4]置为min(Low(5)，Low(6))
- 回退到顶点5，此时的Low[5]>Order[3]，即顶点5无法访问到顶点3的祖先顶点的，故顶点3-顶点5是一条桥，如下图
- 重新复习下Order和Low的定义
- Order表示当前顶点遍历的顺序
- Low表示当前顶点能访问到的顶点的最小值
- 依次回退到顶点3-1，到达顶点1时，其连接的顶点都被遍历过，此时将Low[1]置为min(Low(3)，Low(0))
至此，查找完成，在图中有且存在一条桥(顶点3-顶点5)，整个过程的动图如下
1.4 代码实现
边的实体类
/**
* @Author: huangyibo
* @Date: 2022/4/25 0:23
* @Description: 边的实体类
*/
public class Edge {
private int v;
private int 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.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.TreeSet;
/**
* @Author: huangyibo
* @Date: 2022/3/28 1:02
* @Description: 领接表, 目前只支持无向无权图
*/
public class Graph {
//顶点个数
private int V;
//边的条数
private int E;
//领接表的底层存储结构
private TreeSet<Integer>[] adj;
public Graph(String filename){
File file = new File(filename);
try {
Scanner scanner = new Scanner(file);
V = scanner.nextInt();
if(V < 0){
throw new IllegalArgumentException("V must be non-negative");
}
adj = new TreeSet[V];
//初始化领接表
for (int i = 0; i < V; i++) {
adj[i] = new TreeSet<>();
}
E = scanner.nextInt();
if(E < 0){
throw new IllegalArgumentException("E must be non-negative");
}
for (int i = 0; i < E; i++) {
int a = scanner.nextInt();
//校验顶点a是否合法
validateVertex(a);
int b = scanner.nextInt();
//校验顶点b是否合法
validateVertex(b);
//校验是否是自环边
if(a == b){
throw new IllegalArgumentException("Self Loop is Detected!");
}
//校验是否是平行边
if(adj[a].contains(b)){
throw new IllegalArgumentException("Parallel Edges are Detected!");
}
adj[a].add(b);
adj[b].add(a);
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
/**
* 校验顶点是否合法
* @param v
*/
public void validateVertex(int v){
if(v < 0 || v >= V){
throw new IllegalArgumentException("vertex " + v + " is invalid");
}
}
/**
* 获取顶点个数
* @return
*/
public int V(){
return V;
}
/**
* 获取边的条数
* @return
*/
public int E(){
return E;
}
/**
* 图中是否存在v到w的边
* @param v
* @param w
* @return
*/
public boolean hasEdge(int v, int w){
//校验顶点v是否合法
validateVertex(v);
//校验顶点w是否合法
validateVertex(w);
return adj[v].contains(w);
}
/**
* 返回和v相邻的顶点
* @param v
* @return
*/
public Iterable<Integer> adj(int v){
//校验顶点v是否合法
validateVertex(v);
return adj[v];
}
/**
* 返回顶点v的度
* 顶点v的度（Degree）是指在图中与v相关联的边的条数
* @param v
* @return
*/
public int degree(int v){
//校验顶点v是否合法
validateVertex(v);
return adj[v].size();
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(String.format("V = %d, E = %d\n", V, E));
for (int v = 0; v < V; v++) {
sb.append(String.format("%d : ", v));
for (Integer w : adj[v]) {
sb.append(String.format("%d ", w));
}
sb.append("\n");
}
return sb.toString();
}
public static void main(String[] args) {
Graph adjSet = new Graph("src/main/resources/g.txt");
System.out.println(adjSet);
}
}
寻找桥的算法
import com.yibo.graph.Graph;
import java.util.ArrayList;
import java.util.List;
/**
* @Author: huangyibo
* @Date: 2022/4/25 0:24
* @Description: 寻找桥的算法
*/
public class FindBridges {
private Graph G;
/**
* 图的顶点是否已经被遍历过
*/
private boolean[] visited;
/**
* 表示当前顶点遍历的顺序
*/
private int ord[];
/**
* 表示当前顶点能访问到的顶点的最小值
*/
private int low[];
/**
* 遍历节点的顺序变量，从0开始
*/
private int cnt;
private List<Edge> res;
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);
}
/**
* 图的深度优先遍历
* @param v 当前顶点
* @param parent 当前顶点的父顶点
*/
private void dfs(int v, int parent){
//标识当前顶点为已遍历
visited[v] = true;
//当前顶点的遍历顺序
ord[v] = cnt;
//当前顶点能访问到的顶点的最小值, 节点遍历初始值为遍历顺序
low[v] = ord[v];
//遍历顺序自增, 用于下一节点的遍历顺序
cnt ++;
for(int w: G.adj(v))
//如果节点没有被遍历过
if(!visited[w]){
//递归调用
dfs(w, v);
//当前顶点能访问到的顶点的最小值
low[v] = Math.min(low[v], low[w]);
//如果当前顶点能访问到的顶点的最小值大于父节点的遍历顺序值
if(low[w] > ord[v]){
//说明这两个顶点之间就是桥
res.add(new Edge(v, w));
}
} else if(w != parent){
//当前顶点能访问到的顶点的最小值
low[v] = Math.min(low[v], low[w]);
}
}
/**
* 获取桥的集合
* @return
*/
public List<Edge> result(){
return res;
}
public static void main(String[] args){
Graph g = new Graph("src/main/resources/bridge/g.txt");
FindBridges fb = new FindBridges(g);
System.out.println("Bridges in g : " + fb.result());
Graph g2 = new Graph("src/main/resources/bridge/g2.txt");
FindBridges fb2 = new FindBridges(g2);
System.out.println("Bridges in g2 : " + fb2.result());
Graph g3 = new Graph("src/main/resources/bridge/g3.txt");
FindBridges fb3 = new FindBridges(g3);
System.out.println("Bridges in g3 : " + fb3.result());
Graph tree = new Graph("src/main/resources/bridge/tree.txt");
FindBridges fb_tree = new FindBridges(tree);
System.out.println("Bridges in tree : " + fb_tree.result());
}
}
g.txt
7 8
0 1
0 2
1 3
2 3
3 5
4 5
4 6
5 6
g2.txt
12 16
0 1
0 2
1 3
2 3
3 5
4 5
4 6
4 7
5 6
6 8
8 9
8 10
8 11
9 10
9 11
10 11
g3.txt
4 5
0 1
0 2
1 2
1 3
2 3
tree.txt
7 6
0 1
0 3
1 6
2 3
2 5
3 4
注意：
查找桥使用了深度优先遍历(DFS)，不能!使用广度优先遍历(BFS)
二、割点
2.1 定义
对于无向图，如果删除了一个顶点(顶点邻边也删除)，整个图的联通分量数量改变，则称这个顶点为割点，如下图，顶点3和顶点5就是该图的两个割点
2.2 性质
与桥的性质类似
- 一个图可以有多个割点
- 桥两边的点不一定是割点,如一棵树
- 一棵树不是每一个点都是割点(一棵树的每一条边都是桥)
2.3 查找割点
注意：以下描述中，分为顶点和节点，顶点为图中的每一个顶点，节点为遍历树中的每一个节点
同寻找桥一致，给各个顶点标记上Order和Low(详情请参照文章前部的寻找桥)
遍历树中，假设节点v有一个孩子节点w，满足Low[w]>=Order[v]，则v是割点
分析:
- 如果孩子节点w最小能到达的节点就是它的父节点v，那么如果断开节点v，则w无法再访问到小于v的任何节点，所以该理论成立
- 根节点
- 在图中绝对不包含比根节点小的节点，所以上述的判断方式不适用于根节点
- 对于根节点，如果有一个以上的孩子节点，则这个根节点是割点，如下图
2.4 代码实现
import com.yibo.graph.Graph;
import java.util.HashSet;
import java.util.Set;
/**
* @Author: huangyibo
* @Date: 2022/4/28 0:20
* @Description: 寻找割点的算法
*/
public class FindCutPoints {
private Graph G;
/**
* 图的顶点是否已经被遍历过
*/
private boolean[] visited;
/**
* 表示当前顶点遍历的顺序
*/
private int ord[];
/**
* 表示当前顶点能访问到的顶点的最小值
*/
private int low[];
/**
* 遍历节点的顺序变量，从0开始
*/
private int cnt;
private Set<Integer> res;
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);
}
/**
* 图的深度优先遍历
* @param v 当前顶点
* @param parent 当前顶点的父顶点
*/
private void dfs(int v, int parent){
//标识当前顶点为已遍历
visited[v] = true;
//当前顶点的遍历顺序
ord[v] = cnt;
//当前顶点能访问到的顶点的最小值, 节点遍历初始值为遍历顺序
low[v] = ord[v];
//遍历顺序自增, 用于下一节点的遍历顺序
cnt ++;
//根节点的孩子节点
int child = 0;
for(int w: G.adj(v))
//如果节点没有被遍历过
if(!visited[w]){
//递归调用
dfs(w, v);
//当前顶点能访问到的顶点的最小值
low[v] = Math.min(low[v], low[w]);
//v不是根节点
//且当前顶点能访问到的顶点的最小值大于等于父节点的遍历顺序值
if(v != parent && low[w] >= ord[v]){
//说明顶点v就是割点
res.add(v);
}
child ++;
//如果v是根节点, 并且其孩子节点大于1
if(v == parent && child > 1){
//说明根节点v就是割点
res.add(v);
}
} else if(w != parent){
//当前顶点能访问到的顶点的最小值
low[v] = Math.min(low[v], low[w]);
}
}
/**
* 获取割点的集合
* @return
*/
public Set<Integer> result(){
return res;
}
public static void main(String[] args){
Graph g = new Graph("src/main/resources/cutpoint/g.txt");
FindCutPoints fcp = new FindCutPoints(g);
System.out.println("CutPoints in g : " + fcp.result());
Graph g2 = new Graph("src/main/resources/cutpoint/g2.txt");
FindCutPoints fcp2 = new FindCutPoints(g2);
System.out.println("CutPoints in g2 : " + fcp2.result());
Graph g3 = new Graph("src/main/resources/cutpoint/g3.txt");
FindCutPoints fcp3 = new FindCutPoints(g3);
System.out.println("CutPoints in g3 : " + fcp3.result());
Graph tree = new Graph("src/main/resources/cutpoint/tree.txt");
FindCutPoints fcp_tree = new FindCutPoints(tree);
System.out.println("CutPoints in tree : " + fcp_tree.result());
}
}
参考：
https://blog.csdn.net/z13192905903/article/details/103304766
网友评论