Breadth-First Search

Level-order traversal using a queue. Guarantees shortest path in unweighted graphs.

BFS(graph, start):
  visited = {start}
  queue = [start]
  order = []

  WHILE queue not empty:
    node = DEQUEUE(queue)
    order.append(node)

    FOR each neighbor OF node:
      IF neighbor NOT in visited:
        visited.add(neighbor)
        ENQUEUE(queue, neighbor)

  RETURN order