Meni

Široko prvo iskanje (BFS) C ++ Program za prečkanje grafa ali drevesa

  • Glavni
  • Drugo
  • Široko prvo iskanje (BFS) C ++ Program za prečkanje grafa ali drevesa

breadth first search c program traverse graph

Ta vadnica zajema prvo iskanje širine v jeziku C ++, v katerem je graf ali drevo prehodno v širino. Naučili se boste tudi algoritma in implementacije BFS:

Ta eksplicitna vadnica za C ++ vam bo dala podrobno razlago tehnik prečkanja, ki jih je mogoče izvesti na drevesu ali grafu.

Prehod je tehnika, s katero obiščemo vsako vozlišče grafa ali drevesa. Obstajata dve standardni metodi prečkanja.

  • Iskanje po širini (BFS)
  • Iskanje po globini (DFS)

=> Glejte tukaj, če želite raziskati celoten seznam vadnic za C ++.

Najširše iskanje v jeziku C ++

DVD programska oprema za kopiranje za Windows 10

Kaj se boste naučili:

Tehnika širšega prvega iskanja (BFS) v jeziku C ++

V tej vadnici bomo podrobno obravnavali tehniko iskanja po širini.

Pri tehniki prečkanja širine najprej se graf ali drevo prečka širino. Ta tehnika uporablja strukturo podatkov čakalne vrste za shranjevanje vozlišč ali vozlišč in tudi za določitev, katero točko / vozlišče je treba nadalje uporabiti.

Najširši algoritem se začne s korenskim vozliščem in nato prečka vsa sosednja vozlišča. Nato izbere najbližje vozlišče in razišče vsa ostala neobiskana vozlišča. Ta postopek se ponavlja, dokler niso raziskana vsa vozlišča v grafu.

Širina-prvi algoritem iskanja

Spodaj je naveden algoritem za tehniko BFS.

Razmislite o G kot grafu, ki ga bomo prečkali z uporabo algoritma BFS.

Naj bo S koreninsko / začetno vozlišče grafa.

  • Korak 1: Začnite z vozliščem S in ga postavite v čakalno vrsto.
  • 2. korak: Ponovite naslednje korake za vsa vozlišča na grafu.
  • 3. korak: Izbrišite S in ga obdelajte.
  • 4. korak: V sosednja vozlišča S postavite v vrsto in jih obdelajte.
  • [KONEC ZANIKE]
  • 6. korak: IZHOD

Psevkodo

Psevdo-koda za tehniko BFS je navedena spodaj.

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

Prehodi z ilustracijami

BFS ilustracije 1. korak

Naj bo 0 začetno vozlišče ali izvorno vozlišče. Najprej ga postavimo v čakalno vrsto v obiskani vrsti in vsa sosednja vozlišča v čakalni vrsti.

BFS ilustracije 2. korak

Nato vzamemo za obdelavo eno od sosednjih vozlišč, tj. 1. Označimo jo kot obiskano tako, da jo odstranimo iz čakalne vrste in sosednja vozlišča postavimo v čakalno vrsto (2 in 3 sta že v čakalni vrsti). Ker je 0 že obiskano, ga prezremo.

BFS ilustracije 3. korak

c ++ nedefinirano sklicevanje na razred

Nato vozlišče 2 odstranimo iz vrstnega reda in ga označimo kot obiskano. Nato se v čakalno vrsto doda sosednje vozlišče 4.

BFS ilustracije 4. korak

Nato iz čakalne vrste odstranimo 3 in jo označimo kot obiskano. Vozlišče 3 ima samo eno sosednje vozlišče, tj. 0, ki je že obiskano. Zato ga ignoriramo.

BFS Illustrations 5. korak

Na tej stopnji je v čakalni vrsti samo vozlišče 4. Sosednje vozlišče 2 je že obiskano, zato ga prezremo. Zdaj označujemo 4 kot obiskane.

BFS ilustracije 6. korak

Nato je zaporedje na obiskanem seznamu prvi prehod danega grafa v širino.

Če opazujemo dani graf in zaporedje prečkanja, lahko opazimo, da za algoritem BFS res prehodimo graf v širino in nato preidemo na naslednjo stopnjo.

Izvajanje 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): '<

Izhod:

Prehod širine in širine za dani graf (z 0 kot začetno vozlišče):

funkcionalno preskušanje vs nefunkcionalno preskušanje

0 1 2 3 4

BFS smo uvedli v zgornjem programu. Upoštevajte, da je graf v obliki seznama sosednosti, nato pa z iteratorjem preletimo seznam in izvedemo BFS.

Za primerjavo zaporedja prehodov smo uporabili isti graf, kot smo ga uporabili za ponazoritev.

Analiza med izvajanjem

Če je V število oglišč in E število robov grafa, potem lahko časovno zapletenost BFS izrazimo kot O (| V | + | E |) . Ob tem je odvisno tudi od podatkovne strukture, ki jo uporabljamo za predstavitev grafa.

Če uporabimo seznam sosednosti (kot pri naši izvedbi), potem je časovna zapletenost O (| V | + | E |).

Če uporabimo matrico sosednosti, potem je časovna zapletenost O (V ^ 2) .

Poleg uporabljenih podatkovnih struktur obstaja tudi dejavnik, ali je graf gosto poseljen ali redko poseljen.

Ko število oglišč preseže število robov, naj bi bil graf redko povezan, saj bo veliko odpovedanih oglišč. V tem primeru bo časovna zapletenost grafa O (V).

Po drugi strani pa ima lahko včasih graf večje število robov kot število točk. V takem primeru naj bi bil graf gosto poseljen. Časovna zapletenost takega grafa je O (E).

Če zaključimo, kaj pomeni izraz O (| V | + | E |), je odvisno od tega, ali je graf gosto ali redko poseljen, bo prevladujoči faktor, tj.rebri ali oglišča, ustrezno določil časovno zapletenost grafa.

Aplikacije BFS Traversal

  • Zbiranje odpadkov: Tehnika zbiranja smeti, 'Cheneyev algoritem', uporablja kopiranje prvega širine za kopiranje odvoza smeti.
  • Oddajanje v omrežjih: Paket potuje od enega vozlišča do drugega s pomočjo tehnike BFS v oddajnem omrežju, da doseže vsa vozlišča.
  • GPS navigacija: BFS v navigaciji GPS lahko uporabimo za iskanje vseh sosednjih ali sosednjih lokacijskih vozlišč.
  • Spletna mesta za družabna omrežja: Glede na osebo 'P' lahko najdemo vse ljudi na daljavo, 'd' od p z uporabo BFS do ravni d.
  • Medsebojna omrežja: Spet lahko BFS uporabimo v enakovrednih omrežjih za iskanje vseh sosednjih vozlišč.
  • Najkrajša pot in najmanjše drevo v nestehtanem grafu: Tehnika BFS se uporablja za iskanje najkrajše poti, tj.pot z najmanjšim številom robov v neuteženem grafu. Podobno lahko z BFS v neuteženem grafu najdemo tudi minimalno drevo, ki se razteza.

Zaključek

Tehnika iskanja po širini je metoda, ki se uporablja za prehod vseh vozlišč grafa ali drevesa v širino.

Ta tehnika se večinoma uporablja za iskanje najkrajše poti med vozlišči grafa ali v aplikacijah, ki zahtevajo obisk vsakega sosednjega vozlišča kot v omrežjih.

=> Kliknite tukaj za brezplačni tečaj C ++.

Priporočeno branje

^