breadth first search c program traverse graph
Ovaj vodič obuhvaća prvo pretraživanje širine u jeziku C ++ u kojem se grafikon ili stablo prelazi u širinu. Također ćete naučiti BFS algoritam i implementaciju:
Ovaj eksplicitni tutorial za C ++ dat će vam detaljno objašnjenje tehnika prelaska koje se mogu izvesti na stablu ili grafu.
Prelazak je tehnika pomoću koje posjećujemo svaki čvor grafa ili stabla. Postoje dvije standardne metode prelaska.
- Pretraživanje u širini (BFS)
- Dubinsko prvo pretraživanje (DFS)
=> Pogledajte ovdje kako biste istražili cjeloviti popis vodiča za C ++.
testirajte web stranicu u različitim preglednicima besplatno
Što ćete naučiti:
Tehnika pretraživanja širine (BFS) na C ++
U ovom uputstvu detaljno ćemo razmotriti tehniku pretraživanja po širini.
U tehnici prijelaza u širinu, grafikon ili stablo prelazi se u širinu. Ova tehnika koristi strukturu podataka o redu za pohranu vrhova ili čvorova i također za određivanje kojeg vrha / čvora treba sljedeći.
Širina algoritma započinje s korijenskim čvorom, a zatim prelazi sve susjedne čvorove. Zatim odabire najbliži čvor i istražuje sve ostale ne posjećene čvorove. Taj se postupak ponavlja dok se ne istraže svi čvorovi na grafikonu.
Širina-prvi algoritam pretraživanja
Dolje je dan algoritam za BFS tehniku.
Smatrajte G grafom koji ćemo preći pomoću BFS algoritma.
Neka je S korijenski / početni čvor grafa.
- Korak 1: Počnite s čvorom S i stavite ga u red čekanja.
- Korak 2: Ponovite sljedeće korake za sve čvorove na grafikonu.
- Korak 3: Dequeue S i obraditi.
- Korak 4: Stavite u red sve susjedne čvorove S i obradite ih.
- (KRAJ petlje)
- Korak 6: IZLAZ
Pseudokod
Pseudo-kôd za BFS tehniku dan je u nastavku.
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. endPutovanja s ilustracijama
Neka 0 bude početni čvor ili izvorni čvor. Prvo ga stavljamo u red za posjete i sve susjedne čvorove u redu.
Dalje, uzimamo jedan od susjednih čvorova za obradu, tj. 1. Označavamo ga kao posjećen uklanjanjem iz reda i stavljanje susjednih čvorova u red (2 i 3 već u redu). Kako je 0 već posjećeno, zanemarujemo ga.
kako pokrenuti .swf
Zatim čvor 2 uklanjamo iz redova i označavamo ga kao posjećen. Zatim se susjedni čvor 4 dodaje u red čekanja.
Dalje uklanjamo red 3 iz reda i označavamo ga kao posjećen. Čvor 3 ima samo jedan susjedni čvor, tj. 0 koji je već posjećen. Stoga ga zanemarujemo.
U ovoj je fazi u redu samo čvor 4. Njegov susjedni čvor 2 već je posjećen, stoga ga zanemarujemo. Sada označavamo 4 kao posjećene.
Dalje, slijed prisutan na posjećenom popisu prijelaz je širine zadanog grafa.
Ako promatramo zadani graf i redoslijed prelaska, možemo primijetiti da za BFS algoritam zaista prelazimo graf u širini i prelazimo na sljedeću razinu.
Implementacija BFS-a
#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): '< Izlaz:
što je deque c ++
Prijelaz širina-prvo za zadani graf (s 0 kao početni čvor):
0 1 2 3 4
Implementirali smo BFS u gore navedeni program. Imajte na umu da je graf u obliku popisa susjednosti, a zatim koristimo iterator za itiranje kroz popis i izvođenje BFS-a.
Koristili smo isti graf koji smo koristili u ilustracijske svrhe kao ulaz u program za usporedbu redoslijeda prelaska.
Analiza vremena izvođenja
Ako je V broj vrhova, a E broj bridova grafa, tada se vremenska složenost za BFS može izraziti kao O (| V | + | E |) . Rekavši to, ovisi i o strukturi podataka koju koristimo za predstavljanje grafa.
Ako koristimo popis susjednosti (kao u našoj provedbi), tada je vremenska složenost O (| V | + | E |).
Ako koristimo matricu susjedstva, tada je vremenska složenost O (V ^ 2) .
Osim korištenih struktura podataka, postoji i faktor je li graf gusto naseljen ili rijetko popunjen.
Kada broj vrhova premaši broj bridova, tada se kaže da je graf rijetko povezan jer će biti mnogo nepovezanih vrhova. U ovom će slučaju vremenska složenost grafa biti O (V).
S druge strane, ponekad grafikon može imati veći broj bridova od broja vrhova. U takvom slučaju kaže se da je graf gusto naseljen. Složenost vremena takvog grafa je O (E).
Da zaključimo, što znači izraz O (| V | + | E |), ovisno o tome je li graf gusto ili rijetko naseljen, dominirajući faktor tj. Rubovi ili vrhovi odredit će vremensku složenost grafa u skladu s tim.
Primjene BFS prelaska
- Kolekcija smeća: Tehnika odvoza smeća, 'Cheneyev algoritam', koristi preslikavanje u širinu za kopiranje odvoza smeća.
- Emitiranje u mrežama: Paket putuje od jednog do drugog čvora pomoću BFS tehnike u radiodifuznoj mreži da bi dosegao sve čvorove.
- GPS navigacija: BFS možemo koristiti u GPS navigaciji kako bismo pronašli sve susjedne ili susjedne čvorove lokacije.
- Web stranice o društvenim mrežama: S obzirom na osobu „P“, možemo pronaći sve ljude na udaljenosti, „d“ od p koristeći BFS do d razine.
- Peer to Peer mreže: Opet se BFS može koristiti u ravnopravnim mrežama za pronalaženje svih susjednih čvorova.
- Najkraći put i minimalno rasponično stablo u neuvažanom grafikonu: BFS tehnika koristi se za pronalaženje najkraće putanje, tj. Putanje s najmanjim brojem bridova u neuvažanom grafu. Slično tome, također možemo pronaći stablo minimalnog raspona pomoću BFS-a u ne-ponderiranom grafikonu.
Zaključak
Tehnika pretraživanja u širinu je metoda koja se koristi za prelazak svih čvorova grafa ili stabla na širinu.
Ova se tehnika uglavnom koristi za pronalaženje najkraćeg puta između čvorova grafa ili u aplikacijama koje zahtijevaju da posjetimo svaki susjedni čvor kao u mrežama.
=> Kliknite ovdje za besplatni tečaj C ++.
Preporučena literatura
- Binarno stablo pretraživanja C ++: Implementacija BST-a i operacije s primjerima
- Struktura podataka stabla B i stabla B + u jeziku C ++
- Implementacija grafikona u C ++ pomoću popisa susjedstva
- Struktura podataka binarnog stabla u C ++
- 12 najboljih alata za izradu linijskih grafova za stvaranje zapanjujućih linijskih grafova (2021 RANGING)
- Struktura podataka AVL stabla i hrpe u C ++
- Stabla u C ++: Osnovna terminologija, tehnike prelaska i tipovi stabala C ++
- Grafikon uzroka i posljedica - Tehnika pisanja dinamičkih test slučajeva za maksimalno pokriće s manje test slučajeva