Package edu.princeton.cs.algs4
Class DirectedDFS
 Object

 edu.princeton.cs.algs4.DirectedDFS

public class DirectedDFS extends Object
TheDirectedDFS
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, seeDepthFirstDirectedPaths
andBreadthFirstDirectedPaths
.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.
 Author:
 Robert Sedgewick, Kevin Wayne


Constructor Summary
Constructors Constructor Description DirectedDFS(Digraph G, int s)
Computes the vertices in digraphG
that are reachable from the source vertexs
.DirectedDFS(Digraph G, Iterable<Integer> sources)
Computes the vertices in digraphG
that are connected to any of the source verticessources
.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description int
count()
Returns the number of vertices reachable from the source vertex (or source vertices).static void
main(String[] args)
Unit tests theDirectedDFS
data type.boolean
marked(int v)
Is there a directed path from the source vertex (or any of the source vertices) and vertexv
?



Constructor Detail

DirectedDFS
public DirectedDFS(Digraph G, int s)
Computes the vertices in digraphG
that are reachable from the source vertexs
. Parameters:
G
 the digraphs
 the source vertex Throws:
IllegalArgumentException
 unless0 <= s < V

DirectedDFS
public DirectedDFS(Digraph G, Iterable<Integer> sources)
Computes the vertices in digraphG
that are connected to any of the source verticessources
. Parameters:
G
 the graphsources
 the source vertices Throws:
IllegalArgumentException
 ifsources
isnull
IllegalArgumentException
 ifsources
contains no verticesIllegalArgumentException
 unless0 <= s < V
for each vertexs
insources


Method Detail

marked
public boolean marked(int v)
Is there a directed path from the source vertex (or any of the source vertices) and vertexv
? Parameters:
v
 the vertex Returns:
true
if there is a directed path,false
otherwise Throws:
IllegalArgumentException
 unless0 <= v < V

count
public int count()
Returns the number of vertices reachable from the source vertex (or source vertices). Returns:
 the number of vertices reachable from the source vertex (or source vertices)

main
public static void main(String[] args)
Unit tests theDirectedDFS
data type. Parameters:
args
 the commandline arguments

