Breadth-First Search
>Graph>Traversal>Breadth-First Search
Fundamental
Essential building blocks
Breadth-First Search (BFS) is a traversal algorithm that explores a graph layer by layer. This makes it useful for finding the shortest path between two nodes, as long as all edge weights are equal and there are no negative-weight edges. If that sounds confusing, donât worryâwe'll cover more advanced shortest-path algorithms in the future.
If you're new to BFS, here are two excellent resources to get started:
- Breadth First Search by hackerearth
- Breadth First Search by Algorithms for Competitive Programming
Struggling to memorize?
Rather than memorizing the template line by line, please refer to the How to Memorize section.
BFS Template
from collections import deque
""" Example adjacency list """
adj_list = {
0: [1, 2], # Node 1 and 2 are adjacent to node 0
1: [3],
2: [3, 4],
3: [5],
4: [5],
5: []
}
def bfs(adj_list):
bfs_queue = deque([0]) # Initialize the queue with the starting node
visited = set([0])
while bfs_queue:
layer_len = len(bfs_queue)
for _ in range(layer_len):
front = bfs_queue.popleft()
""" Add your custom logic here; in this example, we print the node value """
print(front, end=" ")
for neighbor in adj_list[front]:
if neighbor not in visited:
bfs_queue.append(neighbor)
visited.add(neighbor)
print() # Print a new line after processing each layer
bfs(adj_list)
""" Output:
0
1 2
3 4
5
"""BFS Template (Finding Shortest Path)
from collections import deque
""" Example adjacency list """
adj_list = {
0: [1, 2],
1: [3],
2: [3, 4],
3: [5],
4: [5],
5: []
}
def bfs_shortest_path(adj_list, a, b): # Find the shortest path between nodes a and b
bfs_queue = deque([a]) # Initialize the queue with the starting node
visited = set([a])
length = 0
while bfs_queue:
layer_len = len(bfs_queue)
for _ in range(layer_len):
front = bfs_queue.popleft()
if front == b:
return length
for neighbor in adj_list[front]:
if neighbor not in visited:
bfs_queue.append(neighbor)
visited.add(neighbor)
length += 1
return -1 # Return -1 if node a cannot reach node b
print(bfs_shortest_path(adj_list, 0, 5))
""" Output:
3
"""Important!
Key Points about BFS and this Template:
- Some BFS templates omit the layer_len variable and its associated loop. However, this variable is crucial for distinguishing layers. Without it, we wouldn't know when to increment the length variable (e.g., length += 1).
- The time complexity of BFS is O(V + E), where V is the total number of nodes, and E is the total number of edges.
How to Memorize
- Breadth-First Search explores nodes layer by layer.
- A queue is used to manage nodes during traversal.
- Use a variable like layer_len to track the number of nodes in the current layer, helping you identify when the layer ends.