depth first search c program traverse graph
Aquest tutorial cobreix la cerca de profunditat (DFS) en C ++ en què es transmet un gràfic o un arbre a la profunditat. També aprendreu l'algorisme i la implementació de DFS:
La cerca en profunditat (DFS) és una altra tècnica que s’utilitza per recórrer un arbre o un gràfic.
DFS comença amb un node arrel o un node inicial i després explora els nodes adjacents del node actual aprofundint en el gràfic o en un arbre. Això significa que a DFS els nodes s’exploren en profunditat fins que es troba un node sense fills.
Un cop assolit el node fulla, DFS retrocedeix i comença a explorar alguns nodes més de manera similar.
=> Mireu aquí la guia de formació per a principiants C ++.
Què aprendreu:
Primera cerca de profunditat (DFS) a C ++
A diferència de BFS, en què explorem els nodes de manera amplada, en DFS explorem els nodes en profunditat. A DFS fem servir una estructura de dades de pila per emmagatzemar els nodes que s’estan explorant. Les vores que ens porten a nodes inexplorats s’anomenen «vores de descobriment», mentre que les vores que porten a nodes ja visitats s’anomenen «vores de blocs».
A continuació, veurem l'algorisme i el pseudocodi per a la tècnica DFS.
Algorisme DFS
- Pas 1: Inseriu el node arrel o el node inicial d'un arbre o un gràfic a la pila.
- Pas 2: Feu sortir l'element superior de la pila i afegiu-lo a la llista de visites.
- Pas 3: Cerqueu tots els nodes adjacents del node marcat com a visitat i afegiu-los a la pila.
- Pas 4 : Repetiu els passos 2 i 3 fins que la pila estigui buida.
Pseudocodi
A continuació es dóna el pseudocodi de DFS.
A partir del pseudocodi anterior, observem que l'algorisme DFS s'anomena recursivament a cada vèrtex per assegurar que es visiten tots els vèrtexs.
Traversals amb il·lustracions
Il·lustrem ara el recorregut DFS d'un gràfic. A efectes de claredat, utilitzarem el mateix gràfic que hem utilitzat a la il·lustració de BFS.
Sigui 0 el node inicial o el node font. En primer lloc, el marquem com a visitat i l’afegim a la llista de visites. A continuació, empenyem tots els seus nodes adjacents a la pila.
A continuació, agafem un dels nodes adjacents per processar, és a dir, la part superior de la pila que és 1. El marquem com a visitat afegint-lo a la llista de visites. Ara busqueu els nodes adjacents de 1. Com que 0 ja és a la llista de visites, l’ignorem i visitem 2, que és la part superior de la pila.
A continuació, marquem el node 2 com a visitat. El node adjacent 4 s’afegeix a la pila.
A continuació, marquem 4 que és la part superior de la pila tal com es va visitar. El node 4 només té el node 2 com a adjacent que ja es visita, per tant, l’ignorem.
En aquesta etapa, només el node 3 està present a la pila. El seu node adjacent 0 ja està visitat, de manera que l’ignorem. Ara marquem 3 com a visitades.
Ara la pila està buida i la llista visitada mostra la seqüència del recorregut de la primera profunditat del gràfic donat.
Si observem el gràfic donat i la seqüència de recorregut, observem que, per a l'algorisme DFS, realment recorrem el gràfic en profunditat i després el retrocedim per explorar nous nodes.
Implementació de la cerca de profunditat
Implantem la tècnica de travessia DFS mitjançant 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:'< Sortida:
Primer recorregut per la profunditat del gràfic donat:
0 1 2 4 3
Hem tornat a utilitzar el gràfic del programa que hem utilitzat per il·lustrar. Veiem que l’algorisme DFS (separat en dues funcions) s’anomena recursivament a cada vèrtex del gràfic per tal de garantir que es visiten tots els vèrtexs.
Anàlisi del temps d'execució
La complexitat temporal de DFS és la mateixa que BFS, és a dir. O (| V | + | E |) on V és el nombre de vèrtexs i E és el nombre d’arestes d’un gràfic donat.
De manera similar a BFS, segons si el gràfic està poc poblat o densament poblat, el factor dominant serà els vèrtexs o les arestes respectivament en el càlcul de la complexitat temporal.
DFS iteratiu
La implementació que es mostra anteriorment per a la tècnica DFS té un caràcter recursiu i utilitza una pila de trucades de funcions. Tenim una altra variació per implementar DFS, és a dir, ' Primera cerca iterativa de profunditat ”. En això, fem servir la pila explícita per mantenir els vèrtexs visitats.
A continuació, hem mostrat la implementació del DFS iteratiu. Tingueu en compte que la implementació és la mateixa que BFS, excepte el factor que fem servir l'estructura de dades de la pila en lloc d'una cua.
#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; } Sortida:
Sortida del primer recorregut de profunditat iterativa:
0 3 2 4 1
Utilitzem el mateix gràfic que hem utilitzat en la nostra implementació recursiva. La diferència de sortida es deu al fet que utilitzem la pila en la implementació iterativa. A mesura que les piles segueixen l’ordre LIFO, obtenim una seqüència diferent de DFS. Per obtenir la mateixa seqüència, potser voldríem inserir els vèrtexs en l'ordre invers.
BFS contra DFS
Fins ara hem discutit les tècniques de recorregut per a gràfics, és a dir, BFS i DFS.
Vegem ara les diferències entre els dos.
BFS DFS Indica per 'Primera cerca per amplada' Significa 'Cerca a la profunditat' Els nodes s’exploren amplitud nivell per nivell. Els nodes s’exploren en profunditat fins que només hi ha nodes de fulles i després es retrocedeix per explorar altres nodes no visitats. BFS es realitza amb l'ajut de l'estructura de dades de la cua. DFS es realitza amb l'ajut de l'estructura de dades de la pila. Rendiment més lent. Més ràpid que BFS. Útil per trobar el camí més curt entre dos nodes. S'utilitza principalment per detectar cicles en gràfics.
Aplicacions de DFS
- Detecció de cicles al gràfic: Si trobem una vora posterior mentre realitzem DFS en un gràfic, podem concloure que el gràfic té un cicle. Per tant, s’utilitza DFS per detectar els cicles d’un gràfic.
- Recorregut: Donats dos vèrtexs x i, podem trobar el camí entre x i y utilitzant DFS. Comencem amb el vèrtex x i després empenyem tots els vèrtexs cap a la pila fins que ens trobem amb y. El contingut de la pila dóna el camí entre x i y.
- Arbre d’abast mínim i camí més curt: El recorregut DFS del gràfic sense ponderació ens proporciona un arbre d’extensió mínim i el camí més curt entre nodes.
- Classificació topològica: Utilitzem l’ordenació topològica quan hem de programar les feines a partir de les dependències donades entre feines. En el camp de la informàtica, l’utilitzem principalment per resoldre dependències de símbols en enllaçadors, serialització de dades, programació d’instruccions, etc. DFS s’utilitza àmpliament en l’ordenació topològica.
Conclusió
En el darrer parell de tutorials, hem explorat més sobre les dues tècniques de recorregut per a gràfics, és a dir, BFS i DFS. Hem vist les diferències i les aplicacions de les dues tècniques. BFS i DFS bàsicament aconsegueixen el mateix resultat de visitar tots els nodes d'un gràfic, però difereixen en l'ordre de sortida i la forma en què es fa.
També hem vist la implementació d’ambdues tècniques. Mentre que BFS utilitza una cua, DFS fa ús de piles per implementar la tècnica. Amb això, conclouem el tutorial sobre tècniques de recorregut de gràfics. També podem utilitzar BFS i DFS en arbres.
què és un fitxer swf?
Aprendrem més sobre els arbres que abasten i un parell d’algoritmes per trobar el camí més curt entre els nodes d’un gràfic al nostre proper tutorial.
=> Vegeu aquí per explorar la llista completa de tutorials de C ++.
Lectura recomanada
- Programa C ++ de Breadth First Search (BFS) per recórrer un gràfic o un arbre
- Arbre de cerca binària C ++: implementació i operacions de BST amb exemples
- Estructura de dades d’arbre B i arbre B + en C ++
- Tutorials Eclipse en profunditat per a principiants
- Estructura de dades de l'arbre binari en C ++
- Implementació de gràfics a C ++ mitjançant la llista d’adjacències
- Arbre AVL i estructura de dades Heap a C ++
- 12 millors eines per crear gràfics de línies per crear gràfics de línies impressionants (CLASSIFICACIONS 2021)