Meni

Dubinsko prvo pretraživanje (DFS) C ++ program za prelazak preko grafa ili stabla

  • Glavni
  • Ostalo
  • Dubinsko prvo pretraživanje (DFS) C ++ program za prelazak preko grafa ili stabla

depth first search c program traverse graph

Ovaj priručnik pokriva dubinsko prvo pretraživanje (DFS) u C ++ u kojem se graf ili stablo prelazi u dubinu. Naučit ćete i DFS algoritam i implementaciju:

Dubinsko pretraživanje (DFS) još je jedna tehnika koja se koristi za prelazak stabla ili grafa.

DFS započinje s korijenskim čvorom ili početnim čvorom, a zatim istražuje susjedne čvorove trenutnog čvora ulazeći dublje u graf ili stablo. To znači da se u DFS-u čvorovi istražuju dubinski dok se ne naiđe na čvor bez djece.

kako otvoriti swf datoteke na sustavu Windows 7

Jednom kada se dođe do čvora lista, DFS se vraća i započinje istraživanje još nekih čvorova na sličan način.

=> Ovdje pripazite na Vodič za obuku za početnike C ++.

Dubinsko prvo pretraživanje

Što ćete naučiti:

Dubinsko prvo pretraživanje (DFS) u C ++

Za razliku od BFS-a u kojem čvorove istražujemo u širini, u DFS-u čvorove istražujemo dubinski. U DFS-u koristimo strukturu podataka steka za pohranu čvorova koji se istražuju. Rubovi koji nas vode do neistraženih čvorova nazivaju se 'rubovi otkrića', dok se rubovi koji vode do već posjećenih čvorova nazivaju 'rubovi blokova'.

Dalje, vidjet ćemo algoritam i pseudo-kôd za DFS tehniku.

DFS algoritam

  • Korak 1: U hrpu umetnite korijenski čvor ili početni čvor stabla ili grafa.
  • Korak 2: Otvorite gornju stavku iz snopa i dodajte je na posjećeni popis.
  • Korak 3: Pronađite sve susjedne čvorove čvora koji su označeni kao posjećeni i dodajte one koji još nisu posjećeni u stog.
  • 4. korak : Ponavljajte korake 2 i 3 dok se stog ne isprazni.

Pseudokod

Pseudo-kôd za DFS dan je u nastavku.

Pseudo-kôd za DFS

Iz gornjeg pseudo-koda primjećujemo da se algoritam DFS poziva rekurzivno na svakom vrhu da bi se osiguralo posjećivanje svih vrhova.

Putovanja s ilustracijama

Ilustrirajmo sada DFS-ov presjek grafa. Radi jasnoće koristit ćemo isti grafikon koji smo koristili na BFS ilustraciji.

DFS ilustracije s traverzama

Neka 0 bude početni čvor ili izvorni čvor. Prvo ga označavamo kao posjećeno i dodajemo na popis posjećenih. Zatim gurnemo sve njegove susjedne čvorove u stog.

Pritisnite sve susjedne čvorove u stogu

Zatim uzmemo jedan od susjednih čvorova za obradu, tj. Vrh stoga koji je 1. Označavamo ga kao posjećen dodavanjem na popis posjećenih. Sada potražite susjedne čvorove 1. Kako je 0 već na posjećenom popisu, zanemarujemo ga i posjećujemo 2 koji je vrh stoga.

DFS ilustracija - korak 3

Dalje, čvor 2 označavamo kao posjećen. Njegov susjedni čvor 4 dodaje se u stog.

DFS ilustracija 4. korak

Dalje, označavamo 4 koji je vrh stoga kao posjećen. Čvor 4 ima samo čvor 2 kao susjedni koji je već posjećen, stoga ga zanemarujemo.

DFS ilustracija 5. korak

U ovoj je fazi u hrpi prisutan samo čvor 3. Njegov susjedni čvor 0 već je posjećen, stoga ga zanemarujemo. Sada označavamo 3 kao posjećene.

DFS ilustracija 6. korak

Sad je stog prazan, a posjećeni popis prikazuje slijed prijelaza prema dubini zadanog grafa.

Ako promatramo zadani graf i redoslijed zaokretanja, primjećujemo da za algoritam DFS doista prelazimo graf u dubinu i zatim ga ponovno vraćamo za istraživanje novih čvorova.

Dubinska implementacija pretraživanja

Primijenimo tehniku ​​DFS prelaska pomoću C ++.

#include #include using namespace std; //graph class for DFS travesal class DFSGraph { int V; // No. of vertices list *adjList; // adjacency list void DFS_util(int v, bool visited[]); // A function used by DFS public: // class Constructor DFSGraph(int V) { this->V = V; adjList = new list[V]; } // function to add an edge to graph void addEdge(int v, int w){ adjList[v].push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal function }; void DFSGraph::DFS_util(int v, bool visited[]) { // current node v is visited visited[v] = true; cout << v << ' '; // recursively process all the adjacent vertices of the node list::iterator i; for(i = adjList[v].begin(); i != adjList[v].end(); ++i) if(!visited[*i]) DFS_util(*i, visited); } // DFS traversal void DFSGraph::DFS() { // initially none of the vertices are visited bool *visited = new bool[V]; for (int i = 0; i < V; i++) visited[i] = false; // explore the vertices one by one by recursively calling DFS_util for (int i = 0; i < V; i++) if (visited[i] == false) DFS_util(i, visited); } int main() { // Create a graph DFSGraph gdfs(5); gdfs.addEdge(0, 1); gdfs.addEdge(0, 2); gdfs.addEdge(0, 3); gdfs.addEdge(1, 2); gdfs.addEdge(2, 4); gdfs.addEdge(3, 3); gdfs.addEdge(4, 4); cout << 'Depth-first traversal for the given graph:'<

Izlaz:

Prelazak dubine za zadani graf:

0 1 2 4 3

Ponovno smo upotrijebili graf u programu koji smo koristili u ilustracijske svrhe. Vidimo da se algoritam DFS (odvojen u dvije funkcije) poziva rekurzivno na svakom vrhu u grafikonu kako bi se osiguralo posjećivanje svih vrhova.

Analiza vremena izvođenja

Vremenska složenost DFS-a jednaka je BFS-u tj. O (| V | + | E |) gdje je V broj vrhova, a E broj bridova u danom grafu.

Slično BFS-u, ovisno o tome je li graf rijetko popunjen ili gusto naseljen, dominantni čimbenik bit će vrhovi, odnosno rubovi u izračunu vremenske složenosti.

Iterativni DFS

Gore prikazana implementacija za DFS tehniku ​​rekurzivne je prirode i koristi se skupom poziva funkcija. Imamo još jednu varijaciju za implementaciju DFS-a, tj. ' Iterativno traženje dubine '. U tome koristimo eksplicitni stog za zadržavanje posjećenih vrhova.

U nastavku smo prikazali implementaciju iterativnog DFS-a. Imajte na umu da je implementacija ista kao BFS, osim faktora da koristimo strukturu podataka steka umjesto reda.

#include using namespace std; // graph class class Graph { int V; // No. of vertices list *adjList; // adjacency lists public: Graph(int V) //graph Constructor { this->V = V; adjList = new list[V]; } void addEdge(int v, int w) // add an edge to graph { adjList[v].push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal // utility function called by DFS void DFSUtil(int s, vector &visited); }; //traverses all not visited vertices reachable from start node s void Graph::DFSUtil(int s, vector &visited) { // stack for DFS stack dfsstack; // current source node inside stack dfsstack.push(s); while (!dfsstack.empty()) { // Pop a vertex s = dfsstack.top(); dfsstack.pop(); // display the item or node only if its not visited if (!visited[s]) { cout << s << ' '; visited[s] = true; } // explore all adjacent vertices of popped vertex. //Push the vertex to the stack if still not visited for (auto i = adjList[s].begin(); i != adjList[s].end(); ++i) if (!visited[*i]) dfsstack.push(*i); } } // DFS void Graph::DFS() { // initially all vertices are not visited vector visited(V, false); for (int i = 0; i < V; i++) if (!visited[i]) DFSUtil(i, visited); } //main program int main() { Graph gidfs(5); //create graph gidfs.addEdge(0, 1); gidfs.addEdge(0, 2); gidfs.addEdge(0, 3); gidfs.addEdge(1, 2); gidfs.addEdge(2, 4); gidfs.addEdge(3, 3); gidfs.addEdge(4, 4); cout << 'Output of Iterative Depth-first traversal: '; gidfs.DFS(); return 0; }

Izlaz:

Izlaz iz ponovljenog dubinskog prijelaza:

0 3 2 4 1

Koristimo isti graf koji smo koristili u našoj rekurzivnoj implementaciji. Razlika u izlazu je zato što u iterativnoj implementaciji koristimo stog. Kako stogovi slijede LIFO redoslijed, dobivamo drugačiji redoslijed DFS-a. Da bismo dobili isti slijed, možda bismo htjeli umetnuti vrhove obrnutim redoslijedom.

BFS vs DFS

Do sada smo razgovarali o tehnikama prijelaza za grafove, tj. BFS i DFS.

Pogledajmo sada razlike između njih dvoje.

BFSDFS
Znači za 'Širinu prije svega'Znači za 'Dubinsko pretraživanje prvo'
Čvorovi se istražuju po širini, razina po razina.Čvorovi se istražuju dubinski dok ne postoje samo čvorovi listova, a zatim se vraćaju unatrag da bi se istražili drugi ne posjećeni čvorovi.
BFS se izvodi uz pomoć strukture podataka reda.DFS se izvodi uz pomoć strukture podataka steka.
Sporije u izvedbi.Brži od BFS-a.
Korisno u pronalaženju najkraćeg puta između dva čvora.Koristi se uglavnom za otkrivanje ciklusa u grafikonima.

Primjene DFS-a

  • Otkrivanje ciklusa na grafikonu: Ako tijekom izvođenja DFS-a na grafikonu pronađemo stražnji rub, možemo zaključiti da graf ima ciklus. Stoga se DFS koristi za otkrivanje ciklusa u grafikonu.
  • Pronalaženje puta: S obzirom na dva vrha x i y, put između x i y možemo pronaći pomoću DFS-a. Počinjemo s vrhom x, a zatim guramo sve vrhove na putu do hrpe dok ne naiđemo na y. Sadržaj stoga daje put između x i y.
  • Najmanji raspon stabala i najkraći put: DFS obilazak neutegnutog grafa daje nam minimalno rasponično stablo i najkraći put između čvorova.
  • Topološko sortiranje: Topološko sortiranje koristimo kada trebamo rasporediti poslove iz zadanih ovisnosti među poslovima. U području računalnih znanosti koristimo ga uglavnom za rješavanje ovisnosti simbola u poveznicima, serializaciju podataka, raspoređivanje uputa itd. DFS se široko koristi u topološkom sortiranju.

Zaključak

U posljednjih nekoliko vodiča istražili smo više o dvije tehnike prelaska za grafikone, tj. BFS i DFS. Vidjeli smo razlike kao i primjene obje tehnike. BFS i DFS u osnovi postižu isti rezultat posjećivanja svih čvorova grafa, ali se razlikuju po redoslijedu izlaza i načinu na koji se to radi.

Također smo vidjeli primjenu obje tehnike. Dok BFS koristi red, DFS koristi stekove kako bi implementirao tehniku. Ovim zaključujemo tutorial o tehnikama prelaska grafova. Također možemo koristiti BFS i DFS na drveću.

Naučit ćemo više o obuhvaćanju stabala i nekoliko algoritama za pronalaženje najkraćeg puta između čvorova grafa u našem nadolazećem vodiču.

=> Pogledajte ovdje kako biste istražili cjeloviti popis vodiča za C ++.

Preporučena literatura

^