pygraphs.bfs_distances#

bfs_distances(graph, start, *, max_distance=None, _skip_check=False)[source]#

Compute shortest path distances from a source vertex to all reachable vertices using BFS.

Parameters:

  • graph (Graph) – An instance of the Graph class representing the graph to be traversed.

  • start (Integral) – The starting vertex index for the BFS.

  • max_distance (Optional[Integral], optional (default: None)) – The maximum distance to search for in the BFS. All vertices that are not reachable within this distance will be ignored.

  • _skip_check (bool)

Returns:

A list of integers representing the shortest path distances from the starting vertex to all other vertices in the graph. The length of the output list is equal to the number of vertices in the graph. Unreachable vertices have distance of -1.

Return type:

List[int]

See also

pygraphs.bfs()

Core implementation of BFS.

pygraphs.bfs_matrix()

Compute the shortest path distance matrix for all pairs of vertices in the graph using breadth-first search (BFS).

Examples

Create a simple disconnected graph of 7 vertices and compute the shortest path distances from a starting vertex (0) to all other vertices in the graph.

../../_images/graph.png

Disconnected graph with 7 vertices for BFS example. Distance from vertex 0 to vertex 4 is 3 (0 -> 2 -> 3 -> 4).#

1from pygraphs import bfs_distances, Graph
2
3graph = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3], [6], [5]]
4graph = Graph.from_adjacency(graph)
5start_vertex = 0
6
7distances = bfs_distances(graph, start_vertex)
8print(distances)

[0, 1, 1, 2, 3, -1, -1]

This method can be applied for directed graphs as well, where the adjacency list represents the outgoing neighbors of each vertex.

../../_images/graph_directed.png

Directed graph with 7 vertices for BFS example. Distance from vertex 2 to vertex 0 is 2 (2 -> 1 -> 0).#

1from pygraphs import bfs_distances, Graph
2
3graph = [[1, 2], [0, 2], [1, 3], [4], [3], [6], []]
4graph = Graph.from_adjacency(graph)
5start_vertex = 2
6
7distances = bfs_distances(graph, start_vertex)
8print(distances)

[2, 1, 0, 1, 2, -1, -1]