public class DepthFirstSearch extends Object
DepthFirstSearchclass 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, see
This implementation uses depth-first search.
NonrecursiveDFS for a non-recursive 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.
|Constructor and Description|
Computes the vertices in graph
|Modifier and Type||Method and Description|
Returns the number of vertices connected to the source vertex
Unit tests the
Is there a path between the source vertex
public DepthFirstSearch(Graph G, int s)
Gthat are connected to the source vertex
G- the graph
s- the source vertex
0 <= s < V
public boolean marked(int v)
v- the vertex
trueif there is a path,
0 <= v < V
public int count()
public static void main(String args)
args- the command-line arguments