Pseudokod

Lekcja 4 z 9 w kursie Przeszukiwanie wszerz — algorytmy grafowe w Coddy.

bfs(n, edges, start):
   build adjacency (sort each list ascending)
   visited = all false
   queue = [start]; visited[start] = true
   order = []
   while queue not empty:
      node = queue.dequeue()   # take from the FRONT
      order.add(node)
      for nb in adj[node]:
         if not visited[nb]:
            visited[nb] = true
            queue.enqueue(nb)
   return order

Jedyną różnicą w porównaniu z DFS jest kontener: kolejka (FIFO) zamiast stosu (LIFO).
Łatwo zaimplementować kolejkę jako tablicę z przesuwającym się indeksem head: usuń element z kolejki, odczytując queue[head] i zwiększając head.

Spróbuj swoich sił

Ta lekcja nie zawiera wyzwania z kodem.