Breadth-First Search (BFS) is one of the most essential algorithms for exploring graphs and trees. Unlike Depth-First Search (DFS), which dives deep into one branch before backtracking, BFS explores nodes level by level. This approach ensures that all nodes at the current depth are visited before moving on to the next level. BFS is especially useful when you need to find the shortest path in an unweighted graph, explore social networks, or solve puzzles like mazes.
with hands-on learning.
get the skills and confidence to land your next move.
For beginners, understanding BFS is a great way to learn how queues and graphs work together. It also lays the foundation for many advanced algorithms in computer science. In this article, we will explore how to implement BFS in Python using various approaches, ranging from basic traversal to more practical applications like finding the shortest path. By following along with these examples, you will gain a solid understanding of BFS and its usefulness in solving real-world problems.
Program 1: Basic BFS Using a Queue
This first program demonstrates a simple BFS traversal on a graph using Python’s queue module. It visits all nodes starting from a specified starting node and prints them in level order.
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
graph = {
0: [1, 2],
1: [3, 4],
2: [5],
3: [],
4: [],
5: []
}
print("BFS traversal starting from node 0:")
bfs(graph, 0)In this example, the graph is represented as a dictionary, which acts as an adjacency list. A queue is used to keep track of nodes that need to be visited, and a visited set ensures that no node is processed twice. This implementation is simple, beginner-friendly, and clearly shows how BFS processes nodes level by level.
Program 2: BFS Using Adjacency Matrix
Some graphs are represented as adjacency matrices instead of lists. This version shows how BFS can be performed when the graph is dense.
from collections import deque
def bfs_matrix(matrix, start):
visited = [False] * len(matrix)
queue = deque([start])
visited[start] = True
while queue:
node = queue.popleft()
print(node, end=" ")
for i, val in enumerate(matrix[node]):
if val == 1 and not visited[i]:
visited[i] = True
queue.append(i)
graph_matrix = [
[0, 1, 1, 0, 0],
[1, 0, 1, 1, 0],
[1, 1, 0, 0, 1],
[0, 1, 0, 0, 1],
[0, 0, 1, 1, 0]
]
print("BFS traversal using adjacency matrix starting from node 0:")
bfs_matrix(graph_matrix, 0)Here, the graph is a 2D list where 1 indicates an edge between nodes. BFS works similarly to the adjacency list version, but we iterate through the matrix rows to find neighbors. This approach is useful when working with dense graphs and makes it easier to check connectivity between nodes.
Program 3: BFS Using Recursion
While BFS is usually iterative, we can simulate its behavior using recursion to explore nodes level by level.
def bfs_recursive(current_level, graph, visited):
if not current_level:
return
next_level = []
for node in current_level:
print(node, end=" ")
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
next_level.append(neighbor)
bfs_recursive(next_level, graph, visited)
graph = {
0: [1, 2],
1: [3, 4],
2: [5],
3: [],
4: [],
5: []
}
print("BFS traversal using recursion starting from node 0:")
bfs_recursive([0], graph, {0})This recursive approach helps beginners understand BFS as a level-based process. Each recursive call processes all nodes at the current level and prepares a list of nodes for the next level. Although recursion is less common for BFS in practice, it provides a different perspective on how nodes can be explored.
Program 4: BFS for Shortest Path in an Unweighted Graph
BFS can also be used to find the shortest path between two nodes in an unweighted graph. This program demonstrates that application.
from collections import deque
def bfs_shortest_path(graph, start, target):
queue = deque([start])
visited = {start}
parent = {start: None}
while queue:
node = queue.popleft()
if node == target:
break
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
parent[neighbor] = node
queue.append(neighbor)
path = []
current = target
while current is not None:
path.append(current)
current = parent[current]
path.reverse()
print(f"Shortest path from {start} to {target}: {path}")
graph = {
0: [1, 2],
1: [3, 4],
2: [5],
3: [],
4: [5],
5: []
}
bfs_shortest_path(graph, 0, 5)In this version, BFS keeps track of each node’s parent to reconstruct the shortest path once the target is reached. This application is extremely practical for network routing, social network analysis, and pathfinding in games.
Program 5: BFS for Connected Components in an Undirected Graph
BFS can also identify connected components in an undirected graph. This program shows how to explore all nodes and determine distinct groups.
from collections import deque
def bfs_connected_components(graph):
visited = set()
components = []
for start in graph:
if start not in visited:
queue = deque([start])
component = []
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
component.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
components.append(component)
return components
graph = {
'A': ['B'],
'B': ['A'],
'C': ['D'],
'D': ['C'],
'E': []
}
components = bfs_connected_components(graph)
print("Connected components in the graph:", components)This program uses BFS to explore every unvisited node fully and collects all nodes reachable from it as a connected component. Beginners can see how BFS can systematically find groups in a network and analyze graph connectivity.
Program 6: BFS with User Input
To make BFS interactive, this program allows the user to input a graph and then performs BFS from a chosen starting node.
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
graph = {}
edges = int(input("Enter number of edges: "))
for _ in range(edges):
u, v = map(int, input("Enter edge (u v): ").split())
graph.setdefault(u, []).append(v)
graph.setdefault(v, []).append(u)
start = int(input("Enter starting node: "))
print(f"BFS traversal starting from node {start}:")
bfs(graph, start)By allowing users to enter their own nodes and edges, this version helps beginners experiment with different graph structures and see BFS in action dynamically. It’s a great way to practice and reinforce understanding.
Frequently Asked Questions (FAQ)
Here are some common questions beginners often ask about BFS in Python.
Q1: What is Breadth-First Search (BFS)?
BFS is a graph traversal algorithm that explores nodes level by level, ensuring that all neighbors of a node are visited before moving deeper.
Q2: What data structure is used in BFS?
A queue is typically used to maintain the order of nodes to visit next, ensuring level-by-level traversal.
Q3: How is BFS different from DFS?
BFS explores all neighbors before moving deeper, while DFS dives deep into one path before backtracking.
Q4: Can BFS find the shortest path?
Yes, in an unweighted graph, BFS always finds the shortest path between two nodes.
Q5: Is BFS suitable for directed and undirected graphs?
Yes, BFS works on both types of graphs with minor adjustments in graph representation.
Conclusion
Breadth-First Search is a core algorithm that plays a vital role in computer science and programming. It is especially useful for level-order traversal, finding the shortest paths, and exploring networks. By going through these five Python programs, you’ve seen how BFS can be implemented using queues, adjacency matrices, recursion, and user input.
For beginners, the best way to master BFS is to practice with different graph structures and starting nodes. Experimenting with these programs will help solidify your understanding and prepare you for more advanced graph algorithms in the future.
