Meni

Poglobljeno iskanje (DFS) Program C ++ za prehod grafa ali drevesa

  • Glavni
  • Drugo
  • Poglobljeno iskanje (DFS) Program C ++ za prehod grafa ali drevesa

depth first search c program traverse graph

Preizkusite Naš Instrument Za Odpravo Težav

Ta vadnica zajema iskanje po globini (DFS) v jeziku C ++, v katerem se graf ali drevo prečka globinsko. Naučili se boste tudi algoritma DFS in implementacije:

Iskanje po globini (DFS) je še ena tehnika, ki se uporablja za prehod drevesa ali grafa.

DFS se začne s korenskim vozliščem ali začetnim vozliščem in nato razišče sosednja vozlišča trenutnega vozlišča tako, da gre globlje v graf ali drevo. To pomeni, da se v DFS vozlišča raziskujejo poglobljeno, dokler ne naleti vozlišče brez otrok.

Ko dosežemo listno vozlišče, se DFS vrne nazaj in začne na podoben način raziskovati še nekaj vozlišč.

=> Tukaj bodite pozorni na vodnik za usposabljanje za začetnike C ++.

Iskanje po globini

Kaj se boste naučili:

Globinsko prvo iskanje (DFS) v C ++

Za razliko od BFS, v katerem vozlišča raziskujemo v širini, pri DFS vozlišča raziskujemo poglobljeno. V DFS uporabljamo podatkovno strukturo skladov za shranjevanje vozlišč, ki jih raziskujemo. Robovi, ki nas vodijo do neraziskanih vozlišč, se imenujejo 'robovi odkrivanja', robovi, ki vodijo do že obiskanih vozlišč, pa 'blokirani robovi'.

Nato bomo videli algoritem in psevdo-kodo za tehniko DFS.

DFS algoritem

  • Korak 1: V sklad vstavite korensko vozlišče ali začetno vozlišče drevesa ali grafa.
  • 2. korak: Odprite zgornji element iz sklada in ga dodajte na obiskani seznam.
  • 3. korak: Poiščite vsa sosednja vozlišča vozlišča, ki so označena kot obiskana, in dodajte tista, ki še niso bila obiskana, v sklad.
  • 4. korak : Ponavljajte koraka 2 in 3, dokler se sklad ne izprazni.

Psevkodo

Psevdo-koda za DFS je podana spodaj.

Psevdo-koda za DFS

Iz zgornje psevdo-kode opazimo, da je algoritem DFS poklican rekurzivno na vsaki točki, da se zagotovi obisk vseh točk.

Prehodi z ilustracijami

Poglejmo zdaj DFS prehod grafa. Zaradi jasnosti bomo uporabili isti graf, kot smo ga uporabili na ilustraciji BFS.

DFS ilustracije s prečnicami

Naj bo 0 začetno vozlišče ali izvorno vozlišče. Najprej jo označimo kot obiskano in jo dodamo na seznam obiskanih. Nato potisnemo vsa sosednja vozlišča v sklad.

Potisnite vsa sosednja vozlišča v sklad

Nato vzamemo eno od sosednjih vozlišč za obdelavo, tj. Vrh sklada, ki je 1. Označimo ga kot obiskanega, tako da ga dodamo na seznam obiskanih. Zdaj poiščite sosednja vozlišča 1. Ker je 0 že na obiskanem seznamu, ga prezremo in obiščemo 2, ki je vrh sklada.

Ilustracija DFS - 3. korak

Nato vozlišče 2 označimo kot obiskano. Njeno sosednje vozlišče 4 je dodano v sklad.

DFS ilustracija 4. korak

Nato označimo 4, ki je vrh sklada, kot smo ga obiskali. Vozlišče 4 ima samo sosednje vozlišče 2, ki je že obiskano, zato ga ignoriramo.

DFS ilustracija 5. korak

Na tej stopnji je v svežnju prisotno le vozlišče 3. Sosednje vozlišče 0 je že obiskano, zato ga prezremo. Zdaj označujemo 3 kot obiskane.

DFS ilustracija 6. korak

Zdaj je kup prazen, obiskani seznam pa prikazuje zaporedje prečka globine prvega grafa.

Če opazujemo dani graf in zaporedje prečkanja, opazimo, da za algoritem DFS res prehodimo graf po globini in ga nato znova sledimo, da raziščemo nova vozlišča.

Izvajanje iskanja po globini

Izvedimo tehniko prečkanja DFS s pomočjo 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:'<

Izhod:

Prehod globine prvi za dani graf:

0 1 2 4 3

Graf smo ponovno uporabili v programu, ki smo ga uporabili za ponazoritev. Vidimo, da se algoritem DFS (ločen na dve funkciji) rekurzivno pokliče na vsaki točki v grafu, da se zagotovi obisk vseh točk.

Analiza med izvajanjem

Časovna zapletenost DFS je enaka BFS, tj. O (| V | + | E |) kjer je V število oglišč in E število robov v danem grafu.

Podobno kot pri BFS bodo tudi pri izračunu časovne kompleksnosti prevladujoči dejavnik vertikli oziroma robovi, odvisno od tega, ali je graf redko poseljen ali gosto poseljen.

Ponavljajoči DFS

Zgoraj prikazana izvedba tehnike DFS je rekurzivne narave in uporablja sklad funkcijskih klicev. Imamo še eno različico za izvajanje DFS, tj. ' Iterativno globinsko iskanje '. Pri tem uporabljamo eksplicitni sklad za zadrževanje obiskanih točk.

Spodaj smo prikazali izvajanje iterativnega DFS. Upoštevajte, da je izvedba enaka kot BFS, razen dejavnika, da namesto čakalne vrste uporabljamo strukturo podatkovnega sklada.

#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; }

Izhod:

Rezultat ponovitve globoko prvi prehod:

0 3 2 4 1

Uporabljamo isti graf, kot smo ga uporabili pri rekurzivni izvedbi. Razlika v izhodu je zato, ker pri iterativni izvedbi uporabljamo sklad. Ker skladi sledijo vrstnemu redu LIFO, dobimo drugačno zaporedje DFS. Če želimo dobiti isto zaporedje, bomo morda želeli vstaviti točke v obratnem vrstnem redu.

BFS vs DFS

Do zdaj smo razpravljali o obeh tehnikah prečkanja grafov, tj. BFS in DFS.

Zdaj pa poglejmo razlike med obema.

BFSDFS
Stojala za iskanje po širiniStojalo za 'iskanje po globini'
Vozlišča se preučujejo po širini po stopnjah.Vozlišča se preiskujejo poglobljeno, dokler ne obstajajo samo vozlišča listov, nato pa se jih potegne nazaj za raziskovanje drugih neobiskanih vozlišč.
BFS se izvede s pomočjo strukture podatkov čakalne vrste.DFS se izvede s pomočjo strukture podatkovnih skladov.
Počasnejše delovanje.Hitreje kot BFS.
Uporabno pri iskanju najkrajše poti med dvema vozliščema.Uporablja se večinoma za zaznavanje ciklov v grafih.

Aplikacije DFS

  • Odkrivanje ciklov v grafu: Če med izvajanjem DFS v grafu najdemo zadnji rob, lahko ugotovimo, da ima graf cikel. Zato se DFS uporablja za zaznavanje ciklov v grafu.
  • Iskanje poti: Glede na dve točki x in y lahko s pomočjo DFS najdemo pot med x in y. Začnemo z ogliščem x in nato potisnemo vse oglišča na poti do sklada, dokler ne naletimo na y. Vsebina sklada poda pot med x in y.
  • Najmanjše drevo in najkrajša pot: DFS prehod neuteženega grafa nam daje najmanjše raztezajoče se drevo in najkrajšo pot med vozlišči.
  • Topološko razvrščanje: Topološko razvrščanje uporabljamo, ko moramo razporejati opravila iz danih odvisnosti med opravili. Na področju računalništva ga uporabljamo predvsem za reševanje odvisnosti simbolov v povezovalcih, serializacijo podatkov, razporejanje navodil itd. DFS se pogosto uporablja pri topološkem razvrščanju.

Zaključek

V zadnjih nekaj vajah smo raziskali več o dveh tehnikah prečkanja grafov, tj. BFS in DFS. Videli smo razlike, pa tudi uporabe obeh tehnik. BFS in DFS v bistvu dosežeta enak rezultat obiska vseh vozlišč grafa, vendar se razlikujejo po vrstnem redu izhodnih podatkov in načinu, kako je to storjeno.

Opazili smo tudi izvajanje obeh tehnik. Medtem ko BFS uporablja čakalno vrsto, DFS za uporabo tehnike uporablja sklade. S tem zaključujemo vajo o tehnikah prečkanja grafov. Na drevesih lahko uporabimo tudi BFS in DFS.

levi spoj proti levemu zunanjemu spoju

Več o zajemanju dreves in nekaj algoritmih za iskanje najkrajše poti med vozlišči grafa bomo izvedeli v naši prihajajoči vadnici.

=> Za ogled celotnega seznama vadnic za C ++ glejte tukaj.

Priporočeno branje

^