Depth-first search in Python: grafen en bomen doorlopen

Stel je voor dat je een uitgestrekt grottenstelsel verkent. Je kiest een tunnel en volgt die zo ver mogelijk, steeds dieper, tot je op een doodlopend stuk stuit. Dan ga je terug naar de laatste splitsing en probeer je een nieuwe tunnel. Deze manier van diepgaand verkennen, waarbij je alleen terugkeert als het moet, lijkt sterk op depth-first search (DFS), een fundamenteel algoritme om datastructuren zoals grafen en bomen te doorlopen.

Als je geïnteresseerd bent in datastructuren, algoritmen en probleemoplossing, zit je bij DataCamp goed: Leer meer over verschillende datastructuren en de beste algoritmen om ze te verkennen in de Data Structures and Algorithms in Python-cursus en onze Data Structures: A Comprehensive Guide With Python Examples-tutorial.

Wat is depth-first search?

Depth-first search (DFS) is een algoritme om een datastructuur, zoals een graaf of boom, te doorlopen of te doorzoeken. Het basisidee achter DFS is dat het een tak van de graaf of boom zo ver mogelijk verkent voordat het terugkeert om alternatieve takken te onderzoeken. Deze aanpak staat tegenover breadth-first search, dat alle knooppunten op het huidige diepteniveau onderzoekt voordat het naar het volgende gaat. Je kunt HIER over breadth-first search lezen.

Zie depth-first search als het verkennen van een doolhof: je kiest een pad en volgt het tot je op een doodlopend stuk komt. Eenmaal aan het einde ga je terug naar het laatste beslispunt en probeer je een andere route. Deze diepe verkenning maakt DFS een uitstekende keuze wanneer het doel is om een structuur volledig te verkennen, vooral één met veel mogelijke paden.

DFS is vooral nuttig bij problemen waarbij je elke mogelijke oplossing moet verkennen.

Een paar voorbeelden zijn:

• Beslissingsbomen in AI doorlopen, waar elke tak een reeks keuzes vertegenwoordigt en het doel is om alle mogelijke uitkomsten te evalueren.
• Padvindproblemen, zoals een spelbord navigeren of routes op een kaart vinden, die uitputtende zoektochten vereisen.

DFS zorgt ervoor dat elk knooppunt één keer wordt bezocht en dat het algoritme de volledige graaf of boom dekt.

Belangrijkste kenmerken van depth-first search in Python

Depth-first search hanteert een systematische aanpak om knooppunten te verkennen en keert alleen terug wanneer dat nodig is. Laten we enkele kernkenmerken bekijken.

Recursieve aard

In de kern werkt DFS recursief, wat betekent dat het het probleem oplost door zichzelf herhaaldelijk aan te roepen terwijl het dieper de structuur in gaat. Wanneer DFS een tak induikt, verkent het die zo diep mogelijk voordat het terugkomt om andere takken te verkennen. Dit proces van een pad dieper volgen en terugkeren wanneer er geen opties meer zijn, leent zich ideaal voor recursie. Bekijk Understanding Recursive Functions in Python voor een diepere kijk op wat recursieve functies zijn en wanneer ze nuttig zijn.

Backtracking

Backtracking is essentieel voor DFS. Wanneer het algoritme een knooppunt bereikt zonder onbezette buren, loopt het zijn stappen terug naar het vorige knooppunt en controleert of daar nog onbezette buren zijn. Als die er zijn, verkent het die; zo niet, dan blijft het teruggaan. Deze cyclus van dieper duiken en terugkeren gaat door tot alle mogelijke paden zijn behandeld of een stopvoorwaarde is bereikt.

Omgaan met cycli

Grafen kunnen cycli bevatten, paden die naar zichzelf teruglussen. Zonder de juiste voorzorgsmaatregelen kan DFS knooppunten in deze cycli eindeloos blijven bezoeken. Door elk knooppunt te markeren als bezocht zodra het voor het eerst wordt tegengekomen, voorkomt DFS onnodig herbezoeken. Zo blijft DFS, zelfs in cyclische grafen, efficiënt en vermijdt het oneindige lussen.

Grondige verkenning

Een van de kenmerken van DFS is het vermogen om een structuur volledig te verkennen. Het algoritme gaat door tot elk knooppunt is bezocht. Dit is vooral nuttig wanneer je zeker wilt weten dat geen enkele potentiële oplossing gemist wordt, zoals bij het oplossen van puzzels, het verkennen van beslissingsbomen of het navigeren door doolhoven.

Depth-first search implementeren in Python

Er zijn twee hoofdmanieren om depth-first search in Python te implementeren: recursief en iteratief. Elke aanpak heeft zijn voordelen en afwegingen, en de keuze hangt vaak af van de grootte van de graaf en het probleem dat je oplost.

Om beide methoden te illustreren, maken we een eenvoudige beslissingsboom en gebruiken we DFS om die te doorlopen. We gebruiken Python voor ons voorbeeld. Je kunt altijd de Python Programming-skill track bekijken om je Python-kennis op te frissen.

Neem als voorbeeld een binaire beslissingsboom. Hier is een eenvoudige boomstructuur waarbij elk knooppunt twee kindertakken heeft:

Laten we deze beslissingsboom expliciet in Python definiëren als een dictionary.

# Define the decision tree as a dictionary
tree = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': ['H', 'I'],
    'E': ['J', 'K'],
    'F': ['L', 'M'],
    'G': ['N', 'O'],
    'H': [], 'I': [], 'J': [], 'K': [],
    'L': [], 'M': [], 'N': [], 'O': []
}Mogelijk gemaakt door

Recursieve DFS

DFS wordt vaak recursief geïmplementeerd. Bij elk knooppunt roept DFS zichzelf aan op zijn kindknooppunten tot er geen meer te bezoeken zijn, waarna het terugkeert. Hier is een recursieve DFS-functie om de boom te doorlopen.

# Recursive DFS function
def dfs_recursive(tree, node, visited=None):
    if visited is None:
        visited = set()  # Initialize the visited set
    visited.add(node)    # Mark the node as visited
    print(node)          # Print the current node (for illustration)
    for child in tree[node]:  # Recursively visit children
        if child not in visited:
            dfs_recursive(tree, child, visited)

# Run DFS starting from node 'A'
dfs_recursive(tree, 'A')Mogelijk gemaakt door

In deze recursieve versie beginnen we bij de wortel A en verkennen we elke tak naar beneden voordat we terugkeren om de alternatieven te verkennen. Als we deze code draaien, geeft die het gevolgde pad bij het verkennen van de boom weer:

A
B
D
H
I
E
J
K
C
F
L
M
G
N
OMogelijk gemaakt door

Iteratieve DFS

Voor zeer grote beslissingsbomen kan Pythons recursiedieptelimiet problemen veroorzaken. In dat geval kunnen we DFS iteratief implementeren, met een stack om de te bezoeken knooppunten te beheren. Zo kun je voor dezelfde beslissingsboom een iteratieve DFS implementeren:

# Iterative DFS function
def dfs_iterative(tree, start):
    visited = set()  # Track visited nodes
    stack = [start]  # Stack for DFS

    while stack:  # Continue until stack is empty
        node = stack.pop()  # Pop a node from the stack
        if node not in visited:
            visited.add(node)  # Mark node as visited
            print(node)        # Print the current node (for illustration)
            stack.extend(reversed(tree[node]))  # Add child nodes to stack

# Run DFS starting from node 'A'
dfs_iterative(tree, 'A')Mogelijk gemaakt door

Deze iteratieve aanpak omzeilt recursiedieptelimieten door de stack handmatig te beheren, wat handig kan zijn voor grote bomen of diepe structuren. Het uitvoeren van deze code levert dezelfde output op als hierboven.

Wanneer recursieve versus iteratieve DFS gebruiken

Zowel recursieve als iteratieve benaderingen van depth-first search zijn waardevolle tools, maar de keuze ertussen hangt af van de structuur van de graaf en je specifieke behoeften. Laten we de sterke en zwakke punten van elke aanpak nader bekijken.

Recursieve DFS

Ik geef doorgaans de voorkeur aan recursieve DFS vanwege de eenvoud en elegantie. Deze aanpak is intuïtief en strak.

Pluspunten:

• Eenvoud: De code is compact en weerspiegelt het probleem goed.
• Leesbaarheid: Makkelijker te begrijpen, vooral voor kleine tot middelgrote problemen.

Minpunten:

• Recursiedieptelimiet: Bij grote grafen kun je stuiten op Pythons recursiedieptelimiet.

Recursie is ideaal voor problemen waarbij de boom of graaf relatief klein is en comfortabel binnen Pythons recursiediepte past.

Iteratieve DFS

Hoewel iets complexer om te schrijven, is iteratieve DFS flexibeler en kan het grotere problemen aan zonder je zorgen te maken over recursielimieten. In plaats van te vertrouwen op Pythons call stack, beheert iteratieve DFS expliciet de te verkennen knooppunten via een stack.

Pluspunten:

• Geen recursielimiet: Door de stack handmatig te beheren omzeil je Pythons recursiedieptelimiet.

Minpunten:

• Meer code: Iteratieve DFS vereist meer opzet en kan minder intuïtief zijn.
• Leesbaarheid: De code is vaak iets uitgebreider, waardoor die lastiger te volgen is.

De iteratieve aanpak is het best voor grote of complexe problemen waarbij recursiediepte een aandachtspunt is. Het is ook handig wanneer je meer controle over de doorloop nodig hebt.

Tijds- en ruimtecomplexiteit

DFS is een efficiënt algoritme, maar de prestaties worden beïnvloed door de grootte en structuur van de graaf die het verkent. Hoe lang DFS draait en hoeveel geheugen het gebruikt, hangt af van het aantal bezochte knooppunten en de verbindingen ertussen.

We gebruiken Big O-notatie om over complexiteit te praten. Voor een opfrisser over Big O-notatie, bekijk de Big O Notation and Time Complexity Guide: Intuition and Math.

Tijdscomplexiteit

De tijdscomplexiteit van DFS is O(V + E), waarbij V het aantal knooppunten is en E het aantal verbindingen ("edges"). DFS bezoekt elk knooppunt en elke verbinding één keer. De totale tijd die DFS nodig heeft, hangt dus af van hoeveel knooppunten en verbindingen er zijn.

Ruimtecomplexiteit

Het geheugengebruik in DFS hangt af van hoeveel knooppunten het algoritme op enig moment bijhoudt. Zowel recursieve als iteratieve DFS gebruiken een stack om de te verkennen knooppunten bij te houden. In het slechtste geval kan het geheugen alle knooppunten van de graaf bevatten, wat leidt tot een ruimtecomplexiteit van O(V).

Ontdek andere manieren om algoritmecomplexiteit te meten in de Analyzing Complexity of Code through Python-tutorial.

Toepassingen van depth-first search in de echte wereld

DFS is nuttig in veel vakgebieden, waaronder informatica, AI en gamedevelopment. Bekijk de onderstaande tabel voor enkele veelvoorkomende toepassingen van DFS.

Depth-first search versus andere zoekalgoritmen

Laten we DFS vergelijken met andere bekende algoritmen zoals breadth-first search, Dijkstra’s algoritme en A*.

Depth-first search versus breadth-first search

Breadth-first search (BFS) verkent een graaf laag voor laag en bezoekt alle knooppunten op het huidige diepteniveau voordat het doorgaat naar het volgende. BFS is vooral handig wanneer het doel is om het kortste pad in een ongewogen graaf te vinden. BFS kan echter veel geheugen gebruiken, vooral in brede grafen, omdat het alle knooppunten per niveau moet bijhouden. BFS is een uitstekende keuze voor sociale-netwerkanalyses of eenvoudige routeringsproblemen.

Depth-first search is daarentegen nuttig wanneer het doel is om alle mogelijke paden of oplossingen te verkennen, zoals bij het oplossen van puzzels of het vinden van cycli in een graaf. In tegenstelling tot BFS garandeert DFS niet het kortste pad. Maar het is geheugen-efficiënter, omdat het alleen het huidige pad bijhoudt.

Je kunt meer leren over breadth-first search in Breadth-First Search: A Beginner’s Guide with Python Examples.

DFS versus Dijkstra’s algoritme

Dijkstra’s algoritme is ontworpen om het kortste pad te vinden in grafen met gewogen randen, waarbij elke verbinding tussen knooppunten een bijbehorende kost heeft. Dijkstra’s verkent steeds eerst het pad met de laagste kost, zodat het optimale pad van het startknooppunt naar elk ander knooppunt wordt gevonden. Het kan echter trager zijn dan DFS bij bepaalde eenvoudige graafverkenningen. Dijkstra’s is perfect voor taken waarbij randgewichten ertoe doen, zoals wegennetwerken of complexere routeringsproblemen.

Depth-first search houdt geen rekening met randgewichten en garandeert dus niet het optimale pad. Het is echter sneller dan Dijkstra’s in ongewogen grafen of wanneer randgewichten niet relevant zijn.

Je kunt meer leren over Dijkstra’s algoritme in Implementing the Dijkstra Algorithm in Python: A Step-by-Step Tutorial.

DFS versus A*

A* (uitgesproken als “A-star”) is een algoritme dat voortbouwt op Dijkstra’s door een heuristiek te gebruiken om de zoekopdracht te sturen. Dit maakt het in veel gevallen sneller en efficiënter. A* balanceert tussen het verkennen van paden met de laagste kost (zoals Dijkstra’s) en rechtstreeks richting het doel gaan, met een heuristiek zoals de rechte-lijn-afstand naar het doel. Dit maakt A* zeer efficiënt voor taken zoals GPS-navigatie of padvinden in videogames.

Depth-first search gebruikt geen heuristiek en mist dus de “richting” die A* inzet om efficiënt het doel te bereiken. DFS is geschikter voor problemen die een grondige verkenning van de volledige graaf of beslissingsboom vereisen, terwijl A* beter is wanneer het kortste pad efficiënt moet worden gevonden met behulp van een heuristiek.

Veelvoorkomende valkuilen en hoe ze te vermijden

Bij het gebruik van depth-first search kunnen enkele veelvoorkomende problemen optreden, vooral bij grote grafen.

Vergeten bezochte knooppunten bij te houden

Een probleem ontstaat wanneer je niet bijhoudt welke knooppunten al zijn bezocht. Dit kan leiden tot oneindige lussen, vooral in grafen met cycli. Wanneer DFS knooppunten opnieuw bezoekt zonder te controleren of ze al verkend zijn, kan het vastlopen in een oneindige lus. Om dit te voorkomen, houd je een lijst of set met bezochte knooppunten bij. Controleer vóór een bezoek aan een nieuw knooppunt of het al in de visited-set staat. Zo ja, dan kun je het overslaan en voorkom je dat je vastloopt.

Stack overflow in recursieve DFS

In Python is de recursiediepte standaard beperkt tot ongeveer 1.000 niveaus, wat betekent dat diep geneste recursieve aanroepen in grote grafen een RecursionError kunnen veroorzaken. Om dit te voorkomen, kunnen we voor grote grafen een iteratieve DFS-implementatie gebruiken. Door de stack als een lijst bij te houden, omzeilen we de recursiedieptelimieten en kunnen we veel grotere grafen veilig afhandelen.

Een oplossing aanzien voor het kortste pad

Het is ook belangrijk te onthouden dat DFS niet het kortste pad tussen twee knooppunten garandeert. Omdat DFS één pad diep volgt voordat het terugkeert om andere te verkennen, kan het wel een oplossing vinden, maar die is mogelijk niet de meest directe.

Conclusie

Depth-first search is een krachtig algoritme om grafen en bomen te verkennen en te doorlopen. Met het vermogen om diep paden in te duiken en alle mogelijkheden te verkennen, is het geschikt voor uiteenlopende problemen zoals doolhoven oplossen, puzzels oplossen en beslissingsbomen verkennen.

Als je geïnteresseerd bent in zoekalgoritmen, bekijk dan mijn andere artikelen in deze serie: Binary Search in Python: A Complete Guide for Efficient Searching en Breadth-First Search: A Beginner’s Guide with Python Examples. Mogelijk ben je ook geïnteresseerd in AVL Tree: Complete Guide With Python Implementation, en Introduction to Network Analysis in Python.