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.
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