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 depthfirst 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 commandline arguments