breadth first search c program traverse graph
Acest tutorial acoperă prima căutare a lățimii în C ++ în care graficul sau arborele este parcurs în sens larg. Veți învăța, de asemenea, algoritmul și implementarea BFS:
Acest tutorial explicit C ++ vă va oferi o explicație detaliată a tehnicilor de traversare care pot fi efectuate pe un copac sau pe un grafic.
Traversal este tehnica prin care vizităm fiecare nod al graficului sau al unui copac. Există două metode standard de traversări.
- Căutare în lățime (BFS)
- Căutare în profunzime (DFS)
=> Consultați aici pentru a explora lista completă de tutoriale C ++.
bun descărcător de muzică gratuit pentru Android
Ce veți învăța:
Tehnica Breadth First Search (BFS) în C ++
În acest tutorial, vom discuta în detaliu despre tehnica de căutare pe lățime.
În tehnica de traversare a lățimii, graficul sau arborele este parcurs în funcție de lățime. Această tehnică folosește structura de date a cozii pentru a stoca vârfurile sau nodurile și, de asemenea, pentru a determina care vârf / nod ar trebui să fie preluat în continuare.
Primul algoritm de lățime începe cu nodul rădăcină și apoi traversează toate nodurile adiacente. Apoi, selectează cel mai apropiat nod și explorează toate celelalte noduri nevizitate. Acest proces se repetă până când sunt explorate toate nodurile din grafic.
Algoritm de căutare a lățimii
Dat mai jos este algoritmul pentru tehnica BFS.
Luați în considerare G ca un grafic pe care îl vom parcurge folosind algoritmul BFS.
Fie S nodul rădăcină / de pornire al graficului.
- Pasul 1: Începeți cu nodul S și puneți-l în coadă.
- Pasul 2: Repetați pașii următori pentru toate nodurile din grafic.
- Pasul 3: Scoateți S și procesați-l.
- Pasul 4: Strângeți toate nodurile adiacente ale lui S și procesați-le.
- (END OF LOOP)
- Pasul 6: IEȘIRE
Pseudo cod
Pseudo-codul pentru tehnica BFS este dat mai jos.
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. endTraversări cu ilustrații
Fie 0 nodul de pornire sau nodul sursă. Mai întâi, îl punem în coadă în coada vizitată și în toate nodurile adiacente din coadă.
Apoi, luăm unul dintre nodurile adiacente pentru a procesa, adică 1. îl marcăm ca vizitat eliminându-l din coadă și punem nodurile adiacente în coadă (2 și 3 deja în coadă). Deoarece 0 este deja vizitat, îl ignorăm.
qa testarea întrebărilor și răspunsurilor la interviu pentru cei cu experiență
Apoi, scoatem coada nodului 2 și îl marcăm ca vizitat. Apoi, nodul său adiacent 4 este adăugat la coadă.
Apoi, scoatem 3 din coadă și îl marcăm ca vizitat. Nodul 3 are un singur nod adiacent, adică 0 care este deja vizitat. Prin urmare, îl ignorăm.
În acest stadiu, doar nodul 4 este prezent în coadă. Nodul său 2 adiacent este deja vizitat, de aceea îl ignorăm. Acum notăm 4 ca vizitate.
Apoi, secvența prezentă în lista vizitată este prima lățime a graficului dat.
Dacă observăm graficul dat și secvența de traversare, putem observa că, pentru algoritmul BFS, traversăm graficul în funcție de latitudine și apoi trecem la nivelul următor.
Implementarea 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): '< Ieșire:
diferența dintre testarea sarcinii și testarea performanței
Breadth-First Traversal pentru graficul dat (cu 0 ca nod de pornire):
0 1 2 3 4
Am implementat BFS în programul de mai sus. Rețineți că graficul este sub forma unei liste de adiacență și apoi folosim un iterator pentru a itera prin listă și pentru a efectua BFS.
Am folosit același grafic pe care l-am folosit în scopuri ilustrative ca intrare în program pentru a compara secvența de traversare.
Analiza Runtime
Dacă V este numărul de vârfuri și E este numărul de muchii ale unui grafic, atunci complexitatea timpului pentru BFS poate fi exprimată ca O (| V | + | E |) . Acestea fiind spuse, depinde și de structura datelor pe care o folosim pentru a reprezenta graficul.
Dacă folosim lista de adiacențe (ca în implementarea noastră), atunci complexitatea timpului este O (| V | + | E |).
Dacă folosim matricea de adiacență, atunci complexitatea timpului este O (V ^ 2) .
În afară de structurile de date utilizate, există și un factor dacă graficul este dens populat sau slab populat.
Când numărul de vârfuri depășește numărul de muchii, atunci se spune că graficul este slab conectat, deoarece vor exista multe vârfuri deconectate. În acest caz, complexitatea în timp a graficului va fi O (V).
Pe de altă parte, uneori graficul poate avea un număr mai mare de muchii decât numărul de vârfuri. Într-un astfel de caz, se spune că graficul este dens populat. Complexitatea timpului unui astfel de grafic este O (E).
În concluzie, ceea ce înseamnă expresia O (| V | + | E |) este în funcție de faptul dacă graficul este dens sau slab populat, factorul dominant, adică muchiile sau vârfurile, va determina complexitatea timpului graficului în consecință.
Aplicații ale BFS Traversal
- Colectarea gunoiului: Tehnica de colectare a gunoiului, „algoritmul lui Cheney” folosește prima traversare a lățimii pentru copierea colectării gunoiului.
- Difuzarea în rețele: Un pachet călătorește de la un nod la altul folosind tehnica BFS din rețeaua de difuzare pentru a ajunge la toate nodurile.
- Navigare GPS: Putem folosi BFS în navigarea GPS pentru a găsi toate nodurile de locație adiacente sau învecinate.
- Site-uri de rețele sociale: Având în vedere o persoană „P”, putem găsi toți oamenii la distanță, „d” de la p folosind BFS până la nivelurile d.
- Rețele de la egal la egal: Din nou, BFS poate fi utilizat în rețelele de la egal la egal pentru a găsi toate nodurile adiacente.
- Cea mai scurtă cale și arborele minim de întindere din graficul neponderat: Tehnica BFS este utilizată pentru a găsi cea mai scurtă cale, adică calea cu cel mai mic număr de margini în graficul neponderat. În mod similar, putem găsi, de asemenea, un copac minim care se întinde utilizând BFS în graficul neponderat.
Concluzie
Prima tehnică de căutare în lățime este o metodă care este utilizată pentru a traversa toate nodurile unui grafic sau a unui copac într-o manieră largă.
Această tehnică este folosită mai ales pentru a găsi cea mai scurtă cale între nodurile unui grafic sau în aplicații care necesită să vizităm fiecare nod adiacent, cum ar fi în rețele.
=> Faceți clic aici pentru cursul gratuit C ++.
Lectură recomandată
- Arborele de căutare binară C ++: Implementarea și operațiile BST cu exemple
- Structura de date B Tree și B + Tree în C ++
- Implementarea graficului în C ++ folosind lista Adjacency
- Structura de date a arborelui binar în C ++
- Cele mai bune 12 instrumente de creare a graficelor de linii pentru crearea graficelor de linii uimitoare (CLASAMENTE 2021)
- Arborele AVL și structura de date Heap în C ++
- Copaci în C ++: terminologie de bază, tehnici transversale și tipuri de arbori C ++
- Grafic de cauză și efect - Tehnică dinamică de scriere a cazurilor de testare pentru o acoperire maximă cu mai puține cazuri de testare