Breadth-First Search (BFS)

Algorithms

Breadth-First Search (BFS) is a graph traversal algorithm that explores all vertices at the present depth level before moving to vertices at the next depth level.

Algorithm

BFS uses a queue to maintain the order of vertices to visit:

  1. Start from a given vertex and add it to the queue
  2. While the queue is not empty:
    • Dequeue a vertex
    • Mark it as visited
    • Add all unvisited neighbors to the queue

Time Complexity

The time complexity is , where is the number of vertices and is the number of edges.

Implementation

from collections import deque

class Graph:
    def __init__(self):
        self.graph = {{}}
    
    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = []
        if v not in self.graph:
            self.graph[v] = []
        self.graph[u].append(v)
        self.graph[v].append(u)
    
    def bfs(self, start):
        visited = set()
        queue = deque([start])
        visited.add(start)
        
        while queue:
            node = queue.popleft()
            print(node, end=' ')
            for neighbor in self.graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
    
    def print_graph(self):
        for node in self.graph:
            print("{}: {}".format(node, ', '.join(map(str, self.graph[node]))))

# Example usage
if __name__ == "__main__":
    g = Graph()
    
    # Add edges to the graph
    g.add_edge('A', 'B')
    g.add_edge('A', 'C')
    g.add_edge('B', 'D')
    g.add_edge('B', 'E')
    g.add_edge('C', 'F')
    g.add_edge('C', 'G')
    
    # Print the graph
    print("Graph Representation:")
    g.print_graph()
    
    # Perform BFS
    print("\nBFS Traversal:")
    g.bfs('A')

Trace it by hand

ProblemBFS visitation order
Run BFS from vertex A on this directed graph. List the order in which vertices are visited. A → B, C B → D, E C → F D → (none) E → F F → (none)