|
| 1 | +/** |
| 2 | + * Run depth first search |
| 3 | + * |
| 4 | + */ |
| 5 | +public class DepthFirstSearch { |
| 6 | + private boolean[] marked; // marked[v] = is there an s-v path? |
| 7 | + private int count; // number of vertices connected to s |
| 8 | + |
| 9 | + // Computes the vertices in graph `G` that are connected to the source vertex `s` |
| 10 | + public DepthFirstSearch(Graph G, int s) { |
| 11 | + marked = new boolean[G.V()]; |
| 12 | + validateVertex(s); |
| 13 | + dfs(G, s); |
| 14 | + } |
| 15 | + |
| 16 | + // depth first search from v |
| 17 | + private void dfs(Graph G, int v) { |
| 18 | + count++; |
| 19 | + marked[v] = true; |
| 20 | + for(int w:G.adj(v)) { |
| 21 | + if(!marked[w]) |
| 22 | + dfs(G, w); |
| 23 | + } |
| 24 | + } |
| 25 | + |
| 26 | + // Is there a path between the source vertex `s` and vertex `v`? |
| 27 | + public boolean marked(int v) { |
| 28 | + validateVertex(v); |
| 29 | + return marked[v]; |
| 30 | + } |
| 31 | + |
| 32 | + // Returns the number of vertices connected to the source vertex `s` |
| 33 | + public int count() { |
| 34 | + return count; |
| 35 | + } |
| 36 | + |
| 37 | + // throw an IllegalArgumentException unless `0 <= v < V` |
| 38 | + private void validateVertex(int v) { |
| 39 | + int V = marked.length; |
| 40 | + if(v < 0 || v >= V) |
| 41 | + throw new IllegalArgumentException("vertex " + V + "is not between 0 and " + (V - 1)); |
| 42 | + } |
| 43 | + |
| 44 | + // test |
| 45 | + public static void main(String[] args) { |
| 46 | + In in = new In(args[0]); |
| 47 | + Graph G = new Graph(in); |
| 48 | + int s = Integer.parseInt(args[1]); |
| 49 | + DepthFirstSearch search = new DepthFirstSearch(G, s); |
| 50 | + for(int v = 0; v < G.V(); v++) { |
| 51 | + if(search.marked(v)) |
| 52 | + StdOut.print(v + " "); |
| 53 | + } |
| 54 | + |
| 55 | + StdOut.println(); |
| 56 | + if(search.count() != G.V()) |
| 57 | + StdOut.println("NOT connected"); |
| 58 | + else |
| 59 | + StdOut.println("connected"); |
| 60 | + } |
| 61 | +} |
0 commit comments