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 time proportional to V + E,
where V is the number of vertices and E is the number of edges.
Each call to hasPathTo(int)
takes constant time;
each call to pathTo(int)
takes time proportional to the length
of the path returned.
It uses extra space (not including the graph) proportional to V.
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