public class NonrecursiveDirectedDFS extends Object
NonrecursiveDirectedDFS
class represents a data type for finding
the vertices reachable from a source vertex s in the digraph.
This implementation uses a nonrecursive version of depth-first search with an explicit stack. 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 digraph).
For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
NonrecursiveDirectedDFS(Digraph G,
int s)
Computes the vertices reachable from the source vertex
s in the digraph G . |
Modifier and Type | Method and Description |
---|---|
static void |
main(String[] args)
Unit tests the
NonrecursiveDirectedDFS data type. |
boolean |
marked(int v)
Is vertex
v reachable from the source vertex s ? |
public NonrecursiveDirectedDFS(Digraph G, int s)
s
in the digraph G
.G
- the digraphs
- the source vertexIllegalArgumentException
- unless 0 <= s < V
public boolean marked(int v)
v
reachable from the source vertex s
?v
- the vertextrue
if vertex v
is reachable from the source vertex s
,
and false
otherwiseIllegalArgumentException
- unless 0 <= v < V
public static void main(String[] args)
NonrecursiveDirectedDFS
data type.args
- the command-line arguments