Breadth-first search

Given an adjacency-list representation of a graph and a starting vertex, visit and print every reachable vertex in breadth-first order.

Hint

Use a queue to process vertices level by level. Mark the starting vertex visited before adding it to the queue. Repeatedly remove the next vertex, print it, and enqueue each unvisited neighbor while marking it visited. Marking a vertex when it is enqueued prevents duplicate visits.

• Python
• Javascript
•  Run

from collections import deque

def bfs(graph, src):
  visited = [False] * len(graph)
  
  queue = deque()
  
  queue.append(src)
  visited[src] = True

  while queue:
    node = queue.popleft()
    print(node, end=" ")

    for x in graph[node]:
      if not visited[x]:
        queue.append(x)
        visited[x] = True
  
  print()

graph = [[1, 2], [0, 3, 4], [0, 4], [1], [1, 2]]
bfs(graph, 0)

//=include bfs.js