breadth first search c program traverse graph
Denne vejledning dækker første søgning i bredde i C ++, hvor grafen eller træet krydses bredt. Du lærer også BFS algoritme og implementering:
Denne eksplicitte C ++ tutorial giver dig en detaljeret forklaring af traversal teknikker, der kan udføres på et træ eller en graf.
Traversal er den teknik, hvor vi besøger hver eneste node i grafen eller et træ. Der er to standardmetoder til traversaler.
- Bredde-første søgning (BFS)
- Dybde-første søgning (DFS)
=> Se her for at udforske den komplette C ++ tutorials-liste.
hvad er brugstilfælde i softwaretest
Hvad du lærer:
Breadth First Search (BFS) teknik i C ++
I denne vejledning diskuterer vi detaljeret den første søgningsteknik.
I bredde-første traversal-teknikken krydses grafen eller træet bredt. Denne teknik bruger kødatastrukturen til at gemme hjørnerne eller knudepunkterne og også til at bestemme, hvilken toppunkt / knude der skal tages op næste.
Bredde-første algoritme starter med rodnoden og krydser derefter alle de tilstødende noder. Derefter vælger den nærmeste knude og udforsker alle de andre ubesøgte noder. Denne proces gentages, indtil alle knudepunkterne i grafen udforskes.
Bredde-første søgningsalgoritme
Nedenfor er algoritmen for BFS-teknik.
Overvej G som en graf, som vi skal krydse ved hjælp af BFS-algoritmen.
Lad S være rod- / startknudepunktet for grafen.
- Trin 1: Start med knudepunkt S, og sæt det i køen.
- Trin 2: Gentag følgende trin for alle knudepunkter i grafen.
- Trin 3: Dequeue S og behandle det.
- Trin 4: Indsæt alle de tilstødende noder i S, og behandl dem.
- [SLUT AF LØKKEN]
- Trin 6: AFSLUT
Pseudokode
Pseudokoden til BFS-teknikken er angivet 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. endTraversaler med illustrationer
Lad 0 være startknudepunktet eller kildeknudepunktet. Først indkapsler vi den i den besøgte kø og alle dens tilstødende noder i køen.
Dernæst tager vi en af de tilstødende noder til behandling, dvs. 1. Vi markerer den som besøgt ved at fjerne den fra køen og sætte de tilstødende noder i køen (2 og 3 allerede i kø). Da 0 allerede er besøgt, ignorerer vi det.
oracle interview spørgsmål og svar til erfarne
Dernæst dequeue node 2 og markere det som besøgt. Derefter føjes dens tilstødende knudepunkt 4 til køen.
Dernæst afskiller vi 3 fra køen og markerer det som besøgt. Node 3 har kun en tilstødende node, dvs. 0, som allerede er besøgt. Derfor ignorerer vi det.
På dette trin er kun knude 4 til stede i køen. Dens tilstødende knudepunkt 2 er allerede besøgt, derfor ignorerer vi det. Nu markerer vi 4 som besøgt.
Derefter er sekvensen, der er til stede i den besøgte liste, bredden-første gennemkørsel af den givne graf.
Hvis vi observerer den givne graf og traversalsekvensen, kan vi bemærke, at vi for BFS-algoritmen faktisk krydser grafen bredt og derefter går til det næste niveau.
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): '< Produktion:
gratis dvd-kopieringssoftware til mac
Bredde-første gennemgang for den givne graf (med 0 som startnode):
0 1 2 3 4
Vi har implementeret BFS i ovenstående program. Bemærk, at grafen er i form af en nærhedsliste, og derefter bruger vi en iterator til at gentage listen og udføre BFS.
Vi har brugt den samme graf, som vi brugte til illustration som input til programmet for at sammenligne traversalsekvensen.
Runtime-analyse
Hvis V er antallet af hjørner og E er antallet af kanter i en graf, kan tidskompleksiteten for BFS udtrykkes som O (| V | + | E |) . Når det er sagt, afhænger det også af datastrukturen, som vi bruger til at repræsentere grafen.
Hvis vi bruger nærhedslisten (som i vores implementering), er tidskompleksiteten O (| V | + | E |).
Hvis vi bruger nærhedsmatrixen, er tidskompleksiteten O (V ^ 2) .
Bortset fra de anvendte datastrukturer er der også en faktor for, om grafen er tæt befolket eller tyndt befolket.
Når antallet af hjørner overstiger antallet af kanter, siges grafen at være tyndt forbundet, da der vil være mange frakoblede hjørner. I dette tilfælde vil grafens tidskompleksitet være O (V).
På den anden side kan grafen undertiden have et højere antal kanter end antallet af hjørner. I et sådant tilfælde siges det, at grafen er tæt befolket. Tidskompleksiteten af en sådan graf er O (E).
For at konkludere, hvad udtrykket O (| V | + | E |) betyder, afhænger af om grafen er tæt eller tyndt befolket, den dominerende faktor, dvs. kanter eller hjørner, bestemmer grafens tidskompleksitet i overensstemmelse hermed.
Anvendelser af BFS Traversal
- Dagrenovation: Affaldsindsamlingsteknikken, 'Cheneys algoritme', bruger bredeste første traversal til kopiering af affaldssamling.
- Broadcasting i netværk: En pakke bevæger sig fra en node til en anden ved hjælp af BFS-teknikken i radionetværket for at nå alle noder.
- GPS-navigation: Vi kan bruge BFS i GPS-navigation til at finde alle de tilstødende eller nærliggende lokaliseringsknudepunkter.
- Sociale netværkswebsteder: I betragtning af en person 'P' kan vi finde alle mennesker inden for en afstand, 'd' fra p ved hjælp af BFS til d-niveauerne.
- Peer to Peer-netværk: Igen kan BFS bruges i peer-to-peer-netværk for at finde alle de tilstødende noder.
- Korteste sti og mindst spændende træ i den ikke-vægtede graf: BFS-teknik bruges til at finde den korteste sti, dvs. stien med mindst antal kanter i den ikke-vægtede graf. På samme måde kan vi også finde et minimumspændende træ ved hjælp af BFS i den ikke-vægtede graf.
Konklusion
Bredden-første søgningsteknikken er en metode, der bruges til at krydse alle knudepunkterne i en graf eller et træ bredt.
Denne teknik bruges mest til at finde den korteste sti mellem knudepunkterne i en graf eller i applikationer, der kræver, at vi besøger hver tilstødende knude som i netværk.
=> Klik her for det gratis C ++ kursus.
Anbefalet læsning
- Binært søgetræ C ++: BST-implementering og operationer med eksempler
- B Tree og B + Tree Datastruktur i C ++
- Grafimplementering i C ++ ved hjælp af Adjacency List
- Datastruktur for binært træ i C ++
- 12 bedste værktøjer til fremstilling af linjegraf til oprettelse af fantastiske linjegrafer [2021 RANGER]
- AVL-træ- og bunndatastruktur i C ++
- Træer i C ++: grundlæggende terminologi, gennemgange og C ++ trætyper
- Årsag og virkning Graf - Dynamisk skrivetekst skriveteknik til maksimal dækning med færre testsager