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}