Menu

Programma C ++ Breadth First Search (BFS) per attraversare un grafico o un albero

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

breadth first search c program traverse graph

Prova Il Nostro Strumento Per Eliminare I Problemi

Questo tutorial tratta la ricerca di ampiezza prima in C ++ in cui il grafico o l'albero viene attraversato in larghezza. Imparerai anche l'algoritmo e l'implementazione BFS:

Questo tutorial esplicito in C ++ ti darà una spiegazione dettagliata delle tecniche di attraversamento che possono essere eseguite su un albero o su un grafico.

Traversal è la tecnica con la quale visitiamo ogni singolo nodo del grafo o albero. Esistono due metodi standard di attraversamento.

  • Ricerca in ampiezza (BFS)
  • Ricerca in profondità (DFS)

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

differenza tra codice c e c ++

Ricerca ampia in C ++

Cosa imparerai:

Tecnica BFS (Breadth First Search) in C ++

In questo tutorial, discuteremo in dettaglio la tecnica di ricerca in ampiezza.

Nella tecnica di attraversamento della larghezza prima, il grafo o l'albero viene attraversato in senso di larghezza. Questa tecnica utilizza la struttura dei dati della coda per memorizzare i vertici o nodi e anche per determinare quale vertice / nodo dovrebbe essere occupato successivamente.

L'algoritmo di ampiezza inizia con il nodo radice e quindi attraversa tutti i nodi adiacenti. Quindi, seleziona il nodo più vicino ed esplora tutti gli altri nodi non visitati. Questo processo viene ripetuto fino a quando non vengono esplorati tutti i nodi nel grafico.

Algoritmo di ricerca in ampiezza

Di seguito è riportato l'algoritmo per la tecnica BFS.

Considera G come un grafico che attraverseremo usando l'algoritmo BFS.

Sia S la radice / nodo iniziale del grafo.

  • Passo 1: Inizia con il nodo S e accodalo alla coda.
  • Passo 2: Ripetere i passaggi seguenti per tutti i nodi nel grafico.
  • Passaggio 3: Dequeue S ed elaboralo.
  • Passaggio 4: Accoda tutti i nodi adiacenti di S ed elaborali.
  • (FINE DEL LOOP)
  • Passaggio 6: USCITA

Pseudocodice

Di seguito viene fornito lo pseudo codice per la tecnica BFS.

Procedure BFS (G, s) G is the graph and s is the source node begin let q be queue to store nodes q.enqueue(s) //insert source node in the queue mark s as visited. while (q is not empty) //remove the element from the queue whose adjacent nodes are to be processed n = q.dequeue( ) //processing all the adjacent nodes of n for all neighbors m of n in Graph G if w is not visited q.enqueue (m) //Stores m in Q to in turn visit its adjacent nodes mark m as visited. end

Traversate con illustrazioni

Illustrazioni BFS Fase 1

Sia 0 il nodo iniziale o il nodo sorgente. Per prima cosa, lo accodiamo nella coda visitata e tutti i suoi nodi adiacenti nella coda.

Illustrazioni BFS Fase 2

Successivamente, prendiamo uno dei nodi adiacenti per l'elaborazione, ad esempio 1. Lo contrassegniamo come visitato rimuovendolo dalla coda e mettiamo i suoi nodi adiacenti nella coda (2 e 3 già in coda). Poiché 0 è già visitato, lo ignoriamo.

chi ha il miglior servizio di posta elettronica

Illustrazioni BFS Fase 3

Successivamente, rimuoviamo dalla coda il nodo 2 e lo contrassegniamo come visitato. Quindi, il suo nodo adiacente 4 viene aggiunto alla coda.

Illustrazioni BFS Fase 4

Successivamente, ne rimuoviamo 3 dalla coda e lo contrassegniamo come visitato. Il nodo 3 ha un solo nodo adiacente, ovvero 0 che è già stato visitato. Quindi, lo ignoriamo.

Illustrazioni BFS Passaggio 5

In questa fase, solo il nodo 4 è presente nella coda. Il suo nodo adiacente 2 è già visitato, quindi lo ignoriamo. Ora contrassegniamo 4 come visitati.

Illustrazioni BFS Passaggio 6

Successivamente, la sequenza presente nella lista visitata è l'attraversamento in ampiezza del grafico dato.

Se osserviamo il grafico dato e la sequenza trasversale, possiamo notare che per l'algoritmo BFS, in effetti attraversiamo il grafico in larghezza e poi andiamo al livello successivo.

Implementazione di BFS

#include #include using namespace std; // a directed graph class class DiGraph { int V; // No. of vertices // Pointer to an array containing adjacency lists list *adjList; public: DiGraph(int V); // Constructor // add an edge from vertex v to w void addEdge(int v, int w); // BFS traversal sequence starting with s ->starting node void BFS(int s); }; DiGraph::DiGraph(int V) { this->V = V; adjList = new list (V); } void DiGraph::addEdge(int v, int w) { adjList(v).push_back(w); // Add w to v’s list. } void DiGraph::BFS(int s) { // initially none of the vertices is visited bool *visited = new bool(V); for(int i = 0; i queue; // Mark the current node as visited and enqueue it visited(s) = true; queue.push_back(s); // iterator 'i' to get all adjacent vertices list ::iterator i; while(!queue.empty()) { // dequeue the vertex s = queue.front(); cout << s << ' '; queue.pop_front(); // get all adjacent vertices of popped vertex and process each if not already visited for (i = adjList(s).begin(); i != adjList(s).end(); ++i) { if (!visited(*i)) { visited(*i) = true; queue.push_back(*i); } } } } // main program int main() { // create a graph DiGraph dg(5); dg.addEdge(0, 1); dg.addEdge(0, 2); dg.addEdge(0, 3); dg.addEdge(1, 2); dg.addEdge(2, 4); dg.addEdge(3, 3); dg.addEdge(4, 4); cout << 'Breadth First Traversal for given graph (with 0 as starting node): '<

Produzione:

protezione malware in tempo reale gratuita 2017

Breadth-First Traversal per il grafico dato (con 0 come nodo iniziale):

0 1 2 3 4

Abbiamo implementato BFS nel programma sopra. Nota che il grafico ha la forma di un elenco di adiacenza e quindi usiamo un iteratore per scorrere l'elenco ed eseguire BFS.

Abbiamo utilizzato lo stesso grafico che abbiamo utilizzato a scopo illustrativo come input per il programma per confrontare la sequenza di attraversamento.

Analisi runtime

Se V è il numero di vertici ed E è il numero di archi di un grafo, la complessità temporale per BFS può essere espressa come O (| V | + | E |) . Detto questo, dipende anche dalla struttura dati che utilizziamo per rappresentare il grafico.

Se usiamo l'elenco di adiacenza (come nella nostra implementazione), la complessità temporale è O (| V | + | E |).

Se usiamo la matrice di adiacenza, allora la complessità temporale è O (V ^ 2) .

Oltre alle strutture di dati utilizzate, c'è anche un fattore che determina se il grafico è densamente popolato o scarsamente popolato.

Quando il numero di vertici supera il numero di spigoli, si dice che il grafo sia scarsamente connesso poiché ci saranno molti vertici scollegati. In questo caso, la complessità temporale del grafico sarà O (V).

D'altra parte, a volte il grafo può avere un numero di bordi maggiore rispetto al numero di vertici. In tal caso, si dice che il grafico sia densamente popolato. La complessità temporale di un tale grafico è O (E).

Per concludere, il significato dell'espressione O (| V | + | E |) dipende dal fatto che il grafo sia densamente o scarsamente popolato, il fattore dominante, cioè i bordi o i vertici, determinerà la complessità temporale del grafo di conseguenza.

Applicazioni di BFS Traversal

  • Raccolta dei rifiuti: La tecnica di raccolta dei rifiuti, 'l'algoritmo di Cheney', utilizza l'attraversamento in ampiezza per copiare la raccolta dei rifiuti.
  • Trasmissione in rete: Un pacchetto viaggia da un nodo all'altro utilizzando la tecnica BFS nella rete di trasmissione per raggiungere tutti i nodi.
  • Navigazione GPS: Possiamo usare BFS nella navigazione GPS per trovare tutti i nodi di posizione adiacenti o vicini.
  • Siti di social network: Data una persona 'P', possiamo trovare tutte le persone a una distanza, 'd' da p utilizzando BFS fino ai livelli d.
  • Reti peer to peer: Anche in questo caso BFS può essere utilizzato nelle reti peer to peer per trovare tutti i nodi adiacenti.
  • Percorso più breve e albero di copertura minimo nel grafico non ponderato: La tecnica BFS viene utilizzata per trovare il percorso più breve, ovvero il percorso con il minor numero di bordi nel grafico non pesato. Allo stesso modo, possiamo anche trovare uno spanning tree minimo utilizzando BFS nel grafico non ponderato.

Conclusione

La tecnica di ricerca in ampiezza è un metodo che viene utilizzato per attraversare tutti i nodi di un grafo o di un albero in modo ampio.

Questa tecnica viene utilizzata principalmente per trovare il percorso più breve tra i nodi di un grafo o in applicazioni che richiedono di visitare ogni nodo adiacente come nelle reti.

=> Fare clic qui per il corso C ++ gratuito.

Lettura consigliata

^