001package algs41; 002import stdlib.*; 003/* *********************************************************************** 004 * Compilation: javac Biconnected.java 005 * Dependencies: Graph.java 006 * 007 * Identify articulation points and print them out. 008 * This can be used to decompose a graph into biconnected components. 009 * Runs in O(E + V) time. 010 * 011 * http://www.cs.brown.edu/courses/cs016/book/slides/Connectivity2x2.pdf 012 * 013 *************************************************************************/ 014 015public class XBiconnected { 016 private final int[] low; 017 private final int[] pre; 018 private int cnt; 019 // private int bridges; 020 private final boolean[] articulation; 021 022 public XBiconnected(Graph G) { 023 low = new int[G.V()]; 024 pre = new int[G.V()]; 025 articulation = new boolean[G.V()]; 026 for (int v = 0; v < G.V(); v++) low[v] = -1; 027 for (int v = 0; v < G.V(); v++) pre[v] = -1; 028 029 for (int v = 0; v < G.V(); v++) 030 if (pre[v] == -1) 031 dfs(G, v, v); 032 } 033 034 private void dfs(Graph G, int u, int v) { 035 int children = 0; 036 pre[v] = cnt++; 037 low[v] = pre[v]; 038 for (int w : G.adj(v)) { 039 if (pre[w] == -1) { 040 children++; 041 dfs(G, v, w); 042 043 // update low number 044 low[v] = Math.min(low[v], low[w]); 045 046 // non-root of DFS is an articulation point if low[w] >= pre[v] 047 if (low[w] >= pre[v] && u != v) 048 articulation[v] = true; 049 } 050 051 // update low number - ignore reverse of edge leading to v 052 else if (w != u) 053 low[v] = Math.min(low[v], pre[w]); 054 } 055 056 // root of DFS is an articulation point if it has more than 1 child 057 if (u == v && children > 1) 058 articulation[v] = true; 059 } 060 061 // is vertex v an articulation point? 062 public boolean isArticulation(int v) { return articulation[v]; } 063 064 // test client 065 public static void main(String[] args) { 066 args = new String [] { "6", "6" }; 067 int V = Integer.parseInt(args[0]); 068 int E = Integer.parseInt(args[1]); 069 Graph G = GraphGenerator.simple(V, E); 070 G.toGraphviz ("g"); 071 StdOut.println(G); 072 073 XBiconnected bic = new XBiconnected(G); 074 075 // print out articulation points 076 StdOut.println(); 077 StdOut.println("Articulation points"); 078 StdOut.println("-------------------"); 079 for (int v = 0; v < G.V(); v++) 080 if (bic.isArticulation(v)) StdOut.println(v); 081 } 082 083 084} 085