桥和割点，以及图的遍历树

本文主要是介绍桥和割点，以及图的遍历树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

什么是桥

寻找桥的算法

代码实现

什么是割点

​寻找割点的算法

         代码实现

---

什么是桥

寻找桥的算法

 

 

代码实现

import java.util.ArrayList;public class FindBridges {private Graph G;private boolean[] visited;private int ord[];private int low[];private int cnt;private ArrayList<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);}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]);}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("Bridges in g : " + fb.result());Graph g2 = new Graph("g2.txt");FindBridges fb2 = new FindBridges(g2);System.out.println("Bridges in g2 : " + fb2.result());Graph g3 = new Graph("g3.txt");FindBridges fb3 = new FindBridges(g3);System.out.println("Bridges in g3 : " + fb3.result());Graph tree = new Graph("tree.txt");FindBridges fb_tree = new FindBridges(tree);System.out.println("Bridges in tree : " + fb_tree.result());}
}

什么是割点

寻找割点的算法

孩子的数量是根据树来说的，而不是看根节点有多少个邻边，遍历树不同孩子数量也不同。

代码实现

import java.util.HashSet;public class FindCutPoints {private Graph G;private boolean[] visited;private int[] ord;private int[] low;private int cnt;private HashSet<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);}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]);if(v != parent && low[w] >= ord[v])res.add(v);child ++;if(v == parent && child > 1)res.add(v);}else if(w != parent)low[v] = Math.min(low[v], ord[w]);}public HashSet<Integer> result(){return res;}public static void main(String[] args){Graph g = new Graph("g.txt");FindCutPoints fc = new FindCutPoints(g);System.out.println("Cut Points in g : " + fc.result());Graph g2 = new Graph("g2.txt");FindCutPoints fc2 = new FindCutPoints(g2);System.out.println("Cut Points in g2 : " + fc2.result());Graph g3 = new Graph("g3.txt");FindCutPoints fc3 = new FindCutPoints(g3);System.out.println("Cut Points in g3 : " + fc3.result());Graph tree = new Graph("tree.txt");FindCutPoints fc4 = new FindCutPoints(tree);System.out.println("Cut Points in tree : " + fc4.result());}
}

这篇关于桥和割点，以及图的遍历树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---