Grafen doorzoeken: BFS en DFS

In 1736 toonde Leonhard Euler aan dat geen wandeling elk van de zeven bruggen van Koningsbergen precies eenmaal oversteekt. Met dat antwoord begon de grafentheorie.

Punten en lijnen

Een graaf is een verzameling punten, knopen genoemd, verbonden door lijnen, kanten genoemd. Het idee is eenvoudig en past bij enorm veel dingen: steden verbonden door wegen, webpagina's door links, mensen door vriendschappen en doolhofvakjes verbonden waar geen muur is. Zodra je een probleem als graaf tekent, kunnen dezelfde paar algoritmen vragen beantwoorden zoals ‘kan ik van hier naar daar?’ en ‘wat is de kortste weg?’

Een graaf opslaan in code

Een gebruikelijke manier om een graaf op te slaan is een burenlijst: voor elke knoop een lijst van zijn buren. De notities bij MIT 6.006 gebruiken precies dit: een array of woordenboek Adj waarin Adj[u] de met u verbonden knopen opsomt. Voor de graaf hierboven ziet dat er zo uit:

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

Breedte-eerst zoeken: ring voor ring

Breedte-eerst zoeken (BFS) verkent een graaf in ringen rond de start. Eerst de start zelf, op afstand 0. Dan alle buren, op afstand 1. Dan elke nieuwe knoop naast die buren, op afstand 2, enzovoort. Hiervoor houdt het een wachtrij bij, waarin wie eerst binnenkomt er eerst uitgaat. Neem de voorste knoop, bezoek die en voeg nog ongeziene buren achteraan toe. Vanaf A bezoekt BFS in het voorbeeld A, dan B en C, dan D en E en dan F. Omdat het ring voor ring naar buiten gaat, vindt BFS bij de eerste keer bereiken van een knoop een pad met de minste kanten. F ligt 3 kanten van A, bijvoorbeeld 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();        // first in, first out
    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
}

Diepte-eerst zoeken: zo ver mogelijk, dan terug

Diepte-eerst zoeken (DFS) gedraagt zich als iemand die in een doolhof één hand aan de muur houdt. Het volgt één pad zo diep mogelijk. Bij een doodlopend einde of al bezochte plek gaat het terug naar het recentste keuzepunt en probeert de volgende optie. Het gebruikt een stapel in plaats van een wachtrij, laatst erin, eerst eruit, en is heel natuurlijk recursief te schrijven, waarbij de aanroepstapel het onthouden doet. Vanaf A bezoekt recursieve DFS A, B, D, C, E, F. DFS bereikt elke knoop die BFS bereikt, maar het gevolgde pad is niet noodzakelijk het kortste.

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
}

Welke kies je?

In het eerste doolhof van het lab bezoekt BFS 105 vakjes en vindt een pad van 22 zetten, het kortst mogelijke. DFS gaat toevallig richting het doel en bezoekt maar 31 vakjes, maar het pad kost 28 zetten. Geen van beide is altijd goedkoper. Beide verwerken elke knoop en elke kant een vast aantal keren en hebben dus looptijd O(V + E) voor V knopen en E kanten. Kies BFS als je de minste stappen nodig hebt: de minste zetten in een puzzel of de minste verbindingen tussen twee mensen. Kies DFS als je alles wilt verkennen of keuzes tot het einde wilt volgen: controleren of elke doolhofkamer verbonden is of puzzelzetten één reeks tegelijk proberen en teruggaan als je vastloopt. Als kanten verschillende lengten hebben, zoals wegen, is geen van beide op zichzelf genoeg; methoden zoals het algoritme van Dijkstra breiden het BFS-idee uit met afstanden.