• Object

• ```public class BreadthFirstPaths
extends Object```
The `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.

Author:
Robert Sedgewick, Kevin Wayne
• Constructor Summary

Constructors
Constructor 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`.
• Method Summary

All Methods
Modifier and Type Method 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.
• Methods inherited from class java.lang.Object

`clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• Constructor Detail

```public BreadthFirstPaths​(Graph G,
int s)```
Computes the shortest path between the source vertex `s` and every other vertex in the graph `G`.
Parameters:
`G` - the graph
`s` - the source vertex
Throws:
`IllegalArgumentException` - unless `0 <= s < V`

```public 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`.
Parameters:
`G` - the graph
`sources` - the source vertices
Throws:
`IllegalArgumentException` - if `sources` is `null`
`IllegalArgumentException` - if `sources` contains no vertices
`IllegalArgumentException` - unless `0 <= s < V` for each vertex `s` in `sources`
• Method Detail

• hasPathTo

`public boolean hasPathTo​(int v)`
Is there a path between the source vertex `s` (or sources) and vertex `v`?
Parameters:
`v` - the vertex
Returns:
`true` if there is a path, and `false` otherwise
Throws:
`IllegalArgumentException` - unless `0 <= v < V`
• distTo

`public int distTo​(int v)`
Returns the number of edges in a shortest path between the source vertex `s` (or sources) and vertex `v`?
Parameters:
`v` - the vertex
Returns:
the number of edges in such a shortest path (or `Integer.MAX_VALUE` if there is no such path)
Throws:
`IllegalArgumentException` - unless `0 <= v < V`
• pathTo

`public Iterable<Integer> pathTo​(int v)`
Returns a shortest path between the source vertex `s` (or sources) and `v`, or `null` if no such path.
Parameters:
`v` - the vertex
Returns:
the sequence of vertices on a shortest path, as an Iterable
Throws:
`IllegalArgumentException` - unless `0 <= v < V`
• main

`public static void main​(String[] args)`
Unit tests the `BreadthFirstPaths` data type.
Parameters:
`args` - the command-line arguments