public class DirectedDFS extends Object
DirectedDFS
class represents a data type for
determining the vertices reachable from a given source vertex s
(or set of source vertices) in a digraph. For versions that find the paths,
see DepthFirstDirectedPaths
and BreadthFirstDirectedPaths
.
This implementation uses depth-first search. The constructor takes time proportional to V + E (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 |
---|
DirectedDFS(Digraph G,
int s)
Computes the vertices in digraph
G that are
reachable from the source vertex s . |
DirectedDFS(Digraph G,
Iterable<Integer> sources)
Computes the vertices in digraph
G that are
connected to any of the source vertices sources . |
Modifier and Type | Method and Description |
---|---|
int |
count()
Returns the number of vertices reachable from the source vertex
(or source vertices).
|
static void |
main(String[] args)
Unit tests the
DirectedDFS data type. |
boolean |
marked(int v)
Is there a directed path from the source vertex (or any
of the source vertices) and vertex
v ? |
public DirectedDFS(Digraph G, int s)
G
that are
reachable from the source vertex s
.G
- the digraphs
- the source vertexIllegalArgumentException
- unless 0 <= s < V
public DirectedDFS(Digraph G, Iterable<Integer> sources)
G
that are
connected to any of the source vertices sources
.G
- the graphsources
- the source verticesIllegalArgumentException
- if sources
is null
IllegalArgumentException
- if sources
contains no verticesIllegalArgumentException
- unless 0 <= s < V
for each vertex s
in sources
public boolean marked(int v)
v
?v
- the vertextrue
if there is a directed path, false
otherwiseIllegalArgumentException
- unless 0 <= v < V
public int count()
public static void main(String[] args)
DirectedDFS
data type.args
- the command-line arguments