breadth first search c program traverse graph
Denne opplæringen dekker bredden første søk i C ++ der grafen eller treet er krysset bredden. Du vil også lære BFS algoritme og implementering:
Denne eksplisitte C ++ opplæringen vil gi deg en detaljert forklaring på traversal teknikker som kan utføres på et tre eller graf.
Traversal er teknikken der vi besøker hver eneste node i grafen eller et tre. Det er to standardmetoder for traversaler.
- Bredde-første-søk (BFS)
- Dybde-første søk (DFS)
=> Se her for å utforske hele C ++ opplæringslisten.
c ++ udefinert referanse til klassefunksjon
Hva du vil lære:
Breadth First Search (BFS) -teknikk i C ++
I denne opplæringen vil vi diskutere i detalj den bredeste første søketeknikken.
I den bredeste første traversale teknikken krysses grafen eller treet bredt. Denne teknikken bruker kødatastrukturen til å lagre toppunktene eller nodene og også for å bestemme hvilken toppunkt / node som skal tas opp neste.
Bredde-først-algoritmen starter med rotnoden og krysser deretter alle tilstøtende noder. Deretter velger den nærmeste node og utforsker alle de andre ubesøkte nodene. Denne prosessen gjentas til alle nodene i grafen er utforsket.
Bredde-første søkealgoritme
Nedenfor er algoritmen for BFS-teknikk.
Betrakt G som et diagram som vi skal krysse ved hjelp av BFS-algoritmen.
La S være rot- / startnoden i grafen.
- Trinn 1: Start med node S og sett den i køen.
- Steg 2: Gjenta følgende trinn for alle nodene i grafen.
- Trinn 3: Dequeue S og behandle den.
- Trinn 4: Begrens alle tilstøtende noder i S og behandle dem.
- (SLUTT AV LØKKEN)
- Trinn 6: EXIT
Pseudokode
Pseudokoden for BFS-teknikken er gitt nedenfor.
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. endGjennomganger med illustrasjoner
La 0 være startnoden eller kildenoden. Først legger vi den i den besøkte køen og alle tilstøtende noder i køen.
Deretter tar vi en av de tilstøtende nodene for å behandle, dvs. 1. Vi markerer den som besøkt ved å fjerne den fra køen og plassere de tilstøtende nodene i køen (2 og 3 allerede i kø). Ettersom 0 allerede er besøkt, ignorerer vi det.
hva er det beste gratis verktøyet for fjerning av skadelig programvare
Deretter dequeue vi node 2 og markerer den som besøkt. Deretter legges den tilstøtende noden 4 til køen.
Deretter dequeue 3 fra køen og merke den som besøkt. Node 3 har bare en tilstøtende node, dvs. 0 som allerede er besøkt. Derfor ignorerer vi det.
På dette stadiet er bare node 4 til stede i køen. Den tilstøtende noden 2 er allerede besøkt, derfor ignorerer vi den. Nå merker vi 4 som besøkt.
Deretter er sekvensen som er tilstede i den besøkte listen den første bredden av den gitte grafen.
Hvis vi observerer den gitte grafen og traversalsekvensen, kan vi legge merke til at vi for BFS-algoritmen faktisk krysser grafen bredt og deretter går til neste nivå.
BFS Implementering
#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): '< Produksjon:
hvordan du kjører en .swf-fil
Bredde-første gjennomgang for den gitte grafen (med 0 som startnode):
0 1 2 3 4
Vi har implementert BFS i programmet ovenfor. Merk at grafen er i form av en tilknytningsliste, og deretter bruker vi en iterator for å gjenta gjennom listen og utføre BFS.
Vi har brukt den samme grafen som vi brukte til illustrasjonsformål som en inngang til programmet for å sammenligne traversalsekvensen.
Runtime-analyse
Hvis V er antall hjørner og E er antall kanter i en graf, kan tidskompleksiteten for BFS uttrykkes som O (| V | + | E |) . Når det er sagt, avhenger det også av datastrukturen vi bruker for å representere grafen.
Hvis vi bruker nabolisten (som i implementeringen vår), er tidskompleksiteten O (| V | + | E |).
Hvis vi bruker tilknytningsmatrisen, er tidskompleksiteten O (V ^ 2) .
Bortsett fra datastrukturene som er brukt, er det også en faktor om grafen er tett befolket eller tynt befolket.
Når antall hjørner overstiger antall kanter, sies det at grafen er tynt forbundet, da det vil være mange frakoblede hjørner. I dette tilfellet vil tidskompleksiteten til grafen være O (V).
På den annen side kan grafen noen ganger ha et høyere antall kanter enn antall hjørner. I et slikt tilfelle sies grafen å være tett befolket. Tidskompleksiteten til en slik graf er O (E).
For å konkludere, hva uttrykket O (| V | + | E |) betyr, er avhengig av om grafen er tett eller tynt befolket, den dominerende faktoren, dvs. kanter eller hjørner, vil bestemme tidskompleksiteten til grafen tilsvarende.
Anvendelser av BFS Traversal
- Søppelsamling: Søppeloppsamlingsteknikken, 'Cheneys algoritme', bruker bredeste første traversal for kopiering av søppeloppsamling.
- Kringkasting i nettverk: En pakke reiser fra en node til en annen ved hjelp av BFS-teknikken i kringkastingsnettverket for å nå alle noder.
- GPS-navigasjon: Vi kan bruke BFS i GPS-navigasjon for å finne alle tilstøtende eller nærliggende posisjonskoder.
- Sosiale nettverk nettsteder: Gitt en person ‘P’, kan vi finne alle menneskene innen en avstand, ‘d’ fra p ved å bruke BFS til d-nivåene.
- Peer to Peer-nettverk: Igjen kan BFS brukes i peer to peer-nettverk for å finne alle tilstøtende noder.
- Korteste sti og minst spennende tre i den uveide grafen: BFS-teknikk brukes til å finne den korteste banen, dvs. banen med minst antall kanter i den uveide grafen. På samme måte kan vi også finne et minimumspennende tre ved hjelp av BFS i den uveide grafen.
Konklusjon
Bredden-første søketeknikken er en metode som brukes til å krysse alle nodene i en graf eller et tre på en bredde-vis måte.
Denne teknikken brukes for det meste for å finne den korteste banen mellom nodene i en graf eller i applikasjoner som krever at vi besøker hver tilstøtende node som i nettverk.
=> Klikk her for gratis C ++ kurs.
Anbefalt lesing
- Binært søketre C ++: BST-implementering og operasjoner med eksempler
- B Tree og B + Tree Datastruktur i C ++
- Grafimplementering i C ++ ved hjelp av Adjacency List
- Datastruktur for binært tre i C ++
- 12 beste linjediagramverktøy for å lage fantastiske linjediagrammer (2021 RANGER)
- AVL Tree and Heap Datastruktur i C ++
- Trees In C ++: Basic Terminology, Traversal Techniques & C ++ Tree Typer
- Årsaks- og virkningsgraf - Dynamisk skriveteknikk for prøvesaker for maksimal dekning med færre testtilfeller