Menu

Programma C ++ Depth First Search (DFS) per attraversare un grafico o un albero

  • Principale
  • Altro
  • Programma C ++ Depth First Search (DFS) per attraversare un grafico o un albero

depth first search c program traverse graph

Prova Il Nostro Strumento Per Eliminare I Problemi

Questo tutorial tratta la ricerca in profondità (DFS) in C ++ in cui un grafico o un albero viene attraversato in profondità. Imparerai anche l'algoritmo e l'implementazione di DFS:

La ricerca in profondità (DFS) è un'altra tecnica utilizzata per attraversare un albero o un grafo.

DFS inizia con un nodo radice o un nodo iniziale e quindi esplora i nodi adiacenti del nodo corrente approfondendo il grafico o un albero. Ciò significa che in DFS i nodi vengono esplorati in profondità fino a quando non viene rilevato un nodo senza figli.

Una volta raggiunto il nodo foglia, DFS esegue il backtrack e inizia a esplorare altri nodi in modo simile.

=> Guarda qui la guida di formazione per principianti C ++.

Prima ricerca in profondità

Cosa imparerai:

Depth First Search (DFS) in C ++

A differenza di BFS in cui esploriamo i nodi in larghezza, in DFS esploriamo i nodi in profondità. In DFS utilizziamo una struttura di dati dello stack per memorizzare i nodi esplorati. Gli spigoli che ci portano a nodi inesplorati sono chiamati 'spigoli di scoperta' mentre gli spigoli che portano a nodi già visitati sono chiamati 'spigoli di blocco'.

Successivamente, vedremo l'algoritmo e lo pseudo-codice per la tecnica DFS.

Algoritmo DFS

  • Passo 1: Inserire il nodo radice o il nodo iniziale di un albero o un grafico nello stack.
  • Passo 2: Estrai l'elemento in cima alla pila e aggiungilo all'elenco dei visitati.
  • Passaggio 3: Trova tutti i nodi adiacenti del nodo contrassegnato come visitato e aggiungi quelli non ancora visitati allo stack.
  • Passaggio 4 : Ripetere i passaggi 2 e 3 fino a quando la pila è vuota.

Pseudocodice

Di seguito è riportato lo pseudo codice per DFS.

Lo pseudo-codice per DFS

Dallo pseudo-codice sopra, notiamo che l'algoritmo DFS viene chiamato ricorsivamente su ogni vertice per garantire che tutti i vertici vengano visitati.

Traversate con illustrazioni

Illustriamo ora l'attraversamento DFS di un grafico. Per motivi di chiarezza, useremo lo stesso grafico che abbiamo usato nell'illustrazione BFS.

Illustrazioni DFS con attraversamenti

Sia 0 il nodo iniziale o il nodo sorgente. Innanzitutto, lo contrassegniamo come visitato e lo aggiungiamo all'elenco dei visitati. Quindi inseriamo tutti i suoi nodi adiacenti nello stack.

Spingi tutti i nodi adiacenti nello stack

Successivamente, prendiamo uno dei nodi adiacenti da elaborare, cioè la parte superiore dello stack che è 1. Lo contrassegniamo come visitato aggiungendolo all'elenco dei visitati. Ora cerca i nodi adiacenti di 1. Poiché 0 è già nella lista visitata, lo ignoriamo e visitiamo 2 che è in cima alla pila.

Illustrazione DFS - Passaggio 3

Successivamente, contrassegniamo il nodo 2 come visitato. Il suo nodo adiacente 4 viene aggiunto alla pila.

Illustrazione DFS Passaggio 4

Successivamente, contrassegniamo 4 che è la parte superiore della pila come visitata. Il nodo 4 ha come adiacente solo il nodo 2 che è già visitato, quindi lo ignoriamo.

Illustrazione DFS Passaggio 5

In questa fase, solo il nodo 3 è presente nello stack. Il suo nodo adiacente 0 è già visitato, quindi lo ignoriamo. Ora contrassegniamo 3 come visitati.

Illustrazione DFS Passaggio 6

Ora lo stack è vuoto e l'elenco visitato mostra la sequenza della traversata in profondità del grafico dato.

Se osserviamo il grafico dato e la sequenza di attraversamento, notiamo che per l'algoritmo DFS, in effetti attraversiamo il grafo in profondità e poi lo facciamo nuovamente indietro per esplorare nuovi nodi.

Implementazione della ricerca in primo luogo

Implementiamo la tecnica di attraversamento DFS utilizzando 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:'<

Produzione:

Prima traversata in profondità per il grafico dato:

0 1 2 4 3

Abbiamo utilizzato ancora una volta il grafico nel programma che abbiamo utilizzato a scopo illustrativo. Vediamo che l'algoritmo DFS (separato in due funzioni) viene chiamato ricorsivamente su ogni vertice del grafo in modo da garantire che tutti i vertici siano visitati.

Analisi runtime

La complessità temporale di DFS è la stessa di BFS, ovvero O (| V | + | E |) dove V è il numero di vertici ed E è il numero di archi in un dato grafo.

Simile a BFS, a seconda che il grafo sia scarsamente popolato o densamente popolato, il fattore dominante saranno rispettivamente i vertici o gli archi nel calcolo della complessità temporale.

DFS iterativo

L'implementazione mostrata in precedenza per la tecnica DFS è di natura ricorsiva e utilizza uno stack di chiamate di funzione. Abbiamo un'altra variante per l'implementazione di DFS, ovvero ' Ricerca iterativa in profondità '. In questo, usiamo lo stack esplicito per contenere i vertici visitati.

Di seguito è stata mostrata l'implementazione per DFS iterativo. Si noti che l'implementazione è la stessa di BFS tranne per il fatto che utilizziamo la struttura dati dello stack invece di una coda.

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

Produzione:

Output della prima traversata Iterative Depth:

0 3 2 4 1

Usiamo lo stesso grafico che abbiamo usato nella nostra implementazione ricorsiva. La differenza nell'output è perché usiamo lo stack nell'implementazione iterativa. Poiché gli stack seguono l'ordine LIFO, otteniamo una sequenza diversa di DFS. Per ottenere la stessa sequenza, potremmo voler inserire i vertici nell'ordine inverso.

BFS vs DFS

Finora abbiamo discusso entrambe le tecniche di attraversamento per i grafici, ovvero BFS e DFS.

Ora esaminiamo le differenze tra i due.

BFSDFS
Sta per 'Ampiezza prima ricerca'Sta per 'Depth-first search'
I nodi vengono esplorati in ampiezza livello per livello.I nodi vengono esplorati in profondità fino a quando non sono presenti solo nodi foglia e quindi vengono riportati indietro per esplorare altri nodi non visitati.
BFS viene eseguito con l'aiuto della struttura dei dati della coda.DFS viene eseguito con l'aiuto della struttura dei dati dello stack.
Più lento nelle prestazioni.Più veloce di BFS.
Utile per trovare il percorso più breve tra due nodi.Utilizzato principalmente per rilevare i cicli nei grafici.

Applicazioni di DFS

  • Rilevamento dei cicli nel grafico: Se troviamo un back edge durante l'esecuzione di DFS in un grafico, possiamo concludere che il grafico ha un ciclo. Quindi DFS viene utilizzato per rilevare i cicli in un grafico.
  • Pathfinding: Dati due vertici x e y, possiamo trovare il percorso tra x e y usando DFS. Iniziamo con il vertice x e poi spingiamo tutti i vertici verso lo stack finché non incontriamo y. Il contenuto dello stack fornisce il percorso tra x e y.
  • Spanning Tree minimo e percorso più breve: L'attraversamento DFS del grafo non pesato fornisce uno spanning tree minimo e un percorso più breve tra i nodi.
  • Ordinamento topologico: Usiamo l'ordinamento topologico quando dobbiamo pianificare i lavori dalle dipendenze date tra i lavori. Nel campo dell'informatica, lo usiamo principalmente per risolvere le dipendenze dei simboli nei linker, serializzazione dei dati, pianificazione delle istruzioni, ecc. DFS è ampiamente utilizzato nell'ordinamento topologico.

Conclusione

Nell'ultimo paio di tutorial, abbiamo esplorato di più sulle due tecniche di attraversamento per i grafici, ovvero BFS e DFS. Abbiamo visto le differenze e le applicazioni di entrambe le tecniche. BFS e DFS ottengono fondamentalmente lo stesso risultato di visitare tutti i nodi di un grafico ma differiscono nell'ordine dell'output e nel modo in cui viene eseguito.

Abbiamo anche visto l'implementazione di entrambe le tecniche. Mentre BFS utilizza una coda, DFS utilizza gli stack per implementare la tecnica. Con questo, concludiamo il tutorial sulle tecniche di attraversamento per i grafici. Possiamo anche usare BFS e DFS sugli alberi.

come scrivere css selector in selenio

Impareremo di più sugli spanning tree e un paio di algoritmi per trovare il percorso più breve tra i nodi di un grafico nel nostro prossimo tutorial.

=> Vedi qui per esplorare l'elenco completo dei tutorial C ++.

Lettura consigliata

^