Breadth First Search (BFS) Algoritm med EXEMPEL

Vad är BFS Algorithm (Bredth-First Search)?

Bredd-först-sökning (BFS) är en algoritm som används för att rita data grafiskt eller söka i ett träd eller korsa strukturer. Den fullständiga formen av BFS är bredd-först-sökning.

Algoritmen besöker och markerar effektivt alla nyckelnoder i en graf på ett exakt breddmässigt sätt. Denna algoritm väljer en enda nod (initialpunkt eller källpunkt) i en graf och besöker sedan alla noder intill den valda noden. Kom ihåg att BFS kommer åt dessa noder en efter en.

När algoritmen besöker och markerar startnoden, flyttar den sig mot de närmaste obesökta noderna och analyserar dem. När de har besökts är alla noder markerade. Dessa iterationer fortsätter tills alla noder i grafen har besökts och markerats.

Vad är Graph-traversals?

En graftraversering är en vanlig metod för att lokalisera vertexpositionen i grafen. Det är en avancerad sökalgoritm som kan analysera grafen med hastighet och precision tillsammans med markering av sekvensen för de besökta hörnen. Denna process gör att du snabbt kan besöka varje nod i en graf utan att vara låst i en oändlig slinga.

Arkitekturen för BFS-algoritmen

1. På de olika datanivåerna kan du markera vilken nod som helst som start- eller initialnod för att börja passera. BFS:en besöker noden, markerar den som besökt och placerar den i kön.
2. Nu kommer BFS att besöka de närmaste och obesökta noderna och markera dem. Dessa värden läggs också till i kön. Kön fungerar på FIFO-modell.
3. På liknande sätt analyseras, markeras och läggs de återstående närmaste och obesökta noderna i grafen till i kön. Dessa objekt tas bort från kön allt eftersom de tas emot och skrivs ut som resultat.

Varför behöver vi BFS Algorithm?

Det finns många anledningar att använda BFS-algoritmen för att söka i din datauppsättning. Några av de viktigaste aspekterna som gör den här algoritmen till ditt förstahandsval är:

• BFS är användbart för att analysera noderna i en graf och konstruera den kortaste vägen att korsa genom dessa.
• BFS kan gå igenom en graf i det minsta antalet iterationer.
• Arkitekturen för BFS-algoritmen är enkel och robust.
• Resultatet av BFS-algoritmen håller en hög nivå av noggrannhet i jämförelse med andra algoritmer.
• BFS-iterationer är sömlösa och det finns ingen möjlighet att den här algoritmen fastnar i ett problem med oändlig loop.

Hur fungerar BFS-algoritmen?

Genomgång av grafer kräver att algoritmen besöker, kontrollerar och/eller uppdaterar varje enskild obesökt nod i en trädliknande struktur. Grafövergångar kategoriseras efter den ordning i vilken de besöker noderna på grafen.

BFS-algoritm startar operationen från den första eller startnoden i en graf och går igenom den ordentligt. När den väl har passerat den initiala noden, besöks och markeras nästa icke-traverserade vertex i grafen.

Därför kan man säga att alla noder intill det aktuella hörnet besöks och passeras i den första iterationen. En enkel kömetodik används för att implementera en BFS-algoritm, och den består av följande steg:

Steg 1)

Varje vertex eller nod i grafen är känd. Du kan till exempel markera noden som V.

Steg 2)

Om vertex V inte nås, lägg då till vertex V i BFS-kön.

Steg 3)

Starta BFS-sökningen och markera punkt V som besökt när den är klar.

Steg 4)

BFS-kön är fortfarande inte tom, ta bort vertex V på grafen från kön.

Steg 5)

Hämta alla återstående noder på grafen som gränsar till noden V.

Steg 6)

För varje angränsande noddel, låt oss säga V1, om den inte är besökt än, lägg då till V1 i BFS-kön.

Steg 7)

BFS kommer att besöka V1, markera den som besökt och ta bort den från kön.

Exempel BFS-algoritm

Steg 1)

Du har en graf med sju tal från 0 till 6.

Steg 2)

0 eller noll har markerats som en rotnod.

Steg 3)

0 besöks, markeras och infogas i ködatastrukturen.

Steg 4)

De återstående 0-intilliggande och obesökta noderna besöks, markeras och infogas i kön.

Steg 5)

Traverserande iterationer upprepas tills alla noder har besökts.

Regler för BFS Algorithm

Här är viktiga regler för att använda BFS-algoritmen:

• En kö (FIFO – Först in, först ut) datastruktur används av BFS.
• Du markerar valfri nod i grafen som rot och börjar bearbeta data från den.
• BFS passerar alla noder i grafen och fortsätter att släppaping dem som färdiga.
• BFS besöker en intilliggande obesökt nod, markerar den som klar och infogar den i en kö.
• Den tar bort den föregående vertexen från kön om ingen intilliggande vertex hittas.
• BFS-algoritmen itererar tills alla noder i grafen har passerats och markerats som slutförda.
• Det finns inga slingor som orsakas av BFS under korsning av data från någon nod.

Tillämpningar av BFS Algorithm

Låt oss ta en titt på några av de verkliga applikationerna där en BFS-algoritmimplementering kan vara mycket effektiv.

• Oviktade grafer: BFS-algoritmen kan enkelt skapa den kortaste vägen och ett minsta möjliga omspännande träd för att besöka alla grafens noder på kortast möjliga tid med hög noggrannhet.
• P2P-nätverk: BFS kan implementeras för att lokalisera alla närmaste eller angränsande noder i ett peer-to-peer-nätverk. Detta kommer att hitta den nödvändiga informationen snabbare.
• Webbsökare: Sökmotorer eller sökrobotar kan enkelt bygga flera nivåer av index genom att använda BFS. BFS-implementering startar från källan, som är webbsidan, och sedan besöker den alla länkar från den källan.
• Navigationssystem: BFS kan hjälpa till att hitta alla närliggande platser från huvud- eller källplatsen.
• Nätverkssändning: Ett utsänt paket styrs av BFS-algoritmen för att hitta och nå alla noder som det har adressen till.

Vanliga frågor