Breadth-First Search (BFS) is a fundamental graph traversal algorithm that explores all vertices at the current depth level before moving to the next level. It is widely used in various applications, such as finding the shortest path, solving puzzles, and network flow analysis. BFS works efficiently on both directed and undirected graphs, represented as adjacency lists or matrices.
Key Features of BFS
1. Level-Order Traversal:
BFS explores nodes level by level, starting from the source node.
2. Queue-Based Implementation:
BFS uses a queue data structure to manage the traversal order.
3. Graph Representation:
BFS operates seamlessly on adjacency lists and adjacency matrices.
4. Time Complexity:
The time complexity is , where is the number of vertices and is the number of edges.
5. Space Complexity:
Space complexity is , as it uses a queue to store nodes during traversal.
BFS Algorithm
1. Initialize a queue and enqueue the starting node.
2. Mark the starting node as visited.
3. Dequeue a node and process it.
4. Enqueue all unvisited neighbors of the dequeued node.
5. Repeat steps 3–4 until the queue is empty.
Code Boilerplate: BFS in Python
from collections import deque
def bfs(graph, start):
visited = set() # To track visited nodes
queue = deque([start]) # Initialize queue with the start node
while queue:
# Dequeue a node from the front
vertex = queue.popleft()
# If the node is not visited, process it
if vertex not in visited:
print(vertex, end=” “) # Process the node
visited.add(vertex)
# Enqueue all unvisited neighbors
for neighbor in graph[vertex]:
if neighbor not in visited:
queue.append(neighbor)
# Example graph (Adjacency List)
graph = {
‘A’: [‘B’, ‘C’],
‘B’: [‘D’, ‘E’],
‘C’: [‘F’],
‘D’: [],
‘E’: [‘F’],
‘F’: []
}
# Perform BFS starting at vertex ‘A’
print(“BFS Traversal:”)
bfs(graph, ‘A’)
Schematic Representation
Consider the graph:
A
/ \
B C
/ \ \
D E — F
BFS starting from A would visit nodes in this order: A → B → C → D → E → F.
Applications of BFS
1. Shortest Path in Unweighted Graphs:
BFS guarantees the shortest path from the source to all reachable nodes.
2. Network Analysis:
BFS is used to measure connectivity and discover reachable nodes.
3. Solving Puzzles and Games:
BFS is commonly applied in maze-solving algorithms or state-space exploration.
4. Cycle Detection in Undirected Graphs:
BFS can identify cycles in graphs by checking revisited nodes.
Conclusion
BFS is a versatile algorithm, ideal for scenarios requiring level-wise exploration. Its queue-based approach ensures systematic traversal, making it an essential tool in graph theory and real-world applications.
The article above is rendered by integrating outputs of 1 HUMAN AGENT & 3 AI AGENTS, an amalgamation of HGI and AI to serve technology education globally.