public class DepthFirstSearch extends Object
DepthFirstSearch
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, see
DepthFirstPaths
and BreadthFirstPaths
.
This implementation uses depth-first search.
See 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 |
---|
DepthFirstSearch(Graph G,
int s)
Computes the vertices in graph
G that are
connected to the source vertex s . |
Modifier and Type | Method and Description |
---|---|
int |
count()
Returns the number of vertices connected to the source vertex
s . |
static void |
main(String[] args)
Unit tests the
DepthFirstSearch data type. |
boolean |
marked(int v)
Is there a path between the source vertex
s and vertex v ? |
public DepthFirstSearch(Graph G, int s)
G
that are
connected to the source vertex s
.G
- the graphs
- the source vertexIllegalArgumentException
- unless 0 <= s < V
public boolean marked(int v)
s
and vertex v
?v
- the vertextrue
if there is a path, false
otherwiseIllegalArgumentException
- unless 0 <= v < V
public int count()
s
.s
public static void main(String[] args)
DepthFirstSearch
data type.args
- the command-line arguments