djup första sökning eller djup första traversal är en rekursiv algoritm för att söka alla hörn av en graf eller träd datastruktur. Traversal innebär att du besöker alla noder i ett diagram.
djup första sökalgoritm
en standard DFS-implementering sätter varje vertex av grafen i en av två kategorier:
- besökte
- inte besökt
syftet med algoritmen är att markera varje vertex som besökt samtidigt som man undviker cykler.,
DFS-algoritmen fungerar enligt följande:
- börja med att sätta någon av grafens hörn ovanpå en stapel.
- ta det översta objektet i stapeln och lägg det till den besökta listan.
- skapa en lista över det vertex intilliggande noder. Lägg till de som inte finns i den besökta listan till toppen av stapeln.
- fortsätt upprepa steg 2 och 3 tills stapeln är tom.
djup första Sökexempel
Låt oss se hur djup första sökalgoritmen fungerar med ett exempel. Vi använder en oriktad graf med 5 hörn.,
vi börjar från vertex 0, DFS-algoritmen börjar genom att sätta den i den besökta listan och sätta alla dess intilliggande hörn i stapeln.
därefter besöker vi elementet längst upp i stacken dvs 1 och går till dess intilliggande noder. Eftersom 0 redan har besökts, besöker vi 2 istället.,
Vertex 2 har ett oönskat intilliggande vertex i 4, så vi lägger det till toppen av stapeln och besöker den.
Efter att vi besökt det sista elementet 3 har det inga oönskade intilliggande noder, så vi har slutfört grafens djup första Traversal.,
DFS Pseudocode (rekursiv implementering)
pseudokoden för DFS visas nedan. I init () – funktionen märker du att vi kör DFS-funktionen på varje nod. Detta beror på att grafen kan ha två olika bortkopplade delar så att vi täcker varje vertex, vi kan också köra DFS-algoritmen på varje nod.,
DFS(G, u) u.visited = true for each v ∈ G.Adj if v.visited == false DFS(G,v) init() { For each u ∈ G u.visited = false For each u ∈ G DFS(G, u)}
DFS-implementering i Python, Java och c/c++
koden för djupets första sökalgoritm med ett exempel visas nedan. Koden har förenklats så att vi kan fokusera på algoritmen snarare än andra detaljer.
komplexiteten i djup första sökning
DFS-algoritmens tidskomplexitet representeras i form avO(V + E), därV är antalet noder ochE är antalet kanter.
algoritmens rymd ärO(V).,
tillämpning av DFS-algoritm
- för att hitta sökvägen
- för att testa om grafen är bipartite
- för att hitta de starkt anslutna komponenterna i ett diagram
- för att upptäcka cykler i ett diagram