public class DepthFirstPaths extends Object
DepthFirstPaths
class represents a data type for finding
paths from a source vertex s to every other vertex
in an undirected graph.
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.
It uses extra space (not including the graph) proportional to V.
For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
DepthFirstPaths(Graph G,
int s)
Computes a path between
s and every other vertex in graph G . |
Modifier and Type | Method and Description |
---|---|
boolean |
hasPathTo(int v)
Is there a path between the source vertex
s and vertex v ? |
static void |
main(String[] args)
Unit tests the
DepthFirstPaths data type. |
Iterable<Integer> |
pathTo(int v)
Returns a path between the source vertex
s and vertex v , or
null if no such path. |
public DepthFirstPaths(Graph G, int s)
s
and every other vertex in graph G
.G
- the graphs
- the source vertexIllegalArgumentException
- unless 0 <= s < V
public boolean hasPathTo(int v)
s
and vertex v
?v
- the vertextrue
if there is a path, false
otherwiseIllegalArgumentException
- unless 0 <= v < V
public Iterable<Integer> pathTo(int v)
s
and vertex v
, or
null
if no such path.v
- the vertexs
and vertex v
, as an IterableIllegalArgumentException
- unless 0 <= v < V
public static void main(String[] args)
DepthFirstPaths
data type.args
- the command-line arguments