DFS (Depth First Traversal) în structura datelor: ce este, comandă și aplicații

Înțeles DFS în Data Structure

DFS în Data Structure, cunoscut și sub denumirea de depth-first traversal, este un algoritm recursiv utilizat în principal pentru a căuta toate nodurile unei structuri de date grafice sau arbore. Traversarea este vizitarea fiecărui nod al unui grafic. Algoritmul începe de la nodul rădăcină (care poate fi un nod arbitrar ca nodul rădăcină dintr-un grafic) și merge cât de departe poate de-a lungul fiecărei ramuri înainte de a reveni.

Ideea este să începeți de la rădăcină sau nodul arbitrar și să păstrați nodul marcat. După aceasta, trebuie să vă mutați la nodul adiacent care este nemarcat și să continuați această buclă până când nu există niciun nod alăturat nemarcat. Apoi întoarceți-vă înapoi și examinați celelalte noduri care sunt nemarcate și traversați-le. Pasul final este imprimarea nodurilor din cale.

Algoritm

Formulați o funcție recursivă care va lua indexul nodului și o matrice vizitată.

1. Păstrați nodul curent marcat ca vizitat și apoi tipăriți-l.
2. Parcurgeți toate notele alăturate și cele nemarcate și apelați funcția recursivă cu indexul nodului adiacent.

Explorați cursurile noastre populare de inginerie software

Proprietăți

Analiza timpului și spațiului în DFS în Data Structure variază în funcție de domeniul său de aplicare. Teoretic, DFS este folosit în principal pentru a traversa un grafic întreg și necesită timp O(|V|+|E|) unde |V| reprezintă numărul de vârfuri și |E| prezintă numărul de muchii. Acest grafic este liniar.

În aceste aplicații, spațiul O(|V|) este folosit și ca ultimă soluție pentru a păstra teancul de vârfuri stocat pe calea de căutare și setul de vârfuri care sunt deja vizitate. Prin urmare, setarea limitelor de timp și spațiu este similară cu căutarea pe lățimea întâi. Aici, cei doi algoritmi utilizați sunt mai puțin dependenți de complexitatea lor și mai mult de diferitele caracteristici ale ordinelor vârfurilor produse de cei doi algoritmi.

Când vine vorba de aplicații ale DFS în Data Structure legate de domenii specifice, cum ar fi găsirea de soluții în web-crawling sau AI, graficul care necesită parcurgere ar putea fi prea substanțial pentru a fi vizitat în totalitate. În astfel de cazuri, căutarea este executată doar la o adâncime limitată; datorită resurselor finite, cum ar fi spațiul pe disc sau memoria. Structurile de date nu sunt utilizate de obicei pentru a urmări setul tuturor nodurilor vizitate anterior. O căutare efectuată la o adâncime limitată face ca timpul să fie liniar atunci când vine vorba de unitatea de muchii și vârfuri extinse.

Cu toate acestea, rețineți că acest număr nu are aceeași dimensiune ca întregul grafic, deoarece unele dintre vârfuri pot fi căutate de mai multe ori, iar altele nu.

În astfel de cazuri, DFS apelează și la metode euristice pentru selectarea unei ramuri mai promițătoare. În cele din urmă, atunci când limita de adâncime adecvată nu poate fi determinată, a priori, DFS de adâncire iterativă este aplicată în mod repetat printr-o secvență de limite de creștere.

Învață cursuri de dezvoltare software online de la cele mai bune universități din lume. Câștigați programe Executive PG, programe avansate de certificat sau programe de master pentru a vă accelera cariera.

Algoritmul de căutare în profunzime primul

Fiecare vârf al unui grafic într-o implementare standard DFS este împărțit în oricare dintre două categorii:

1. Nu a fost vizitat
2. Vizitat

Algoritmul este folosit pentru a identifica fiecare vârf și a le marca ca vizitat și, în același timp, pentru a evita ciclurile.

Iată cum funcționează algoritmul DFS:

1. Puneți orice vârf particular al graficului pe o stivă.
2. Elementul din partea de sus a stivei ar trebui adăugat la lista vizitată.
3. Faceți o listă cu nodurile adiacente acelui vârf și adăugați-le pe cele care nu sunt în lista vizitată în partea de sus a stivei.
4. Continuați să repetați pașii anteriori până când stiva se golește.

Comandă DFS

Ordinea vârfurilor: Există patru moduri de ordonare liniară a vârfurilor unui grafic sau arbore în DFS:

1. Lista vârfurilor aranjate cum au fost vizitate mai întâi de algoritmul DFS este cunoscută sub denumirea de precomandă. Este o modalitate concisă de a descrie progresul căutării.
2. Lista vârfurilor în ordinea în care au fost vizitate ultima dată de algoritm este cunoscută sub denumirea de post-ordonare.
3. Lista vârfurilor în ordinea opusă primei lor vizite este o pre-ordonare inversă. Prin urmare, nu trebuie confundat cu comanda post-comandă.
4. Lista vârfurilor în ordinea opusă ultimei lor vizite este o post-ordonare inversă. Nu trebuie confundat cu precomandă.

În plus, există o ordine în ordine și o ordine inversă pentru arborii binari.

Depth First Search sau DFS pentru un grafic

DFS pentru un grafic este aproape același cu DFS pentru un arbore. Singura diferență este că graficele pot avea cicluri, spre deosebire de copaci. Un nod poate fi vizitat de mai multe ori și pentru a evita procesarea nodului, se utilizează o matrice booleană vizitată.

Rezultatele unei căutări aprofundate

Căutarea pe primul loc în adâncime este mai ușor descrisă în termenii unui arbore care se întinde pe vârfurile la care sunt deja atinse în căutare. Pe baza acestui arbore care se întinde, marginile graficului original sunt împărțite în trei clase: marginile anterioare unde nodul arborelui este îndreptat către unul dintre descendenții săi, marginile din spate unde nodul este îndreptat către unul dintre strămoșii săi și marginile transversale. , care nu face nici una dintre funcțiile anterioare.

Aplicații ale primei traversări în adâncime (DFS)

Căutarea în profunzime este utilizată în următorii algoritmi ca element de bază:

• Căutarea componentelor care sunt conectate.
• Găsirea componentelor conectate cu 2 (vertex sau muchie).
• Găsirea punților graficului.
• Găsirea componentelor conectate cu 3 (vârf sau margine).
• Sortarea topologică.
• Găsirea componentelor care sunt puternic conectate.
• Aflarea dacă o specie este asemănătoare cu una sau alta specie dintr-un arbore filogenetic.
• Testarea planarității.
• Producerea de cuvinte pentru a determina setul limită al oricărui grup.
• Rezolvarea puzzle-urilor care au o singură soluție, cum ar fi labirinturile.
• Generația labirintului .
• Căutarea bi-conectivitate în grafice.

Pseudocod DFS și implementare în Python

Funcția init() este rulată pe fiecare nod din pseudocodul de mai jos pentru a se asigura că toate vârfurile sunt vizitate. Acest lucru este deosebit de important deoarece graficele pot avea diverse zone deconectate.

Iată pseudocodul:

DFS(G, u)

u.visited = adevărat

pentru fiecare v ∈ G.Adj[u]

dacă v.vizitat == fals

DFS(G,v)

init() {

Pentru fiecare u ∈ G

u.visited = fals

Pentru fiecare u ∈ G

DFS(G, u)

}

Iată implementarea DFS în Python:

grafic = {

'5': ['3′,'7'],

„2” : [„1”, „3”],

„6” : [„7”],

„3”: [],

„4” : [„6”],

„7”: []

}

vizitat = set()

def dfs(vizitat, grafic, nod):

dacă nodul nu este vizitat:

imprimare (nod)

visited.add(nod)

pentru vecinul din graf[nodul]:

dfs (vizitat, grafic, vecin)

print(„Acesta este DFS:”)

dfs(vizitat, grafic, „5”)

Ieșire:

Acesta este DFS: 5

Explorați cursurile noastre populare de inginerie software

Complexitatea Depth First Search

John Reif a explorat complexitatea computațională a Depth First Search. Pentru a fi precis, într-un grafic, faptul dat este G, fie O ordinea standard determinată de algoritmul DFS repetitiv. G reprezintă graficul, iar O reprezintă rezultatul de ordonare a algoritmului DFS redundant. Această ieșire este cunoscută sub denumirea de ordonare lexicografică DFS.

Concluzie

Scopul principal al algoritmului DFS este vizitarea fiecărui vârf care evită ciclurile din graficele țintă. Dacă doriți să vă implicați în implementări avansate ale operațiunilor de căutare sau operațiuni de comandă, ar trebui să vă gândiți cu siguranță să urmați un curs premium și holistic în Depth First Search și Data Structure.

upGrad are câteva cursuri DFS de top, cum ar fi Master of Science în Informatică și Specializare în Big Data .

Dacă vă străduiți să faceți următorul pas și căutați sfaturi de specialitate, upGrad Mentorship încearcă să vă ofere sesiuni individuale cu cei mai buni consilieri de carieră și experți din industrie.