Breadth-First Search (BFS)

The breadth-first search (BFS) algorithm is implemented to traverse the graph and find the shortest path between vertices. The BFS algorithm is intented to be used on unweighted graphs.

For unweighted graphs, the distance between two vertices is defined as the number of edges in the shortest path connecting them.

All BFS functions are convenience wrappers built on top of pygraphs.bfs().

bfs(graph, start, *[, max_distance, ...])	[core function] Perform a breadth-first search (BFS) to compute the shortest path distances from a starting vertex to all other vertices in a unweighted graph, and to keep track of the parent vertices for each visited vertex.
bfs_distances(graph, start, *[, ...])	Compute shortest path distances from a source vertex to all reachable vertices using BFS.
bfs_shortest_path(graph, start, end, *[, ...])	Compute the shortest path from a starting vertex to an ending vertex.
bfs_shortest_distance(graph, start, end, *)	Compute the shortest distance from a starting vertex to an ending vertex.
bfs_is_reachable(graph, start, end, *[, ...])	Check if a vertex is reachable from a starting vertex.
bfs_matrix(graph, *[, max_distance, _skip_check])	Compute the shortest path distance matrix for all pairs of vertices.
bfs_reachable(graph, start, *[, ...])	Extract the vertices that are reachable from a starting vertex.
bfs_components(graph, *[, ...])	Extract the connected components (or strongly connected components if strongly_connected=True) of the graph.
bfs_k_annulus(graph, start, inner_distance, ...)	Return all vertices with distance in \([k_1, k_2]\) (ie \(\{v \in V | \text{dist}(i, v) \in [k_1, k_2]\}\)) where \(k_1\) and \(k_2\) are the specified inner and outer distances.
bfs_k_disk(graph, start, distance, *[, ...])	Return all vertices with distance lower than \(k\) (ie \(\{v \in V | \text{dist}(i, v) \leq k\}\)) where \(k\) is the specified distance.
bfs_k_ring(graph, start, distance, *[, ...])	Return all vertices with distance equal to \(k\) (ie \(\{v \in V | \text{dist}(i, v) = k\}\)) where \(k\) is the specified distance.