BreadthFirstPaths Class |
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 time proportional to V + E, where V is the number of vertices and E is the number of edges. It uses extra space (not including the graph) proportional to V.
Namespace: Algs4Net
public class BreadthFirstPaths
The BreadthFirstPaths type exposes the following members.
Name | Description | |
---|---|---|
BreadthFirstPaths(Graph, IEnumerableInt32) |
Computes the shortest path between any one of the source vertices in sources
and every other vertex in graph G. | |
BreadthFirstPaths(Graph, Int32) |
Computes the shortest path between the source vertex s |
Name | Description | |
---|---|---|
DistTo |
Returns the number of edges in a shortest path between the source vertex s
(or sources) and vertex v? | |
HasPathTo |
Is there a path between the source vertex s (or sources) and vertex v? | |
MainTest |
Demo test the BreadthFirstPaths data type. | |
PathTo |
Returns a shortest path between the source vertex s (or sources)
and v, or null if no such path. |
For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
This class is a C# port from the original Java class BreadthFirstPaths implementation by the respective authors.