一、桥
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 = 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(" arallel Edges are Detected!"); } adj[a].add(b); adj.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 80 10 21 32 33 54 54 65 6g2.txt
12 160 10 21 32 33 54 54 64 75 66 88 98 108 119 109 1110 11g3.txt
4 50 10 21 21 32 3tree.txt
7 60 10 31 62 32 53 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
https://www.cnblogs.com/ukcxrtjr/p/11194221.html |
