public class BreadthFirstDirectedPaths extends java.lang.Object
This implementation uses breadth-first search. The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges.
For additional documentation, see Section 4.1 of Algorithms, 4th Edition, by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
BreadthFirstDirectedPaths(Digraph G,
int s)
Computes the shortest path from s and every other vertex in graph G.
|
BreadthFirstDirectedPaths(Digraph G,
java.lang.Iterable<java.lang.Integer> sources)
Computes the shortest path from any one of the source vertices in sources
to every other vertex in graph G.
|
Modifier and Type | Method and Description |
---|---|
int |
distTo(int v)
Returns the number of edges in a shortest path from the source s
(or sources) to vertex v?
|
boolean |
hasPathTo(int v)
Is there a directed path from the source s (or sources) to vertex v?
|
static void |
main(java.lang.String[] args)
Unit tests the BreadthFirstDirectedPaths data type.
|
java.lang.Iterable<java.lang.Integer> |
pathTo(int v)
Returns a shortest path from s (or sources) to v, or
null if no such path.
|
public BreadthFirstDirectedPaths(Digraph G, int s)
G
- the digraphs
- the source vertexpublic BreadthFirstDirectedPaths(Digraph G, java.lang.Iterable<java.lang.Integer> sources)
G
- the digraphsources
- the source verticespublic boolean hasPathTo(int v)
v
- the vertexpublic int distTo(int v)
v
- the vertexpublic java.lang.Iterable<java.lang.Integer> pathTo(int v)
v
- the vertexpublic static void main(java.lang.String[] args)