Package edu.princeton.cs.algs4
Class DepthFirstDirectedPaths
 Object

 edu.princeton.cs.algs4.DepthFirstDirectedPaths

public class DepthFirstDirectedPaths extends Object
TheDepthFirstDirectedPaths
class represents a data type for finding directed paths from a source vertex s to every other vertex in the digraph.This implementation uses depthfirst search. 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).
See
DepthFirstDirectedPaths
for a nonrecursive implementation. 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 DepthFirstDirectedPaths(Digraph G, int s)
Computes a directed path froms
to every other vertex in digraphG
.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
hasPathTo(int v)
Is there a directed path from the source vertexs
to vertexv
?static void
main(String[] args)
Unit tests theDepthFirstDirectedPaths
data type.Iterable<Integer>
pathTo(int v)
Returns a directed path from the source vertexs
to vertexv
, ornull
if no such path.



Constructor Detail

DepthFirstDirectedPaths
public DepthFirstDirectedPaths(Digraph G, int s)
Computes a directed path froms
to every other vertex in digraphG
. Parameters:
G
 the digraphs
 the source vertex Throws:
IllegalArgumentException
 unless0 <= s < V


Method Detail

hasPathTo
public boolean hasPathTo(int v)
Is there a directed path from the source vertexs
to vertexv
? Parameters:
v
 the vertex Returns:
true
if there is a directed path from the source vertexs
to vertexv
,false
otherwise Throws:
IllegalArgumentException
 unless0 <= v < V

pathTo
public Iterable<Integer> pathTo(int v)
Returns a directed path from the source vertexs
to vertexv
, ornull
if no such path. Parameters:
v
 the vertex Returns:
 the sequence of vertices on a directed path from the source vertex
s
to vertexv
, as an Iterable  Throws:
IllegalArgumentException
 unless0 <= v < V

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

