Created
July 26, 2018 17:53
Star
You must be signed in to star a gist
Depth First Search on an Undirected Graph
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class DepthFirstSearch | |
{ | |
private boolean[] marked; // marked[v] = is there an s-v path? | |
private int count; // number of vertices connected to s | |
public DepthFirstSearch( Graph G, int s ) | |
{ | |
marked = new boolean[ G.V() ]; | |
validateVertex( s ); | |
dfs( G, s ); | |
} | |
private void dfs( Graph G, int v ) | |
{ | |
count++; | |
marked[ v ] = true; | |
for ( int w : G.adj( v ) ) | |
{ | |
if ( !marked[ w ] ) | |
{ | |
dfs( G, w ); | |
} | |
} | |
} | |
public boolean marked( int v ) | |
{ | |
validateVertex( v ); | |
return marked[ v ]; | |
} | |
public int count() | |
{ return count; } | |
private void validateVertex( int v ) | |
{ | |
int V = marked.length; | |
if ( v < 0 || v >= V ) | |
throw new IllegalArgumentException( "vertex " + v + " is not between 0 and " + ( V - 1 ) ); | |
} | |
public static void main( String[] args ) | |
{ | |
In in = new In( args[ 0 ] ); | |
Graph G = new Graph( in ); | |
int s = Integer.parseInt( args[ 1 ] ); | |
DepthFirstSearch search = new DepthFirstSearch( G, s ); | |
for ( int v = 0; v < G.V(); v++ ) | |
{ | |
if ( search.marked( v ) ) | |
StdOut.print( v + " " ); | |
} | |
StdOut.println(); | |
if ( search.count() != G.V() ) StdOut.println( "NOT connected" ); | |
else StdOut.println( "connected" ); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment