Meny

Bredd först sökning (BFS) C ++ - program för att korsa en graf eller ett träd

  • Huvud
  • Övrig
  • Bredd först sökning (BFS) C ++ - program för att korsa en graf eller ett träd

breadth first search c program traverse graph

Prova Vårt Instrument För Att Eliminera Problem

Denna handledning täcker den första sökningen i C ++ där diagrammet eller trädet korsas bredvid. Du kommer också att lära dig BFS-algoritm och implementering:

Denna explicita C ++ -handledning ger dig en detaljerad förklaring av traversaltekniker som kan utföras på ett träd eller ett diagram.

Traversal är tekniken med vilken vi besöker varje nod i diagrammet eller ett träd. Det finns två standardmetoder för traversaler.

  • Bredd-först-sökning (BFS)
  • Djup-första sökning (DFS)

=> Se här för att utforska listan med fullständiga C ++ -studier.

hur man programmerar en dator för nybörjare

Bredd först-sökning i C ++

Vad du kommer att lära dig:

Breadth First Search (BFS) Teknik i C ++

I denna handledning kommer vi att diskutera i detalj den bredaste söktekniken.

I bredd-första traversal-tekniken korsas diagrammet eller trädet breddmässigt. Denna teknik använder kuddatastrukturen för att lagra topparna eller noder och även för att bestämma vilken topp / nod som ska tas upp nästa.

Bredd-första-algoritmen börjar med rotnoden och passerar sedan alla intilliggande noder. Därefter väljer den närmaste noden och utforskar alla andra obesökta noder. Denna process upprepas tills alla noder i diagrammet utforskas.

Bredd-första sökalgoritm

Nedan följer algoritmen för BFS-teknik.

Betrakta G som ett diagram som vi ska gå igenom med BFS-algoritmen.

Låt S vara rotens / startnoden i diagrammet.

  • Steg 1: Börja med nod S och stäng den till kön.
  • Steg 2: Upprepa följande steg för alla noder i diagrammet.
  • Steg 3: Dequeue S och bearbeta den.
  • Steg 4: Stäng alla angränsande noder i S och bearbeta dem.
  • (SLUT AV LOPPEN)
  • Steg 6: UTGÅNG

Pseudokod

Pseudokoden för BFS-tekniken ges nedan.

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

Traversaler med illustrationer

BFS-illustrationer Steg 1

Låt 0 vara startnoden eller källnoden. Först slår vi in ​​den i den besökta kön och alla dess intilliggande noder i kön.

BFS Illustrationer Steg 2

Därefter tar vi en av intilliggande noder att bearbeta, dvs. 1. Vi markerar den som besökt genom att ta bort den från kön och placera dess intilliggande noder i kön (2 och 3 redan i kö). Eftersom 0 redan är besökt ignorerar vi det.

testa webbplatsen på olika webbläsare online

BFS-illustrationer Steg 3

Därefter avmarkerar vi nod 2 och markerar den som besökt. Därefter läggs dess intilliggande nod 4 till kön.

BFS-illustrationer Steg 4

Därefter dequeue 3 från kön och markera det som besökt. Nod 3 har bara en angränsande nod, dvs. 0 som redan har besöks. Därför ignorerar vi det.

BFS-illustrationer Steg 5

I detta skede finns endast nod 4 i kön. Dess intilliggande nod 2 är redan besökt, därför ignorerar vi den. Nu markerar vi 4 som besökta.

BFS-illustrationer Steg 6

Därefter är den sekvens som finns i den besökta listan den bredaste första genomgången av den angivna grafen.

Om vi ​​följer den givna grafen och traverssekvensen, kan vi märka att vi för BFS-algoritmen verkligen går igenom grafen bredvid och sedan går till nästa 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): '<

Produktion:

hur man skapar en strängmatris Java

Bredd-första genomgång för den angivna grafen (med 0 som startnod):

0 1 2 3 4

Vi har implementerat BFS i ovanstående program. Observera att diagrammet är i form av en angränsningslista och sedan använder vi en iterator för att iterera genom listan och utföra BFS.

Vi har använt samma diagram som vi använde för illustrationsändamål som en ingång till programmet för att jämföra traverssekvensen.

Runtime-analys

Om V är antalet hörn och E är antalet kanter i en graf, kan tidskomplexiteten för BFS uttryckas som O (| V | + | E |) . Med detta sagt beror det också på datastrukturen som vi använder för att representera grafen.

Om vi ​​använder angränsningslistan (som i vår implementering), är tidskomplexiteten O (| V | + | E |).

Om vi ​​använder angränsningsmatrisen är tidskomplexiteten O (V ^ 2) .

Förutom de datastrukturer som används finns det också en faktor om grafen är tätbefolkad eller glesbefolkad.

När antalet hörn överstiger antalet kanter, sägs diagrammet vara tätt förbundet eftersom det kommer att finnas många bortkopplade hörn. I det här fallet kommer grafens tidskomplexitet att vara O (V).

Å andra sidan kan grafen ibland ha ett högre antal kanter än antalet hörn. I ett sådant fall sägs grafen vara tätt befolkad. Tidskomplexiteten för en sådan graf är O (E).

För att avsluta, vad uttrycket O (| V | + | E |) betyder är beroende på om grafen är tätt eller glesbefolkad, den dominerande faktorn, dvs. kanter eller hörn, kommer att bestämma tidskomplexiteten för diagrammet i enlighet därmed.

Tillämpningar av BFS Traversal

  • Skräp samling: Avfallssamlingstekniken, 'Cheneys algoritm', använder bredd-första genomgång för kopiering av skräpsamling.
  • Sändning i nätverk: Ett paket reser från en nod till en annan med hjälp av BFS-tekniken i sändningsnätet för att nå alla noder.
  • GPS-navigering: Vi kan använda BFS i GPS-navigering för att hitta alla angränsande eller angränsande platsnoder.
  • Webbplatser för sociala nätverk: Med tanke på en person 'P' kan vi hitta alla människor inom ett avstånd, 'd' från p med BFS till d-nivåerna.
  • Peer to Peer-nätverk: Återigen kan BFS användas i peer to peer-nätverk för att hitta alla intilliggande noder.
  • Kortaste sökväg och lägsta spännande träd i den ovägda grafen: BFS-tekniken används för att hitta den kortaste vägen, dvs. vägen med minst antal kanter i den icke-viktade grafen. På samma sätt kan vi också hitta ett minimalt spännande träd med hjälp av BFS i den icke-viktade grafen.

Slutsats

Bredd-första-söktekniken är en metod som används för att korsa alla noder i ett diagram eller ett träd på ett breddmässigt sätt.

Denna teknik används mest för att hitta den kortaste vägen mellan noderna i en graf eller i applikationer som kräver att vi besöker varje angränsande nod som i nätverk.

=> Klicka här för gratis C ++ kurs.

Rekommenderad läsning

^