001package algs41; 002import stdlib.*; 003/* *********************************************************************** 004 * Compilation: javac DepthFirstSearch.java 005 * Execution: java DepthFirstSearch filename.txt s 006 * Dependencies: Graph.java StdOut.java 007 * Data files: http://algs4.cs.princeton.edu/41undirected/tinyG.txt 008 * 009 * Run depth first search on an undirected graph. 010 * Runs in O(E + V) time. 011 * 012 * % java DepthFirstSearch tinyG.txt 0 013 * 0 1 2 3 4 5 6 014 * NOT connected 015 * 016 * % java DepthFirstSearch tinyG.txt 9 017 * 9 10 11 12 018 * NOT connected 019 * 020 *************************************************************************/ 021 022public class DepthFirstSearch { 023 private final boolean[] marked; // marked[v] = is there an s-v path? 024 private int count; // number of vertices connected to s 025 026 // single source 027 public DepthFirstSearch(Graph G, int s) { 028 marked = new boolean[G.V()]; 029 dfs(G, s); 030 } 031 032 // depth first search from v 033 private void dfs(Graph G, int v) { 034 //StdOut.printf ("visited %d\n", v); 035 marked[v] = true; 036 count++; 037 for (int w : G.adj(v)) { 038 if (!marked[w]) { 039 dfs(G, w); 040 } 041 } 042 } 043 044 // using an explicit stack 045 private void dfsLoop1(Graph G, int v) { 046 algs13.Stack<Integer> s = new algs13.Stack<>(); 047 s.push (v); 048 marked[v] = true; 049 count++; 050 while (!s.isEmpty ()) { 051 v = s.pop (); 052 StdOut.printf ("visited %d\n", v); 053 for (int w : G.adj(v)) { 054 if (!marked[w]) { 055 s.push (w); 056 marked[w] = true; 057 count++; 058 } 059 } 060 } 061 } 062 063 // Use tmp stack to get nodes in same order as recursive version 064 private void dfsLoop2(Graph G, int v) { 065 algs13.Stack<Integer> s = new algs13.Stack<>(); 066 s.push (v); 067 marked[v] = true; 068 count++; 069 while (!s.isEmpty ()) { 070 v = s.pop (); 071 StdOut.printf ("visited %d\n", v); 072 algs13.Stack<Integer> tmp= new algs13.Stack<>(); 073 for (int w : G.adj(v)) { 074 if (!marked[w]) { 075 tmp.push (w); 076 marked[w] = true; 077 count++; 078 } 079 } 080 while (!tmp.isEmpty ()) { s.push (tmp.pop ());} 081 } 082 } 083 084 // is there an s-v path? 085 public boolean marked(int v) { 086 return marked[v]; 087 } 088 089 // number of vertices connected to s 090 public int count() { 091 return count; 092 } 093 094 // test client 095 public static void main(String[] args) { 096 args = new String [] { "data/tinyG.txt", "0" }; 097 //args = new String [] { "data/tinyCG.txt", "0" }; 098 099 In in = new In(args[0]); 100 Graph G = GraphGenerator.fromIn (in); 101 StdOut.println (G); 102 103 int s = Integer.parseInt(args[1]); 104 DepthFirstSearch search = new DepthFirstSearch(G, s); 105 106 StdOut.print("Marked="); 107 for (int v = 0; v < G.V(); v++) { 108 if (search.marked(v)) 109 StdOut.print(v + " "); 110 } 111 112 StdOut.println(); 113 StdOut.println("Count=" + search.count ()); 114 if (search.count() != G.V()) StdOut.println("NOT connected"); 115 else StdOut.println("connected"); 116 } 117 118}