dragi cititori, în acest articol vă voi prezenta conceptul de căutare în profunzime (DFS). Acesta este un concept grafic, care este o problemă comună în multe examene de codificare competitive. Deci, să ne uităm la crearea unei traversări DFS folosind Python.
cuprins
ce este adâncimea prima căutare?
căutarea în profunzime este un algoritm care folosește structura de date a stivei pentru a traversa grafice și arbori. Conceptul de adâncime-prima căutare provine din cuvântul „adâncime”. Arborele traversează până la adâncimea unei ramuri și apoi înapoi traversează restul nodurilor.
luați în considerare o „stivă” goală care conține nodurile vizitate pentru fiecare iterație. Sarcina noastră aici este următoarea:
- începeți de la nodul rădăcină și împingeți-l pe stivă.
- verificați dacă există noduri adiacente ale arborelui și selectați un nod.
- traversați întreaga ramură a nodului selectat și împingeți toate nodurile în stivă.
- la atingerea capătului unei ramuri (nu mai există noduri adiacente), adică nodul frunzei n, deplasați-vă înapoi cu un singur pas și căutați nodurile adiacente ale nodului N-1.
- dacă există noduri adiacente pentru nodul n-1, traversați acele ramuri și împingeți nodurile pe stivă.
conceptul de adâncime prima căutare ilustrat
să ne uităm în graficul nostru exemplu de mai jos:
a este nodul rădăcină. Deci, din moment ce A este vizitat, împingem acest lucru pe stivă.
Stack : A
să mergem la sucursala a-B. B nu este vizitat, așa că mergem la B și împingem B pe stivă.
Stack : A B
acum, am ajuns la capătul ramurii noastre A-B și ne mutăm la nodul N-1 Care este A. Ne vom uita acum la nodul adiacent al lui A care este S. vizitați S și împingeți-l pe stivă. Acum trebuie să traversați ramura S-C-D, până la adâncimea adică până la D și marcați S, C, D ca vizitat.
Stack: A B S C D
deoarece D nu are alte noduri adiacente, treceți înapoi la C și traversați ramura adiacentă E-H-G la adâncime și împingeți-le pe stivă.
Stack : A B S C D E H G
la atingerea D, există un singur nod adiacent, adică F, care nu este vizitat. Împingeți F și pe stivă.
Stack : A B S C D E H G F
această stivă în sine este traversarea DFS.
adâncime de codificare primul algoritm de căutare în Python
după cum trebuie să știți, există multe metode de reprezentare a unui grafic care este lista de adiacență și matricea de adiacență.
Deci, în exemplul următor, am definit o listă de adiacență pentru fiecare dintre nodurile din graficul nostru.
graph1 = { 'A' : , 'B' : , 'C' : , 'D' : , 'E' : , 'F' : , 'G' : , 'H' : , 'S' : }
notă: Această listă de adiacență poate fi introdusă de la utilizator și nu trebuie să fie codificată.
acum, vom defini funcția noastră DFS care ia în 3 parametri ca intrare – graficul (lista adiacenta), un nod, și o listă de noduri vizitate.
dacă nodul curent nu este vizitat, adică nu este prezent în lista vizitată, marcați-l ca vizitat și adăugați-l în lista vizitată.
treceți la următorul nod și apoi treceți recursiv acest nod în funcția DFS. În acest fel, fiecare nod se mișcă până la adâncime și îl imprimă ca ieșire DFS.
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)
Cod complet și ieșire
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)
ieșirea codului de mai sus este după cum urmează:
concluzie
sper că ați urmat acest tutorial despre algoritmul DFS și ați reușit să înțelegeți și Codul și exemplul. Încercați-l folosind stilou și hârtie lângă tine pentru a înțelege traversals mai bine.