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)