Nederlands
Menu

BFS versus DFS (breedte-eerst versus diepte-eerst zoeken): bezoekvolgorde, datastructuur, kortste paden, geheugen en toepassingen

Beide zijn manieren om elke knoop van een graaf of boom te bezoeken door de verbindingen te volgen. Breedte-eerst zoeken (BFS) breidt zich uit in volgorde van afstand: het bezoekt eerst alle knopen op één verbinding van het startpunt, dan die op twee verbindingen, enzovoort. Diepte-eerst zoeken (DFS) volgt één pad zo ver mogelijk, en wanneer het op een doodlopend punt komt, keert het terug en probeert een ander pad. BFS wordt geïmplementeerd met een wachtrij en DFS met een stack of recursie; op een graaf die als nabuurlijsten is opgeslagen, bezoeken beide alles in een tijd die evenredig is met het aantal knopen plus het aantal verbindingen. BFS is de gebruikelijke keuze voor kortste paden in ongewogen grafen, en DFS om alle paden uitputtend te doorzoeken of cycli op te sporen.

KenmerkBreedte-eerst zoeken (BFS)Diepte-eerst zoeken (DFS)
BezoekvolgordeDichtstbijzijnde eerst (minste verbindingen vanaf het startpunt), laag voor laag naar buitenGaat diep langs één pad, keert terug bij een doodlopend punt en gaat verder met het volgende pad
Gebruikte datastructuurWachtrij (first in, first out)Stack (last in, first out) of recursieve aanroepen
Kortste padenIn een ongewogen graaf is het aantal verbindingen bij het eerste bereiken van een knoop de kortste afstand vanaf het startpuntNiet gegarandeerd: een knoop kan eerst via een omweg worden bereikt
Tijdcomplexiteit (V knopen, E verbindingen)O(V + E) met nabuurlijsten, O(V²) met een nabuurmatrixGelijk aan BFS: O(V + E) met nabuurlijsten, O(V²) met een nabuurmatrix
GeheugengebruikDe knopen die nog moeten worden bezocht, staan in de wachtrij; bij veel vertakkingen staat een hele laag knopen tegelijk in de wachtrij, dus die wordt grootRecursief geschreven zijn alleen de knopen op het huidige pad nodig, dus het geheugen groeit met de diepte van het pad; zeer diepe zoektochten kunnen de call stack laten overlopen
Of een oplossing wordt gevondenAltijd gevonden als er eindig veel knopen zijn; ook als de zoekruimte onbegrensd groeit, worden ondiepe oplossingen eerst gevondenIn een eindige graaf altijd gevonden als bezochte knopen worden bijgehouden; als paden onbegrensd dieper kunnen worden, kan het langs één pad blijven afdalen en nooit terugkomen
Doorloopvolgorde in bomenLevel-order (niveau voor niveau vanaf de wortel, van links naar rechts)Pre-order, in-order en post-order
Typische toepassingenKortste paden in ongewogen grafen, het minimale aantal stappen in een doolhof, hoeveel hops een netwerk overbrugtUitputtend doorzoeken van doolhoven en puzzels (backtracking), samenhangende componenten en cycli vinden, topologisch sorteren

De getalswaarden zijn typische ordegroottes en variëren per procesgeneratie en product.

Wanneer welke variant?

Breedte-eerst zoeken
Wanneer je het minimale aantal stappen of het kortste pad in een ongewogen graaf wilt, of knopen wilt onderzoeken in volgorde van nabijheid tot het startpunt. Gebruik voor kortste paden met gewogen verbindingen het algoritme van Dijkstra.
Diepte-eerst zoeken
Wanneer je elk pad of elke combinatie uitputtend wilt doorzoeken, samenhangende componenten of cycli wilt vinden, of topologisch wilt sorteren om taken te ordenen. Het kan compact met recursie worden geschreven.

Veelgestelde vragen

Vindt BFS kortste paden als de verbindingen gewichten hebben?

Nee, want het pad met de minste verbindingen heeft niet noodzakelijk het kleinste totale gewicht. Zijn de gewichten nul of meer, gebruik dan het algoritme van Dijkstra. Dat vervangt de wachtrij door een prioriteitswachtrij die de knoop die het dichtst bij het startpunt ligt als eerste uitneemt, en kan worden gezien als een uitbreiding van BFS naar gewogen grafen.

Moet DFS met recursie of met een expliciete stack worden geschreven?

Recursie is kort en goed leesbaar, maar in zeer diepe grafen kunnen de geneste aanroepen de call stack laten overlopen. Schrijf je het als lus met een eigen stack, dan vermijd je dat. Afhankelijk van de volgorde waarin buren op de stack worden gezet, kan de bezoekvolgorde wel afwijken van de recursieve versie.

Wat gebeurt er als bezochte knopen niet worden bijgehouden?

In een graaf met cycli worden dezelfde knopen steeds opnieuw bezocht. Bij BFS groeit de wachtrij onbegrensd, en bij DFS kan de zoektocht eindeloos rond dezelfde cyclus gaan. Bij beide methoden worden bezochte knopen (of knopen die al aan de wachtrij of stack zijn toegevoegd) daarom gemarkeerd, zodat ze nooit opnieuw worden toegevoegd.

Test uw begrip

In een graaf waarvan de kanten geen gewicht hebben, wil je vanaf een startknoop het kleinste aantal kanten naar elke andere knoop bepalen. Welke combinatie van zoekmethode en datastructuur is geschikt?

  1. ABreedte-eerst zoeken met een wachtrij
  2. BDiepte-eerst zoeken met een stack
  3. CBreedte-eerst zoeken met een stack
Antwoord en toelichting tonen

Antwoord: A. Breedte-eerst zoeken met een wachtrij

Breedte-eerst zoeken bezoekt knopen in volgorde van afstand: eerst die op één kant van de start, dan die op twee kanten, enzovoort. Door elke nieuw gevonden knoop achteraan een wachtrij te zetten en knopen vooraan weg te nemen, blijft deze volgorde (dichtstbijzijnde eerst) behouden, zodat het aantal kanten bij het eerste bereiken van een knoop het kortste is. Diepte-eerst zoeken (met recursie of een stack) gaat langs één pad zo ver mogelijk door en kan een knoop dus eerst via een omweg bereiken; kortste afstanden zijn niet gegarandeerd. Wie een stack gebruikt in plaats van een wachtrij, krijgt een doorloop die op diepte-eerst zoeken lijkt.

In een ongerichte graaf zijn de buren van elke knoop A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. Diepte-eerst zoeken met recursie begint bij knoop A. De buren worden in de vermelde volgorde onderzocht, en zodra een nog niet bezochte knoop wordt gevonden, gaat de zoekactie daarheen. In welke volgorde worden de knopen bezocht?

  1. AA, B, C, D, E, F
  2. BA, B, D, E, C, F
  3. CA, B, D, E, F, C
Antwoord en toelichting tonen

Antwoord: C. A, B, D, E, F, C

Vanuit A gaat de zoekactie naar B en dan naar D, de eerste onbezochte buur van B. De enige buur van D, B, is al bezocht, dus de zoekactie keert terug naar B en gaat verder naar E, dan van E naar de onbezochte F en van F naar haar buur C. De volgorde is dus A, B, D, E, F, C. A, B, C, D, E, F is de volgorde van breedte-eerst zoeken, dat de dichtstbijzijnde knopen eerst bezoekt. A, B, D, E, C, F keert bij E terug zonder naar de onbezochte F te gaan en is dus geen volgorde van diepte-eerst zoeken.

Wat is een geschikte manier om een ijle graaf, een graaf met weinig kanten in verhouding tot het aantal knopen, in het geheugen op te slaan, zoals een wegennet met ongeveer 1 miljoen knopen en 3 miljoen kanten?

  1. AEen adjacentiematrix: die controleert in O(1) of twee knopen verbonden zijn en gebruikt ook het minste geheugen
  2. BAdjacentielijsten: het geheugen is evenredig met het aantal knopen plus het aantal kanten, en ze zijn geschikt om de kanten vanuit een knoop één voor één te volgen
  3. CEen adjacentiematrix: het geheugen is alleen evenredig met het aantal kanten
Antwoord en toelichting tonen

Antwoord: B. Adjacentielijsten: het geheugen is evenredig met het aantal knopen plus het aantal kanten, en ze zijn geschikt om de kanten vanuit een knoop één voor één te volgen

Een adjacentiematrix gebruikt voor V knopen een tabel van V × V, dus 1 miljoen knopen vragen 10¹² elementen, ongeveer 125 GB, zelfs met 1 bit per element. Adjacentielijsten bevatten per knoop alleen de buren, dus het geheugen is O(V + E), in dit voorbeeld maar enkele miljoenen elementen. Een adjacentiematrix heeft het voordeel dat een kant in O(1) kan worden gecontroleerd, en is geschikt voor dichte grafen of grafen met weinig knopen. Voor bewerkingen die de kanten vanuit elke knoop één voor één volgen, zoals breedte-eerst zoeken en het algoritme van Dijkstra, zijn adjacentielijsten efficiënter.

  1. In een ongerichte graaf zijn de gewichten (afstanden) van de kanten S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 en A−T: 6. Welk kortste pad van S naar T vindt het algoritme van Dijkstra, en wat is de lengte ervan?
  2. De waarden 50, 30, 70, 20, 40, 60, 80 worden in deze volgorde ingevoegd in een lege binaire zoekboom. In welke volgorde worden de knopen bezocht als de boom in post-order wordt doorlopen (eerst de linkerdeelboom, dan de rechterdeelboom, dan de knoop zelf)?

Oefenvragen over Datastructuren en algoritmen

Belangrijke termen uitgelegd

Breedte-eerst zoeken (breadth-first search)
Manier om een graaf of boom te doorzoeken die knopen bezoekt in volgorde van afstand tot het startpunt: eerst die op één kant afstand, dan die op twee kanten, enzovoort. Ze wordt geïmplementeerd met een wachtrij en vindt in een graaf zonder gewichten op de kanten het kleinste aantal kanten van het startpunt naar elke knoop. Afgekort als BFS.
Diepte-eerst zoeken (depth-first search)
Manier om een graaf of boom te doorzoeken die langs één pad zo ver mogelijk gaat en terugkeert om een ander pad te proberen als ze vastloopt. Ze wordt geïmplementeerd met recursie of een stack en wordt gebruikt om doolhoven op te lossen, samenhangende componenten en cykels te vinden, en voor topologisch sorteren. Afgekort als DFS.
Wachtrij (queue)
First-in-first-out-datastructuur (FIFO) waarin het eerst toegevoegde element als eerste wordt verwijderd. Achteraan toevoegen heet enqueue en vooraan verwijderen dequeue. Wachtrijen worden gebruikt voor werk dat op verwerking wacht, voor het doorgeven van gegevens tussen taken en voor breedte-eerst zoeken.
Stack (stapelgeheugen)
Last-in-first-out-datastructuur (LIFO) waarin het laatst toegevoegde element als eerste wordt verwijderd. Een element toevoegen heet push en een element verwijderen pop. Stacks worden gebruikt om retouradressen en lokale variabelen bij functieaanroepen te beheren (de call stack), om expressies in omgekeerde Poolse notatie te evalueren en voor diepte-eerst zoeken.
Recursie
Een functie die zichzelf aanroept als onderdeel van haar eigen verwerking. Het probleem wordt opgesplitst in kleinere problemen van dezelfde vorm, en de aanroepen stoppen bij een geval dat niet verder wordt opgesplitst (het basisgeval). Elke aanroep gebruikt stackruimte, dus te diepe recursie laat de stack overlopen. Staartrecursie, waarbij de recursieve aanroep het laatste is wat de functie doet, kan worden omgezet in een lus.
Algoritme van Dijkstra
Algoritme dat de kortste paden vindt van één startknoop naar elke knoop in een graaf waarvan de gewichten van de kanten 0 of groter zijn. Het legt herhaaldelijk de dichtstbijzijnde knoop vast waarvan de afstand nog niet definitief is, en werkt de afstanden van haar buren bij. Met negatieve gewichten werkt het niet correct.
Tijdcomplexiteit (O-notatie)
Beschrijving van hoe de rekeninspanning (tijdcomplexiteit) of het geheugen (ruimtecomplexiteit) dat een algoritme nodig heeft, groeit met het aantal gegevens n. Ze wordt geschreven in O-notatie, zoals O(n), O(n log n) of O(n²), waarbij constante factoren en termen van lagere orde wegvallen.

Verwante vergelijkingen