pygraphs.bfs

bfs(graph, start, *, max_distance=None, stop_encounter=None, _skip_check=False)

[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.

Warning

No tests are performed to check if the input graph is valid (e.g., if the graph contains self-loops, if the graph contains invalid vertex indices, …). The behavior of the function is undefined if the input graph is not valid.

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.

• stop_encounter (Optional[Integral], optional (default: None)) – If provided, the BFS will stop as soon as this vertex is encountered. The provided vertex is included in the output.

• _skip_check (bool)

Returns:

• parents (Dict[int, int]) – A dictionary mapping each visited vertex index to its parent vertex index in the BFS tree. The starting vertex will have a parent of None.

• distances (Dict[int, int]) – A dictionary mapping each visited vertex index to its shortest path distance from the starting vertex. The starting vertex will have a distance of 0.

Return type:

Tuple[Dict[int, int], Dict[int, int]]

Notes

The function uses a breadth-first search (BFS) algorithm to compute shortest path distances in an unweighted graph.

BFS explores the graph level by level starting from the source vertex. It first visits all vertices at distance 1, then all vertices at distance 2, and so on. This guarantees that the first time a vertex is visited, the path used is the shortest (in number of edges).

The algorithm maintains a queue of vertices to explore and a dictionary of distances initialized with the source vertex at distance 0. Each time a vertex is processed, all of its unvisited neighbors are assigned a distance equal to the current vertex distance plus one and are added to the queue.

This process continues until all reachable vertices are visited or until an optional stopping condition is met.

The time complexity is \(O(V + E)\), where \(V\) is the number of vertices and \(E\) is the number of edges in the graph.

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.

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

from pygraphs import bfs, Graph

graph = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3], [6], [5]]
graph = Graph.from_adjacency(graph)
start_vertex = 0

parent, distance = bfs(graph, start_vertex)
print("Parent:", parent)
print("Distance:", distance)

Parent: {0: None, 1: 0, 2: 0, 3: 2, 4: 3}
Distance: {0: 0, 1: 1, 2: 1, 3: 2, 4: 3}

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

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

from pygraphs import bfs, Graph

graph = [[1, 2], [0, 2], [1, 3], [4], [3], [6], []]
graph = Graph.from_adjacency(graph)
start_vertex = 2

parent, distance = bfs(graph, start_vertex)
print("Parent:", parent)
print("Distance:", distance)

Parent: {2: None, 1: 2, 3: 2, 0: 1, 4: 3}
Distance: {2: 0, 1: 1, 3: 1, 0: 2, 4: 2}