Package edu.princeton.cs.algs4
Class DepthFirstSearch
 Object

 edu.princeton.cs.algs4.DepthFirstSearch

public class DepthFirstSearch extends Object
TheDepthFirstSearch
class represents a data type for determining the vertices connected to a given source vertex s in an undirected graph. For versions that find the paths, seeDepthFirstPaths
andBreadthFirstPaths
.This implementation uses depthfirst search. See
NonrecursiveDFS
for a nonrecursive version. The constructor takes Θ(V + E) time in the worst case, where V is the number of vertices and E is the number of edges. Each instance method takes Θ(1) time. It uses Θ(V) extra space (not including the graph).For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 Author:
 Robert Sedgewick, Kevin Wayne


Constructor Summary
Constructors Constructor Description DepthFirstSearch(Graph G, int s)
Computes the vertices in graphG
that are connected to the source vertexs
.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description int
count()
Returns the number of vertices connected to the source vertexs
.static void
main(String[] args)
Unit tests theDepthFirstSearch
data type.boolean
marked(int v)
Is there a path between the source vertexs
and vertexv
?



Constructor Detail

DepthFirstSearch
public DepthFirstSearch(Graph G, int s)
Computes the vertices in graphG
that are connected to the source vertexs
. Parameters:
G
 the graphs
 the source vertex Throws:
IllegalArgumentException
 unless0 <= s < V


Method Detail

marked
public boolean marked(int v)
Is there a path between the source vertexs
and vertexv
? Parameters:
v
 the vertex Returns:
true
if there is a path,false
otherwise Throws:
IllegalArgumentException
 unless0 <= v < V

count
public int count()
Returns the number of vertices connected to the source vertexs
. Returns:
 the number of vertices connected to the source vertex
s

main
public static void main(String[] args)
Unit tests theDepthFirstSearch
data type. Parameters:
args
 the commandline arguments

