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 Θ(V + E) time in the worst case, where V is the number of vertices and E is the number of edges. Each instance method takes Θ(1) time. It uses Θ(V) extra space (not including the graph).
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
- if sources
is null
IllegalArgumentException
- 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 vertexInteger.MAX_VALUE
if there is no such path)IllegalArgumentException
- 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