public class BreadthFirstPaths extends Object
BreadthFirstPaths
class represents a data type for finding
shortest paths (number of edges) from a source vertex s
(or a set of source vertices)
to every other vertex in an undirected graph.
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.
Each call to distTo(int)
and 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 |
---|
BreadthFirstPaths(Graph G,
int s)
Computes the shortest path between the source vertex
s
and every other vertex in the graph G . |
BreadthFirstPaths(Graph G,
Iterable<Integer> sources)
Computes the shortest path between any one of the source vertices in
sources
and 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 between the source vertex
s
(or sources) and vertex v ? |
boolean |
hasPathTo(int v)
Is there a path between the source vertex
s (or sources) and vertex v ? |
static void |
main(String[] args)
Unit tests the
BreadthFirstPaths data type. |
Iterable<Integer> |
pathTo(int v)
Returns a shortest path between the source vertex
s (or sources)
and v , or null if no such path. |
public BreadthFirstPaths(Graph G, int s)
s
and every other vertex in the graph G
.G
- the graphs
- the source vertexIllegalArgumentException
- unless 0 <= s < V
public BreadthFirstPaths(Graph G, Iterable<Integer> sources)
sources
and every other vertex in graph G
.G
- the graphsources
- the source verticesIllegalArgumentException
- unless 0 <= s < V
for each vertex
s
in sources
public boolean hasPathTo(int v)
s
(or sources) and vertex v
?v
- the vertextrue
if there is a path, and false
otherwiseIllegalArgumentException
- unless 0 <= v < V
public int distTo(int v)
s
(or sources) and vertex v
?v
- the vertexIllegalArgumentException
- unless 0 <= v < V
public Iterable<Integer> pathTo(int v)
s
(or sources)
and v
, or null
if no such path.v
- the vertexIllegalArgumentException
- unless 0 <= v < V
public static void main(String[] args)
BreadthFirstPaths
data type.args
- the command-line arguments