kära läsare, i den här artikeln kommer jag att gå igenom begreppet djup första sökning (DFS). Detta är en graf koncept som är ett vanligt problem i många konkurrenskraftiga kodning tentor. Så, låt oss titta på att skapa en DFS-traversal med Python.
Innehållsförteckning
Vad är djup första sökning?
djup-första sökningen är en algoritm som använder Stackdatastrukturen för att korsa grafer och träd. Begreppet djup – första sökning kommer från ordet ”djup”. Trädet korsar till djupet av en gren och sedan tillbaka korsar till resten av noderna.
Tänk på en tom ”Stack” som innehåller de besökta noderna för varje iteration. Vår uppgift här är följande:
- börja vid rotnoden och tryck den på stapeln.
- kontrollera eventuella angränsande noder i trädet och välj en nod.
- korsa hela grenen av den valda noden och tryck alla noder i stapeln.
- när du når slutet av en gren (inga fler intilliggande noder) dvs nth bladnod, flytta tillbaka med ett enda steg och leta efter intilliggande noder i n-1: e noden.
- om det finns intilliggande noder för N-1: e noden, korsa dessa grenar och tryck noder på stapeln.
begreppet djup första sökning illustrerad
Låt oss titta på vårt exempeldiagram nedan:
A är rotnoden. Så eftersom A besöks trycker vi detta på stacken.
Stack : A
Låt oss gå till filialen A-B. B besöks inte, så vi går till B och trycker B på stapeln.
Stack : A B
nu har vi kommit till slutet av vår A-B-gren och vi flyttar till n-1: e noden som är A. Vi kommer nu att titta på den intilliggande noden till A som är S. besök S och tryck den på stacken. Nu måste du korsa s-C-d-grenen, upp till djupet, dvs upp till D och markera S, C, D som besökt.
Stack: A B S C D
eftersom D inte har några andra intilliggande noder, flytta tillbaka till C och korsa dess intilliggande gren E-H-G till djupet och skjut dem på stapeln.
Stack : A B S C D E H G
när man når D finns det bara en intilliggande nod dvs F som inte besöks. Tryck F på stapeln också.
Stack : A B S C D E H G F
denna stack i sig är traversal av DFS.
Kodningsdjup första sökalgoritmen i Python
som du måste vara medveten om finns det många metoder för att representera en graf som är adjacency list och adjacency matrix.
så i följande exempel har jag definierat en adjacency-lista för var och en av noderna i vår graf.
graph1 = { 'A' : , 'B' : , 'C' : , 'D' : , 'E' : , 'F' : , 'G' : , 'H' : , 'S' : }
notera: Denna adjacency lista kan matas in från användaren och behöver inte vara hårdkodade.
nu kommer vi att definiera vår DFS – funktion som tar in 3 parametrar som inmatning-grafen (adjacency list), en nod och en lista över besökta noder.
om den aktuella noden inte besöks, dvs inte finns i den besökta listan, markera den som besökt och Lägg till den i den besökta listan.
flytta till nästa nod och skicka sedan denna nod rekursivt till DFS-funktionen. På så sätt flyttar varje nod till djupet och skriver ut det som DFS-utgången.
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)
komplett kod och utgång
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)
utgången från ovanstående kod är som följer:
slutsats
jag hoppas att du har följt denna handledning på DFS-algoritmen och har kunnat förstå koden och exemplet också. Prova det med penna och papper bredvid dig för att förstå traversalerna bättre.