Breadth-First Search (BFS) Example

This example demonstrates the Breadth-First Search (BFS) algorithm on a simple pygraphs.Graph. The BFS algorithm explores the vertices of a graph in layers, starting from a given source vertex and visiting all its neighbors before moving on to the next layer of vertices.

Define the graphs

Create a simple disconnected graph of 7 vertices

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

And a directed graph of 7 vertices

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

from pygraphs import Graph

graph = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3], [6], [5]]
undirected_graph = Graph.from_adjacency(graph)
print(undirected_graph.is_directed())  # False

graph = [[1, 2], [0, 2], [1, 3], [4], [3], [6], []]
directed_graph = Graph.from_adjacency(graph)
print(directed_graph.is_directed())  # True

False
True

BFS Examples

BFS Distances

The BFS distance from a source vertex to all other vertices can be computed using the pygraphs.bfs_distances() method. The distance is defined as the number of edges in the shortest path from the source vertex to each vertex. If a vertex is unreachable from the source, its distance is -1.

from pygraphs import bfs_distances

start_vertex = 0
distances = bfs_distances(undirected_graph, start_vertex)
print(distances)  # [0, 1, 1, 2, 3, -1, -1]

start_vertex = 2
distances = bfs_distances(directed_graph, start_vertex)
print(distances)  # [2, 1, 0, 1, 2, -1, -1]

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

BFS K annulus, disk, ring

The BFS k-annulus, k-disk, and k-ring of a source vertex can be computed using the pygraphs.bfs_k_annulus(), pygraphs.bfs_k_disk(), and pygraphs.bfs_k_ring() methods, respectively. The k-annulus includes all vertices that are at a distance greater than or equal to the inner distance and less than or equal to the outer distance from the source vertex.

from pygraphs import bfs_k_annulus

start_vertex = 0
inner_distance = 1
outer_distance = 2
neighborhood = bfs_k_annulus(
    undirected_graph, start_vertex, inner_distance, outer_distance
)
print(neighborhood)  # [1, 2, 3]

start_vertex = 2
inner_distance = 1
outer_distance = 1
neighborhood = bfs_k_annulus(
    directed_graph, start_vertex, inner_distance, outer_distance
)
print(neighborhood)  # [1, 3]

[1, 2, 3]
[1, 3]

BFS Shortest Path

The BFS shortest path from a source vertex to a target vertex can be computed using the pygraphs.bfs_shortest_path() method. The shortest path is defined as the path with the fewest edges from the source vertex to the target vertex. If the target vertex is unreachable from the source, the method returns an empty list.

from pygraphs import bfs_shortest_path

start_vertex = 0
end_vertex = 4
shortest_path = bfs_shortest_path(undirected_graph, start_vertex, end_vertex)
print(shortest_path)  # [0, 2, 3, 4]

start_vertex = 2
end_vertex = 0
shortest_path = bfs_shortest_path(directed_graph, start_vertex, end_vertex)
print(shortest_path)  # [2, 1, 0]

[0, 2, 3, 4]
[2, 1, 0]

BFS Shortest Distance

The BFS shortest distance between a source vertex and a target vertex can be computed using the pygraphs.bfs_shortest_distance() method. The shortest distance is defined as the number of edges in the shortest path between the source and the target. If the target is unreachable from the source, the method returns -1.

from pygraphs import bfs_shortest_distance

start_vertex = 0
end_vertex = 4
distance = bfs_shortest_distance(undirected_graph, start_vertex, end_vertex)
print(distance)  # 3

start_vertex = 2
end_vertex = 0
distance = bfs_shortest_distance(directed_graph, start_vertex, end_vertex)
print(distance)  # 2

3
2

BFS Adjacency Matrix

The BFS adjacency matrix of a graph can be computed using the pygraphs.bfs_matrix() method. The BFS adjacency matrix is a square matrix where the entry at row i and column j represents the distance from vertex i to vertex j. If vertex j is unreachable from vertex i, the entry is -1.

from pygraphs import bfs_matrix

adjacency_matrix = bfs_matrix(undirected_graph)
print(f"adjacency_matrix (shape={len(adjacency_matrix)}x{len(adjacency_matrix[0])}):")
print(adjacency_matrix)

# Expected output:
# adjacency_matrix (shape=(7x7)):
# [[ 0  1  1  2  3 -1 -1]
#  [ 1  0  1  2  3 -1 -1]
#  [ 1  1  0  1  2 -1 -1]
#  [ 2  2  1  0  1 -1 -1]
#  [ 3  3  2  1  0 -1 -1]
#  [-1 -1 -1 -1 -1  0  1]
#  [-1 -1 -1 -1 -1  1  0]]

adjacency_matrix = bfs_matrix(directed_graph)
print(f"adjacency_matrix (shape={len(adjacency_matrix)}x{len(adjacency_matrix[0])}):")
print(adjacency_matrix)

# Expected output:
# adjacency_matrix (shape=(7x7)):
# [[ 0  1  1  2  3 -1 -1]
#  [ 1  0  1  2  3 -1 -1]
#  [ 2  1  0  1  2 -1 -1]
#  [ 3  2  1  0  1 -1 -1]
#  [ 4  3  2  1  0 -1 -1]
#  [-1 -1 -1 -1 -1  0  1]
#  [-1 -1 -1 -1 -1 -1 0]]

adjacency_matrix (shape=7x7):
[[0, 1, 1, 2, 3, -1, -1], [1, 0, 1, 2, 3, -1, -1], [1, 1, 0, 1, 2, -1, -1], [2, 2, 1, 0, 1, -1, -1], [3, 3, 2, 1, 0, -1, -1], [-1, -1, -1, -1, -1, 0, 1], [-1, -1, -1, -1, -1, 1, 0]]
adjacency_matrix (shape=7x7):
[[0, 1, 1, 2, 3, -1, -1], [1, 0, 1, 2, 3, -1, -1], [2, 1, 0, 1, 2, -1, -1], [-1, -1, -1, 0, 1, -1, -1], [-1, -1, -1, 1, 0, -1, -1], [-1, -1, -1, -1, -1, 0, 1], [-1, -1, -1, -1, -1, -1, 0]]

BFS Reachability

The reachability between two vertices can be checked using the pygraphs.bfs_is_reachable() method. It returns True if there exists a path from the source vertex to the target vertex in the graph, and False otherwise.

from pygraphs import bfs_is_reachable

start_vertex = 0
end_vertex = 4
is_reachable = bfs_is_reachable(undirected_graph, start_vertex, end_vertex)
print(is_reachable)  # True

start_vertex = 6
end_vertex = 5
is_reachable = bfs_is_reachable(directed_graph, start_vertex, end_vertex)
print(is_reachable)  # False

True
False

BFS Reachable Vertices

The BFS reachable vertices from a source vertex can be computed using the pygraphs.bfs_reachable() method. The reachable vertices are defined as the set of vertices that can be reached from the source vertex.

from pygraphs import bfs_reachable

start_vertex = 0
max_distance = None

reachable_vertices = bfs_reachable(
    undirected_graph, start_vertex, max_distance=max_distance
)
print(reachable_vertices)  # [0, 1, 2, 3, 4]

start_vertex = 6
max_distance = None
reachable_vertices = bfs_reachable(
    directed_graph, start_vertex, max_distance=max_distance
)
print(reachable_vertices)  # [6]

[0, 1, 2, 3, 4]
[6]

BFS Connected Components

The BFS connected components of a graph can be computed using the pygraphs.bfs_components() method. The connected components are defined as the sets of vertices that are reachable in at least one direction (i.e., there is a path from vertex A to vertex B OR from vertex B to vertex A).

Note

Use strongly_connected=True to compute the strongly connected components of a directed graph, where both vertices A and B must be reachable from each other (i.e., there is a path from vertex A to vertex B AND from vertex B to vertex A).

from pygraphs import bfs_components

components = bfs_components(undirected_graph)
print(components)  # [[0, 1, 2, 3, 4], [5, 6]]

components = bfs_components(directed_graph, strongly_connected=False)
print(components)  # [[0, 1, 2, 3, 4], [5, 6]]

components = bfs_components(directed_graph, strongly_connected=True)
print(components)  # [[0, 1, 2], [3, 4], [5], [6]]

[[0, 1, 2, 3, 4], [5, 6]]
[[0, 1, 2, 3, 4], [5, 6]]
[[4, 3], [2, 1, 0], [6], [5]]