Package edu.princeton.cs.algs4
Class BreadthFirstPaths
 Object

 edu.princeton.cs.algs4.BreadthFirstPaths

public class BreadthFirstPaths extends Object
TheBreadthFirstPaths
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 breadthfirst 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 vertexs
and every other vertex in the graphG
.BreadthFirstPaths(Graph G, Iterable<Integer> sources)
Computes the shortest path between any one of the source vertices insources
and every other vertex in graphG
.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description int
distTo(int v)
Returns the number of edges in a shortest path between the source vertexs
(or sources) and vertexv
?boolean
hasPathTo(int v)
Is there a path between the source vertexs
(or sources) and vertexv
?static void
main(String[] args)
Unit tests theBreadthFirstPaths
data type.Iterable<Integer>
pathTo(int v)
Returns a shortest path between the source vertexs
(or sources) andv
, ornull
if no such path.



Constructor Detail

BreadthFirstPaths
public BreadthFirstPaths(Graph G, int s)
Computes the shortest path between the source vertexs
and every other vertex in the graphG
. Parameters:
G
 the graphs
 the source vertex Throws:
IllegalArgumentException
 unless0 <= s < V

BreadthFirstPaths
public BreadthFirstPaths(Graph G, Iterable<Integer> sources)
Computes the shortest path between any one of the source vertices insources
and every other vertex in graphG
. Parameters:
G
 the graphsources
 the source vertices Throws:
IllegalArgumentException
 ifsources
isnull
IllegalArgumentException
 ifsources
contains no verticesIllegalArgumentException
 unless0 <= s < V
for each vertexs
insources


Method Detail

hasPathTo
public boolean hasPathTo(int v)
Is there a path between the source vertexs
(or sources) and vertexv
? Parameters:
v
 the vertex Returns:
true
if there is a path, andfalse
otherwise Throws:
IllegalArgumentException
 unless0 <= v < V

distTo
public int distTo(int v)
Returns the number of edges in a shortest path between the source vertexs
(or sources) and vertexv
? 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
 unless0 <= v < V

pathTo
public Iterable<Integer> pathTo(int v)
Returns a shortest path between the source vertexs
(or sources) andv
, ornull
if no such path. Parameters:
v
 the vertex Returns:
 the sequence of vertices on a shortest path, as an Iterable
 Throws:
IllegalArgumentException
 unless0 <= v < V

main
public static void main(String[] args)
Unit tests theBreadthFirstPaths
data type. Parameters:
args
 the commandline arguments

