public class DepthFirstDirectedPaths extends Object
DepthFirstDirectedPaths
class represents a data type for
finding directed paths from a source vertex s to every
other vertex in the digraph.
This implementation uses depth-first 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.
Constructor and Description |
---|
DepthFirstDirectedPaths(Digraph G,
int s)
Computes a directed path from
s to every other vertex in digraph G . |
Modifier and Type | Method and Description |
---|---|
boolean |
hasPathTo(int v)
Is there a directed path from the source vertex
s to vertex v ? |
static void |
main(String[] args)
Unit tests the
DepthFirstDirectedPaths data type. |
Iterable<Integer> |
pathTo(int v)
Returns a directed path from the source vertex
s to vertex v , or
null if no such path. |
public DepthFirstDirectedPaths(Digraph G, int s)
s
to every other vertex in digraph G
.G
- the digraphs
- the source vertexIllegalArgumentException
- unless 0 <= s < V
public boolean hasPathTo(int v)
s
to vertex v
?v
- the vertextrue
if there is a directed path from the source
vertex s
to vertex v
, false
otherwiseIllegalArgumentException
- unless 0 <= v < V
public Iterable<Integer> pathTo(int v)
s
to vertex v
, or
null
if no such path.v
- the vertexs
to vertex v
, as an IterableIllegalArgumentException
- unless 0 <= v < V
public static void main(String[] args)
DepthFirstDirectedPaths
data type.args
- the command-line arguments