public class NonrecursiveDFS extends Object
NonrecursiveDFS
class represents a data type for finding
the vertices connected to a source vertex s in the undirected
graph.
This implementation uses a nonrecursive version of depth-first search
with an explicit stack.
See DepthFirstSearch
for the classic 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.
The marked(int)
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 |
---|
NonrecursiveDFS(Graph G,
int s)
Computes the vertices connected to the source vertex
s in the graph G . |
Modifier and Type | Method and Description |
---|---|
static void |
main(String[] args)
Unit tests the
NonrecursiveDFS data type. |
boolean |
marked(int v)
Is vertex
v connected to the source vertex s ? |
public NonrecursiveDFS(Graph G, int s)
s
in the graph G
.G
- the graphs
- the source vertexIllegalArgumentException
- unless 0 <= s < V
public boolean marked(int v)
v
connected to the source vertex s
?v
- the vertextrue
if vertex v
is connected to the source vertex s
,
and false
otherwiseIllegalArgumentException
- unless 0 <= v < V
public static void main(String[] args)
NonrecursiveDFS
data type.args
- the command-line arguments