Breadth-First Search (BFS)

Breadth First Search is executed through a queue-based approach, commencing from a designated vertex. It systematically explores all adjacent vertices of the initial vertex before progressing to subsequent vertices in the traversal process. Here’s an example implementation of Breadth-First Search (BFS) algorithm:

Time Complexity: O(V + E)

Python

import collections

def bfs(graph, root):
    visited, queue = set(), collections.deque([root])
    visited.add(root)
 
    while queue:
        # Dequeuing a vertex from queue
        vertex = queue.popleft()
        print(str(vertex) + " ", end="")
 
        # If not visited, marking it as visited, and enqueuing it
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
 
 
if __name__ == '__main__':
    graph = {0: [1, 2], 1: [2], 2: [3], 3: [1, 2]}
    print("Below is the Breadth First Traversal: ")
    bfs(graph, 0)

BFS