Wat zijn BFS- en DFS-algoritmen, en wanneer kies je welke?

BFS en DFS zijn algoritmen voor graaftraversal die systematisch vertices vinden die bereikbaar zijn vanaf een startvertex. BFS breidt niveau voor niveau uit vanuit nabije vertices en is daarom geschikt wanneer je een pad met het minimale aantal randen in een ongewogen graaf nodig hebt. DFS volgt één tak zo ver mogelijk voordat het teruggaat, waardoor het als basis wordt gebruikt voor problemen zoals structurele analyse, cyclusdetectie en topologisch sorteren. Geen van beide is altijd beter; de keuze hangt af van het padcriterium en het doel van de graaf. ocw.mit.edu↗algs4.cs.princeton.edu↗

Wat vinden BFS en DFS bij graaftraversal?

Een graaf is een relationele structuur die bestaat uit vertices en randen. Vertices vertegenwoordigen entiteiten zoals mensen, steden, webpagina's of taken, terwijl randen verbindingen daartussen vertegenwoordigen, zoals vriendschappen, wegen, links of afhankelijkheidsrelaties. De vertexverzameling wordt aangeduid met $V$ en de randenverzameling met $E$.

Als randen geen richting hebben, is de graaf ongericht. Een wederzijdse vriendschap kan bijvoorbeeld doorgaans als bidirectioneel worden gezien. Relaties zoals A die B volgt of taak A die moet worden afgerond voordat taak B kan beginnen, vormen daarentegen een gerichte graaf. In een gerichte graaf kun je alleen in de richting van een pijl bewegen; je kunt niet automatisch in de tegenovergestelde richting gaan. ocw.mit.edu↗

De meest basale vraag bij graaftraversal is: „Welke vertices zijn bereikbaar vanaf een startpunt $s$?” Tijdens het beantwoorden van deze vraag kunnen BFS en DFS ook aanvullende informatie vastleggen, zoals of een vertex is bezocht, via welk pad elke vertex voor het eerst is bereikt en de bezoekvolgorde. Een traversal die vanaf één vertex begint, verwerkt echter alleen het deel dat daadwerkelijk vanaf die vertex bereikbaar is. Deze bezoekt niet noodzakelijkerwijs elke vertex in de graaf. ocw.mit.edu↗

Een boom is ook een type graaf. Daarom kunnen BFS en DFS worden gebruikt voor problemen die op bomen lijken, zoals maphiërarchieën of organisatieschema's. Het is echter belangrijk te onthouden dat een algemene graaf cycli kan bevatten die terugkeren naar een vertex, en meerdere paden naar dezelfde vertex. Als je een implementatie die alleen voor boomtraversal is ontworpen rechtstreeks op een algemene graaf toepast, kunnen vertices dubbel worden bezocht.

Hoe verkent BFS eerst nabije vertices?

BFS staat voor Breadth-First Search. Het vindt eerst vertices die vanaf het startpunt via één rand bereikbaar zijn, daarna vertices waarvoor twee randen nodig zijn, vervolgens drie randen, en breidt het zoekbereik in die volgorde uit. Afstand betekent hier geen fysieke afstand of kosten; het is het aantal randen dat vanaf het startpunt moet worden doorlopen. algs4.cs.princeton.edu↗

BFS gebruikt hiervoor gewoonlijk een queue. Een queue is een FIFO-datastructuur (First In, First Out), wat betekent dat het eerste toegevoegde element ook als eerste wordt verwijderd. Plaats de startvertex in de queue en markeer deze als bezocht, verwijder vervolgens één vertex uit de voorkant van de queue. Markeer alle nog niet ontdekte buren van die vertex als bezocht en voeg ze toe aan de achterkant van de queue. Herhaal dit totdat de queue leeg is. Omdat eerder ontdekte, nabijgelegen vertices eerst worden verwerkt, blijft de uitbreiding niveau voor niveau behouden. gh.cp-algorithms.com↗algs4.cs.princeton.edu↗

Stel bijvoorbeeld dat je vanaf A de buren B en C ontdekt. Wanneer BFS B verwerkt, ontdekt het de buren van B; daarna verwerkt het C en ontdekt het de buren van C. Zelfs als een via B ontdekte vertex dieper ligt, wordt C, dat al op hetzelfde niveau in de queue was geplaatst, eerder of kort daarna verwerkt. De exacte volgorde tussen B en C kan variëren, afhankelijk van de volgorde waarin aangrenzende vertices worden opgeslagen.

De sleutel bij BFS is een vertex als bezocht markeren zodra deze wordt ontdekt. Als je het markeren uitstelt tot de vertex uit de queue wordt verwijderd, kunnen twee vertices dezelfde buur ontdekken en deze meer dan eens in de queue plaatsen. Bij een typische BFS is het eenvoudiger en veiliger om een nieuwe buur als ontdekt te markeren op het moment dat deze aan de queue wordt toegevoegd.

Onder welke voorwaarden levert BFS een kortste pad op?

BFS wordt vaak gekozen omdat het in een ongewogen graaf een pad met het minimale aantal randen vindt vanaf de startvertex naar elke bereikbare vertex. Het onderzoekt alle vertices op één stap afstand van de start voordat het vertices op twee stappen afstand onderzoekt. Daardoor kan een pad met minder randen dan het pad waarmee een vertex voor het eerst wordt ontdekt, niet later verschijnen. Als je tijdens BFS bij de eerste ontdekking van elke vertex de voorafgaande vertex als parent vastlegt, vormen die parentpointers een kortste-padboom. algs4.cs.princeton.edu↗

Om een pad te reconstrueren, volg je de parentpointers achterwaarts van de doelvertex naar de startvertex en keer je vervolgens de volgorde om. Als bijvoorbeeld parent[D] = B en parent[B] = A, is het ontdekte pad van A naar D: A → B → D. Gebruik een aparte markering om aan te geven dat de startvertex geen parent heeft.

Een te brede interpretatie van „kortste” leidt echter tot fouten. BFS garandeert alleen het minimale aantal randen wanneer alle randen kunnen worden behandeld alsof ze dezelfde kosten hebben. Als wegen verschillende reistijden hebben of vluchten verschillende tarieven, kan een pad met twee randen goedkoper of sneller zijn dan een pad met één rand. In dat geval is standaard-BFS geen kortste-padalgoritme naar kosten. Overweeg, afhankelijk van de eigenschappen van de gewichten, gespecialiseerde gewogen methoden zoals het algoritme van Dijkstra of het Bellman-Ford-algoritme. algs4.cs.princeton.edu↗

Daarom past BFS goed bij problemen als „Hoeveel graden van verbinding scheiden twee vrienden?” of „Hoeveel zetten zijn nodig om een punt in een raster te bereiken wanneer één cel omhoog, omlaag, naar links of naar rechts gaan als één zet telt?” Als het doel daarentegen de minste tijd of laagste kosten zijn, controleer dan eerst of randgewichten werkelijk gelijk zijn.

Waarom gaat DFS diep voordat het teruggaat?

DFS staat voor Depth-First Search. Vanaf de huidige vertex kiest het één onbezochte buur en blijft het doorgaan totdat het een tak zo diep mogelijk heeft verkend. Wanneer het een doodlopende weg bereikt, keert het terug naar de vorige vertex en zoekt het naar een andere buur die nog niet is verkend. Dit terugkeerproces wordt ook backtracking genoemd. ocw.mit.edu↗

DFS is eenvoudig te implementeren met recursieve aanroepen. Bij het betreden van een vertex markeer je deze eerst als bezocht en roep je vervolgens dezelfde traversalfunctie aan voor elke onbezochte buur van die vertex. Wanneer een recursieve aanroep eindigt, keert de besturing vanzelf terug naar het punt dat deze aanriep, wat het verloop van diep gaan en vervolgens teruggaan uitdrukt.

Recursie is niet de enige optie. DFS kan ook iteratief worden geïmplementeerd met een expliciete stack. Een stack is een LIFO-datastructuur (Last In, First Out), wat betekent dat het laatst toegevoegde element als eerste wordt verwijderd. Door de meest recent ontdekte vertex eerst te verwijderen, kun je depth-first-gedrag creëren. In een recursieve implementatie vervult de call stack van het programma deze rol impliciet. ocw.mit.edu↗gh.cp-algorithms.com↗

Parentpointers die door DFS worden gemaakt, kunnen ook één pad van de startvertex naar een vertex tonen. Er is echter geen garantie dat dat pad het minimale aantal randen heeft. Omdat DFS de eerst gekozen tak zo diep mogelijk volgt, kan het een korter pad in een andere tak pas later ontdekken. ocw.mit.edu↗

Welke soorten structurele analyse gebruiken DFS?

DFS toont zijn waarde bij het analyseren van de structuur van een graaf, in plaats van alleen bereikbaarheid te controleren. Het vinden van verbonden componenten is een representatief voorbeeld. In een ongerichte graaf vindt één DFS-uitvoering vanaf een willekeurige onbezochte vertex alle ermee verbonden vertices als één groep. Door DFS opnieuw te starten vanaf een overgebleven onbezochte vertex, vind je een andere groep.

Cyclusdetectie is een andere veelvoorkomende toepassing van DFS. Een cyclus is een structuur waarbij het volgen van randen je kan terugbrengen naar de startvertex of naar een vertex die al op het huidige pad ligt. In een gerichte graaf kun je een cyclus detecteren door te onderscheiden of je een vertex tegenkomt die al op het huidige recursieve pad ligt. Daarom moet je onderscheid maken tussen een vertex die slechts eenmaal bezocht is en een vertex die zich momenteel op het traversalpad bevindt.

Topologisch sorteren ordent gerichte afhankelijkheden, zoals vereistenrelaties tussen taken, in een volgorde. Dit is alleen mogelijk in een gerichte acyclische graaf, ofwel een DAG. Een DAG is een gerichte graaf zonder cyclus die door het volgen van randrichtingen terugkeert naar het beginpunt. Als er een cyclus bestaat, ontstaat een tegenspraak — bijvoorbeeld B moet klaar zijn vóór A en A moet klaar zijn vóór B — zodat geen enkele lineaire ordening aan alle randen kan voldoen. Een methode die de voltooiingsvolgorde van DFS gebruikt, is een basis voor topologisch sorteren. algs4.cs.princeton.edu↗

Het vinden van sterk verbonden componenten is eveneens een belangrijk onderwerp dat op DFS is gebaseerd. Een sterk verbonden component is een verzameling vertices in een gerichte graaf waarin elk paar vertices binnen dezelfde groep elkaar kan bereiken. Dit probleem wordt echter niet opgelost met slechts één eenvoudige DFS; het vereist een algoritmische constructie die traversalvolgorde en randrichtingen gebruikt. algs4.cs.princeton.edu↗

Welke problemen ontstaan zonder bezoektmarkeringen?

In een algemene graaf is een visited-array of -set niet optioneel; deze is essentieel voor terminatie en correctheid. Als A en B bijvoorbeeld verbonden zijn, kun je van A naar B gaan en vervolgens van B terug naar A. Zonder controle op de bezochte status kan DFS oneindig recursief tussen A en B wisselen, en kan BFS dezelfde vertex meerdere keren in de queue plaatsen. ocw.mit.edu↗

De term bezocht kan afhankelijk van de implementatie iets anders worden onderverdeeld. Bij BFS wordt een vertex gewoonlijk als „ontdekt” gemarkeerd zodra deze aan de queue wordt toegevoegd. Bij DFS is het gebruikelijk om een vertex meteen als bezocht te markeren wanneer de functie ervan wordt betreden. Geavanceerdere analyse van gerichte grafen kan onderscheid maken tussen een onbezochte status, een status die momenteel wordt onderzocht en een voltooide status.

Het principe dat elke vertex slechts één keer wordt bezocht, is rechtstreeks verbonden met de efficiëntie van traversal. Als je vertices die al zijn verwerkt niet opnieuw uitbreidt, inspecteer je met adjacentielijsten elke vertex en rand slechts een beperkt aantal keer. Als je bovendien alleen een parentpointer toewijst wanneer een vertex voor het eerst wordt ontdekt, is duidelijk via welk pad die vertex als eerste is ontdekt.

Om een volledige graaf te doorlopen, heb je een buitenste lus nodig. Onderzoek elke vertex op zijn beurt en start telkens een nieuwe BFS of DFS vanaf een vertex die nog niet is bezocht. In een ongerichte graaf levert dit een traversal per verbonden component op. In een gerichte graaf worden hiermee achtereenvolgens bereiken verwerkt die in de gekozen randrichtingen bereikbaar zijn. ocw.mit.edu↗

Waarom hangt de tijdcomplexiteit af van de graafrepresentatie?

De tijdcomplexiteit van BFS en DFS wordt vaak gegeven als $O(\lvert V \rvert + \lvert E \rvert)$. Dit is de standaardanalyse bij het gebruik van adjacentielijsten. Een adjacentielijst bewaart voor elke vertex de lijst van direct verbonden buren. Met bezoektmarkeringen wordt elke vertex eenmaal verwerkt en worden randen gecontroleerd bij het doorlopen van de buurlijsten, zodat de totale hoeveelheid werk evenredig is met het aantal vertices plus het aantal randen. ocw.mit.edu↗

De extra benodigde ruimte is doorgaans $O(\lvert V \rvert)$. Dit omvat de visited-array, parent-array en de BFS-queue of DFS-stack. Bij recursieve DFS hoort ook de call stack die nodig is voor de recursiediepte bij de extra ruimte. Het is nuttig om onderscheid te maken tussen de ruimte om de graaf zelf op te slaan en de extra ruimte die het traversalalgoritme gebruikt. ocw.mit.edu↗

Een adjacentiematrix slaat voor elk paar vertices in een tabel op of er een rand bestaat. Om de buren van een vertex te vinden, moet je mogelijk elke mogelijke vertex inspecteren. Daarom kan BFS of DFS met een adjacentiematrix doorgaans $O(\lvert V \rvert^2)$ tijd kosten. Voor ijle grafen met weinig randen zijn adjacentielijsten bijzonder efficiënt, omdat ze alleen daadwerkelijk verbonden buren doorlopen. ocw.mit.edu↗

Complexiteitsnotatie beschrijft hoe het gebruik van middelen doorgaans groeit naarmate de invoergrootte toeneemt. De werkelijke uitvoeringstijd wordt ook beïnvloed door vertexidentificatoren, de implementatie van de adjacentielijst, de geheugenindeling en de omvang van het deel dat bereikbaar is vanaf het startpunt van de traversal. Toch is het bij het kiezen van een algoritme verstandig om eerst te controleren of de graaf ijl is en hoe deze wordt weergegeven.

Ligt de daadwerkelijke bezoekvolgorde van BFS of DFS vast?

Nee. BFS volgt het principe dat eerst nabije niveaus worden verwerkt en DFS volgt het principe dat de huidige tak diep wordt verkend, maar welke vertex binnen hetzelfde niveau het eerst wordt bezocht of welke tak als eerste wordt onderzocht uit meerdere buren, hangt af van de opslagvolgorde van aangrenzende vertices. gh.cp-algorithms.com↗gh.cp-algorithms.com↗

Als de buurlijst van A bijvoorbeeld de volgorde B, C heeft, ontdekt BFS doorgaans B eerst. Als de lijst wordt gewijzigd naar C, B, kan C eerst worden ontdekt. Dit verschil kan bij DFS een groter effect hebben. Als de eerst gekozen buur verandert, verandert ook de diep verkende tak zelf, samen met de traversalboom en DFS-paden die via parentpointers worden gemaakt.

Dit feit is belangrijk bij het beoordelen van het resultaat van een algoritme. Als een probleem „de lexicografisch eerste bezoekvolgorde” vereist, moet je adjacentielijsten sorteren of een prioriteitsregel specificeren. Als je daarentegen alleen bereikbaarheid, het aantal verbonden componenten of afstanden in minimaal aantal randen nodig hebt, hoeft de gedetailleerde volgorde binnen hetzelfde niveau of dezelfde diepte niet centraal te staan in het resultaat.

Vooral bij iteratieve DFS met een stack kan de volgorde waarin buren op de stack worden geplaatst het omgekeerde zijn van de volgorde waarin ze daadwerkelijk worden verwijderd. Als je dezelfde bezoekvolgorde wilt als een recursieve implementatie met een opgegeven adjacentielijstvolgorde, moet je bewust de richting aanpassen waarin buren op de stack worden geplaatst. Dit is geen andere definitie van DFS; het is een implementatieverschil dat wordt veroorzaakt door LIFO-gedrag.

Wat zijn veelvoorkomende misvattingen en fouten?

De eerste misvatting is dat BFS elk soort kortste-padprobleem oplost. Zoals eerder besproken garandeert BFS het minimale aantal randen in een ongewogen graaf. Als gewichten verschillen, heeft de ene beweging niet noodzakelijk dezelfde waarde als de andere, waardoor het probleemmodel zelf verandert. algs4.cs.princeton.edu↗algs4.cs.princeton.edu↗

De tweede is de aanname dat DFS altijd minder geheugen gebruikt dan BFS. Inclusief visited-arrays en traversalstatus kunnen beide algoritmen doorgaans $O(\lvert V \rvert)$ extra ruimte gebruiken. De maximale grootte van de queue of stack kan verschillen voor specifieke graafvormen en implementaties, maar asymptotische complexiteit alleen bewijst geen onvoorwaardelijk voordeel voor een van beide. ocw.mit.edu↗

De derde is de overtuiging dat recursieve DFS voor elke invoer veilig is. In een graaf met een zeer grote diepte wordt ook de recursiediepte groot. Je moet rekening houden met de limiet van de call stack van de taal en uitvoeringsomgeving; in zulke gevallen kan een iteratieve implementatie met een expliciete stack praktischer zijn. Het is ook belangrijk te begrijpen dat de recursieve call stack deel uitmaakt van de extra ruimte van DFS. ocw.mit.edu↗

De vierde is een gerichte graaf behandelen alsof deze ongericht is. Het bestaan van een rand van A naar B betekent niet dat je van B naar A kunt gaan. Bij het opslaan van invoer in adjacentielijsten voeg je bij een ongerichte graaf doorgaans een rand toe aan de lijsten van beide vertices, terwijl je deze bij een gerichte graaf alleen toevoegt aan de lijst van de bronvertex. Dit verschil verandert de betekenis van bereikbaarheid, verbondenheid en cycli. ocw.mit.edu↗

De vijfde is een traversalresultaat verwarren met één uniek correct pad. Wanneer meerdere paden hetzelfde minimale aantal randen hebben, legt BFS er één vast via parentpointers. DFS kan ook verschillende paden opleveren, afhankelijk van de buurvolgorde. Als het pad zelf een prioriteit nodig heeft, moeten sorteerregels of aanvullende voorwaarden in het probleem worden gespecificeerd.

Welke criteria gebruik je bij de keuze voor een probleem?

Het beste is om eerst het doel onder woorden te brengen. Als de vraag alleen luidt: „Is het bereikbaar vanaf het startpunt?”, zijn zowel BFS als DFS mogelijk en kun je kiezen op basis van de implementatieomgeving en de analyse die daarna nodig is. Als je het minimale aantal randen nodig hebt, zoals bij „Hoeveel identieke zetten zijn nodig om aan te komen?”, is BFS de logische keuze. Als je een pad diep moet volgen tijdens het analyseren van structuur, of als het moment waarop je terugkeert belangrijk is, is DFS waarschijnlijk passend.

Controleer vervolgens wat de randen betekenen. Bepaal of elke beweging dezelfde kosten heeft of dat gewichten zoals tijd, afstand of kosten een rol spelen. Als gewichten bestaan, pas dan niet rechtstreeks de kortste-padeigenschap van BFS toe. Controleer ook vooraf of de graaf gericht is, of cycli mogelijk zijn en of je de volledige graaf moet onderzoeken. ocw.mit.edu↗algs4.cs.princeton.edu↗

De selectiecriteria kunnen als volgt worden samengevat.

Houd ten slotte rekening met de invoergrootte en representatie. Voor een ijle graaf passen adjacentielijsten en de standaardanalyse van $O(\lvert V \rvert + \lvert E \rvert)$ voor BFS en DFS goed. Overweeg iteratieve DFS in omgevingen waar recursiediepte een probleem kan zijn. Als de bezoekvolgorde invloed heeft op beoordeling of bedrijfsregels, maakt ook de volgorde van adjacentielijsten deel uit van het ontwerp.

Conclusie: traversaldoelen en voorwaarden zijn belangrijker dan namen

BFS en DFS zijn verschillende strategieën om een graaf grondig te doorlopen. BFS gebruikt een queue om vanuit nabije vertices uit te breiden en heeft als sterke punt dat het paden met een minimaal aantal randen biedt in ongewogen grafen. DFS gebruikt recursie of een stack om één tak diep te verkennen en terug te gaan, en vormt de basis voor veel methoden die met graafstructuur werken, waaronder verbonden componenten, cycli en topologisch sorteren in DAG's. ocw.mit.edu↗algs4.cs.princeton.edu↗

Beide vereisen bezoektmarkeringen en hebben doorgaans dezelfde asymptotische tijdcomplexiteit wanneer adjacentielijsten worden gebruikt. De sleutel bij de keuze tussen beide is daarom niet één enkel label zoals snelheid, maar wat een kortste pad definieert, of randen gewogen zijn, hoe richting en cycli moeten worden geïnterpreteerd en of de hele graaf moet worden verwerkt. Door deze voorwaarden eerst te onderscheiden, kun je BFS en DFS voor het juiste doel gebruiken.