图论（八）桥(割边)和割点

藏宝库编辑 · 2024-9-15 05:39:31

一、桥

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

图论（八）桥(割边)和割点

所属分类: 问答交流

新帖推荐: 30日

推荐作品