Pseudocodice

Lezione 4 di 9 del corso Ricerca in ampiezza - Algoritmi sui grafi di 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

L’unica differenza rispetto a DFS è il contenitore: una coda (FIFO) invece di uno stack (LIFO).
Un modo semplice per scrivere la coda consiste nell’usare un array con un indice head che avanza: per estrarre un elemento dalla coda, leggi queue[head] e incrementa head.

Provalo tu

Questa lezione non include una sfida di codice.