beste lezers, in dit artikel zal ik u door het concept van Depth First Search (DFS). Dit is een grafiek concept dat is een veel voorkomend probleem in veel concurrerende codering examens. Dus, laten we eens kijken naar het maken van een DFS traversal met behulp van Python.
inhoudsopgave:
Wat is Diepte Eerste zoekopdracht?
de depth-first search is een algoritme dat gebruik maakt van de stack-gegevensstructuur om grafieken en bomen te doorkruisen. Het concept van diepte – eerste zoekopdracht komt van het woord “diepte”. De boom doorkruist tot de diepte van een tak en dan terug doorkruist naar de rest van de knooppunten.
overweeg een lege “Stack” die de bezochte knooppunten bevat voor elke iteratie. Onze taak hier is als volgt::
- begin bij de root node en duw het op de stack.
- Controleer op aangrenzende knooppunten van de boomstructuur en selecteer één knooppunt.
- doorkruis de gehele tak van het geselecteerde knooppunt en duw alle knooppunten in de stack.
- bij het bereiken van het einde van een tak (geen aangrenzende knooppunten meer) dwz nde bladknooppunt, ga terug met een enkele stap en zoek naar aangrenzende knooppunten van de n-1de knoop.
- als er aangrenzende knooppunten zijn voor de n-1de knooppunt, doorkruis dan die branches en push knooppunten op de stack.
concept van diepte Eerste zoekopdracht geïllustreerd
laten we eens kijken in onze voorbeeld grafiek hieronder:
A is de root node. Dus omdat A wordt bezocht, duwen we dit op de stapel.
Stack : A
laten we naar de tak a-B. B wordt niet bezocht, dus we gaan naar B en duwen B op de stack.
Stack : A B
nu zijn we aan het einde gekomen van onze A-B branch en we gaan naar de n-1de knoop die A. is we zullen nu kijken naar de aangrenzende knoop van A die S. Visit S is en duw het op de stack. Nu moet je de S-C-D tak te doorkruisen, tot de diepte dwz tot D en mark S, C, D zoals bezocht.
Stack: A B S C D
aangezien D geen andere aangrenzende knooppunten heeft, ga terug naar C en doorkruis de aangrenzende tak E-H-G naar de diepte en duw ze op de stack.
Stack : A B S C D E H G
bij het bereiken van D, is er slechts een aangrenzende knooppunt dat wil zeggen F die niet wordt bezocht. Druk F ook op de stapel.
Stack : A B S C D E H G F
deze stack zelf is de traversal van de DFS.
Coderingsdiepte eerste zoekalgoritme in Python
zoals u weet, zijn er veel methoden om een grafiek weer te geven die de adjacency list en adjacency matrix is.
in het volgende voorbeeld heb ik een adjacency lijst gedefinieerd voor elk van de knooppunten in onze grafiek.
graph1 = { 'A' : , 'B' : , 'C' : , 'D' : , 'E' : , 'F' : , 'G' : , 'H' : , 'S' : }
opmerking: Deze adjacency lijst kan worden ingevoerd van de gebruiker en hoeft niet hard-gecodeerd.
nu zullen we onze DFS-functie definiëren die 3 parameters als invoer gebruikt-de grafiek (adjacency list), Een knooppunt en een lijst van bezochte knooppunten.
als het huidige knooppunt niet bezocht is of niet aanwezig is in de bezochte lijst, markeer het als bezocht en voeg het toe aan de bezochte lijst.
Ga naar het volgende knooppunt en geef dit knooppunt recursief door aan de DFS-functie. Op deze manier beweegt elk knooppunt tot de diepte en drukt het af als de DFS-uitvoer.
def dfs(graph, node, visited): if node not in visited: visited.append(node) for k in graph: dfs(graph,k, visited) return visitedvisited = dfs(graph1,'A', )print(visited)
volledige Code en uitvoer
graph1 = { 'A' : , 'B' : , 'C' : , 'D' : , 'E' : , 'F' : , 'G' : , 'H' : , 'S' : }def dfs(graph, node, visited): if node not in visited: visited.append(node) for k in graph: dfs(graph,k, visited) return visitedvisited = dfs(graph1,'A', )print(visited)
de uitvoer van de bovenstaande code is als volgt:
conclusie
ik hoop dat je deze tutorial hebt gevolgd op het DFS algoritme en in staat bent geweest om de code en het voorbeeld te begrijpen. Probeer het uit met pen en papier naast je om de traversals beter te begrijpen.