Master the Breadth-First Search algorithm for finding shortest paths in unweighted graphs. Learn how to systematically explore graph levels and track paths efficiently.
Level 0: A
↙ ↓ ↘
Level 1: B C D
↙ ↘ ↙
Level 2: E F G
| Aspect | Breadth-First Search (BFS) | Depth-First Search (DFS) |
|---|---|---|
| Data Structure | Queue | Stack (or recursion) |
| Order of Exploration | Level by level | Path by path |
| Space Complexity | O(w) where w is the maximum width | O(h) where h is the maximum depth |
| Time Complexity | O(V + E) | O(V + E) |
| Best For | Shortest path, nearest neighbor | Path finding, exhaustive search |
| Applications | Social networks, GPS, web crawling | Puzzles, mazes, topological sorting |
"""
Performs a breadth-first search on a graph starting from a given vertex
:param graph: dict, adjacency list representation of the graph
:param start: starting vertex
:return: dict with parent pointers, distances, and visited set
"""
def bfs(graph, start):
from collections import deque
queue = deque([start])
visited = set([start])
parent = {}
distance = {start: 0}
while queue:
vertex = queue.popleft()
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
parent[neighbor] = vertex
distance[neighbor] = distance[vertex] + 1
return { 'parent': parent, 'distance': distance, 'visited': visited }"""
Finds the shortest path between two vertices in an unweighted graph
:param graph: dict, adjacency list representation of the graph
:param start: starting vertex
:param end: target vertex
:return: list of vertices forming the path, or None if no path exists
"""
def find_shortest_path(graph, start, end):
if start == end:
return [start]
result = bfs(graph, start)
parent = result['parent']
if end not in parent:
return None
path = []
current = end
while current is not None:
path.insert(0, current)
current = parent.get(current)
return path# Sample graph (adjacency list representation)
graph = {
'A': ['B', 'C', 'D'],
'B': ['A', 'E'],
'C': ['A', 'F'],
'D': ['A', 'G'],
'E': ['B'],
'F': ['C'],
'G': ['D']
}
# Basic BFS traversal
visited = bfs(graph, 'A')['visited']
print('BFS traversal:', list(visited)) # Output: ['A', 'B', 'C', 'D', 'E', 'F', 'G']
# Find shortest path from 'A' to 'F'
path = find_shortest_path(graph, 'A', 'F')
print('Shortest path from A to F:', path) # Output: ['A', 'C', 'F']
# Find shortest path from 'E' to 'G'
another_path = find_shortest_path(graph, 'E', 'G')
print('Shortest path from E to G:', another_path) # Output: ['E', 'B', 'A', 'D', 'G']Implement a modified BFS that can start from multiple source nodes simultaneously.
def multi_source_bfs(graph, sources):
from collections import deque
queue = deque(sources)
visited = set(sources)
distance = {source: 0 for source in sources}
while queue:
vertex = queue.popleft()
for neighbor in graph.get(vertex, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
distance[neighbor] = distance[vertex] + 1
return { 'distance': distance, 'visited': visited }Find shortest path that satisfies certain conditions (e.g., must pass through specific nodes).
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# Find path from A to F that passes through E
def find_path_through_node(graph, start, end, must_pass):
# Find path from start to must_pass
path1 = find_shortest_path(graph, start, must_pass)
# Find path from must_pass to end (excluding must_pass itself)
path2 = find_shortest_path(graph, must_pass, end)
if path1 is None or path2 is None:
return None
return path1 + path2[1:]
print(find_path_through_node(graph, 'A', 'F', 'E')) # Output: ['A', 'B', 'E', 'F']Group nodes by their levels (distances) from the start node.
const levels = groupByLevels(graph, 'A');
/*
{
0: ['A'],
1: ['B', 'C', 'D'],
2: ['E', 'F', 'G']
}
*/Note: Previously, this course referenced the CodeSignal Arcade for practice, which is no longer available. The LeetCode problems below follow the same principles and are excellent for practicing BFS algorithms.