Ricerca nei grafi: BFS e DFS

Nel 1736 Leonhard Euler dimostrò che nessuna passeggiata attraversa ciascuno dei sette ponti di Königsberg una volta sola, e con quella risposta nacque la teoria dei grafi.

Punti e linee

Un grafo è un insieme di punti, detti vertici o nodi, uniti da linee, dette archi. L'idea è semplice e si adatta a moltissime cose: città unite da strade, pagine web unite da link, persone unite da amicizie, caselle di un labirinto unite dove non c'è un muro. Una volta disegnato un problema come grafo, la stessa manciata di algoritmi può rispondere a domande come «posso arrivare da qui a lì?» e «qual è la strada più breve?».

Memorizzare un grafo nel codice

Un modo comune per memorizzare un grafo è la lista di adiacenza: per ogni vertice, la lista dei suoi vicini. Gli appunti del corso 6.006 del MIT usano proprio questo, un array o dizionario Adj in cui Adj[u] elenca i vertici uniti a u. Per il grafo qui sopra si presenta così:

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D", "E"],
  D: ["B", "C", "F"],
  E: ["C", "F"],
  F: ["D", "E"],
};

Visita in ampiezza: anello per anello

La visita in ampiezza (BFS) esplora un grafo ad anelli attorno alla partenza. Prima la partenza stessa, a distanza 0. Poi tutti i suoi vicini, a distanza 1. Poi ogni nuovo vertice accanto a questi, a distanza 2, e così via. Per farlo usa una coda, una fila in cui il primo a entrare è il primo a uscire. Prendi il vertice in testa alla coda, visitalo e aggiungi in fondo i suoi vicini non ancora visti. Partendo da A nell'esempio, la BFS visita A, poi B e C, poi D ed E, poi F. Poiché si allarga un anello alla volta, la prima volta che la BFS raggiunge un vertice ha trovato un percorso con il minor numero di archi. F è a 3 archi da A, per esempio A, B, D, F.

function bfs(graph, start) {
  const seen = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length) {
    const u = queue.shift();        // il primo entrato è il primo a uscire
    order.push(u);
    for (const v of graph[u]) {
      if (!seen.has(v)) { seen.add(v); queue.push(v); }
    }
  }
  return order;   // A B C D E F
}

Visita in profondità: più avanti possibile, poi indietro

La visita in profondità (DFS) si comporta come una persona in un labirinto che tiene sempre una mano sul muro. Segue un percorso il più in profondità possibile. Quando arriva a un vicolo cieco o in un punto già visto, torna indietro all'ultimo punto di scelta e prova l'opzione successiva. Usa una pila invece di una coda (l'ultimo entrato è il primo a uscire) ed è molto naturale da scrivere con la ricorsione, dove è la pila delle chiamate a ricordare. Partendo da A, una DFS ricorsiva visita A, B, D, C, E, F. La DFS raggiunge tutti i vertici che raggiunge la BFS, ma il percorso che segue non è per forza il più breve.

function dfs(graph, u, seen = new Set(), order = []) {
  seen.add(u);
  order.push(u);
  for (const v of graph[u]) if (!seen.has(v)) dfs(graph, v, seen, order);
  return order;   // A B D C E F
}

Quale usare

Nel primo labirinto del laboratorio, la BFS visita 105 caselle e trova un percorso di 22 mosse, il più breve possibile. La DFS per caso si tuffa verso l'arrivo e visita solo 31 caselle, ma il suo percorso richiede 28 mosse. Nessuna delle due costa sempre meno. Entrambe trattano ogni vertice e ogni arco un numero fisso di volte, quindi entrambe girano in tempo O(V + E) per V vertici ed E archi. Scegli la BFS quando ti servono meno passi possibile: il minor numero di mosse in un rompicapo, il minor numero di legami tra due persone. Scegli la DFS quando devi esplorare tutto o seguire le scelte fino in fondo: controllare se tutte le stanze di un labirinto sono collegate, oppure provare le mosse di un rompicapo una linea alla volta e tornare indietro quando sei bloccato. Quando gli archi hanno lunghezze diverse, come le strade, nessuna delle due basta da sola; metodi come l'algoritmo di Dijkstra estendono l'idea della BFS con le distanze.