001package algs41; 002import stdlib.*; 003import algs13.Queue; 004/* *********************************************************************** 005 * Compilation: javac CC.java 006 * Execution: java CC filename.txt 007 * Dependencies: Graph.java StdOut.java Queue.java 008 * Data files: http://algs4.cs.princeton.edu/41undirected/tinyG.txt 009 * 010 * Compute connected components using depth first search. 011 * Runs in O(E + V) time. 012 * 013 * % java CC tinyG.txt 014 * 3 components 015 * 0 1 2 3 4 5 6 016 * 7 8 017 * 9 10 11 12 018 * 019 *************************************************************************/ 020 021public class CC { 022 private final boolean[] marked; // marked[v] = has vertex v been marked? 023 private final int[] id; // id[v] = id of connected component containing v 024 private final int[] size; // size[id] = number of vertices in component containing v 025 private int count; // number of connected components 026 027 public CC(Graph G) { 028 marked = new boolean[G.V()]; 029 id = new int[G.V()]; 030 size = new int[G.V()]; 031 for (int v = 0; v < G.V(); v++) { 032 if (!marked[v]) { 033 dfs(G, v); 034 count++; 035 } 036 } 037 } 038 039 // depth first search 040 private void dfs(Graph G, int v) { 041 marked[v] = true; 042 id[v] = count; 043 size[count]++; 044 for (int w : G.adj(v)) { 045 if (!marked[w]) { 046 dfs(G, w); 047 } 048 } 049 } 050 051 // id of connected component containing v 052 public int id(int v) { 053 return id[v]; 054 } 055 056 // size of connected component containing v 057 public int size(int v) { 058 return size[id[v]]; 059 } 060 061 // number of connected components 062 public int count() { 063 return count; 064 } 065 066 // are v and w in the same connected component? 067 public boolean areConnected(int v, int w) { 068 return id(v) == id(w); 069 } 070 071 072 // test client 073 public static void anotherTest() { 074 Graph G; 075 do { 076 G = GraphGenerator.simple(20,40); 077 } while (new CC(G).count() != 1); 078 G.toGraphviz ("g.png"); 079 } 080 public static void main(String[] args) { 081 anotherTest(); 082// args = new String [] { "10", "5" }; 083// final int V = Integer.parseInt(args[0]); 084// final int E = Integer.parseInt(args[1]); 085// final Graph G = GraphGenerator.simple(V, E); 086// StdOut.println(G); 087 088 //args = new String [] { "data/tinyAG.txt" }; 089 args = new String [] { "data/tinyG.txt" }; 090 In in = new In(args[0]); 091 Graph G = GraphGenerator.fromIn (in); 092 StdOut.println(G); 093 G.toGraphviz ("g"); 094 095 CC cc = new CC(G); 096 097 // number of connected components 098 int M = cc.count(); 099 StdOut.println(M + " components"); 100 101 // compute list of vertices in each connected component 102 @SuppressWarnings("unchecked") 103 Queue<Integer>[] components = new Queue[M]; 104 for (int i = 0; i < M; i++) { 105 components[i] = new Queue<>(); 106 } 107 for (int v = 0; v < G.V(); v++) { 108 components[cc.id(v)].enqueue(v); 109 } 110 111 // print results 112 for (int i = 0; i < M; i++) { 113 for (int v : components[i]) { 114 StdOut.print(v + " "); 115 } 116 StdOut.println(); 117 } 118 } 119}