Grafgenomgångsmetoder har alltid fascinerat mig ganska. Från att utföra effektiv peer-to-peer-kommunikation till att hitta närmaste restauranger och kaféer med hjälp av GPS, har traversal-metoder en varierad uppsättning applikationer i det verkliga scenariot. I denna blogg om Breadth-First Search Algorithm kommer vi att diskutera logiken bakom grafgenomgångsmetoder och använda exempel för att förstå hur Breadth-First Search-algoritmen fungerar.
För att få fördjupad kunskap om artificiell intelligens och maskininlärning kan du anmäla dig till live av Edureka med support dygnet runt och livstidsåtkomst.
Här är en lista över ämnen som kommer att vara omfattas av den här bloggen:
- Introduktion till diagramtransversal
- Vad är bredd-första sökningen?
- Förstå algoritmen Breadth-First Search med ett exempel
- Bredd-första sökalgoritm Pseudokod
- Tillämpningar av bredd-första sökning
Introduktion till diagramtransversal
Processen med att besöka och utforska ett diagram för bearbetning kallas diagramtransversal. För att vara mer specifik handlar det om att besöka och utforska varje toppunkt och kant i ett diagram så att alla topparna utforskas exakt en gång.
Det låter enkelt! Men det finns en fångst.
Det finns flera grafgenomgångstekniker som Breadth-First Search, Depth First Search och så vidare. Utmaningen är att använda ett diagram traversal teknik som är mest lämplig för att lösa ett visst problem. Detta leder oss till tekniken Breadth-First Search.
Vad är bredd-första sökalgoritmen?
Breadth-First Search-algoritmen är en grafkörningsteknik, där du väljer en slumpmässig initial nod (källa eller rotnod) och börjar korsa diagrammet på ett sådant sätt att alla noder och deras respektive barnnoder besöks och utforskas.
ruby on rails webbhandledning
Innan vi går vidare och förstår Breadth-First Search med ett exempel, låt oss bekanta oss med två viktiga termer relaterade till grafgenomgång:
- Besöker en nod: Precis som namnet antyder betyder att besöka en nod att besöka eller välja en nod.
- Utforska en nod: Utforska angränsande noder (undernoder) för en vald nod.
Se figuren ovan för att bättre förstå detta.
Förstå algoritmen för bredd-första sökning med ett exempel
Breadth-First Search-algoritmen följer en enkel, nivåbaserad metod för att lösa ett problem. Tänk på det binära trädet nedan (vilket är ett diagram). Vårt mål är att korsa grafen med hjälp av Breadth-First Search Algorithm.
Innan vi börjar måste du vara bekant med den huvudsakliga datastrukturen som är involverad i Breadth-First Search-algoritmen.
En kö är en abstrakt datastruktur som följer metoden First-In-First-Out (data som infogas först kommer åt.). Den är öppen i båda ändar, där den ena änden alltid används för att infoga data (enqueue) och den andra används för att ta bort data (dequeue).
Låt oss nu titta på stegen som är involverade i att korsa en graf med hjälp av Bredd-första sökning:
Steg 1: Ta en tom kö.
Steg 2: Välj en startnod (besöka en nod) och sätt in den i kön.
Steg 3: Förutsatt att kön inte är tom, extrahera noden från kön och infoga dess undernoder (utforska en nod) i kön.
Steg 4: Skriv ut den extraherade noden.
Oroa dig inte om du är förvirrad, vi kommer att förstå detta med ett exempel.
Ta en titt på grafen nedan, vi använder algoritmen Breadth-First Search för att gå igenom diagrammet.
I vårt fall tilldelar vi nod 'a' som rotnod och börjar köra nedåt och följer stegen ovan.
Ovanstående bild visar slut-till-slut-processen för Breadth-First Search Algorithm. Låt mig förklara detta mer ingående.
- Tilldela 'a' som rotnod och infoga det i kön.
- Extrahera nod 'a' från kön och infoga barnnoderna för 'a', dvs 'b' och 'c'.
- Skriv ut nod 'a'.
- Kön är inte tom och har nod 'b' och 'c'. Eftersom 'b' är den första noden i kön, låt oss extrahera den och infoga undernoderna för 'b', dvs nod 'd' och 'e'.
- Upprepa dessa steg tills kön blir tom. Observera att de noder som redan har besöks inte ska läggas till i kön på nytt.
Låt oss nu titta på pseudokoden för algoritmen Breadth-First Search.
Bredd-första sökalgoritm Pseudokod
Här är pseudokoden för att implementera algoritmen Breadth-First Search:
Ingång: s som källnod BFS (G, s) låter Q stå i kö. Q.enqueue (s) markerar s som besökt medan (Q är inte tomt) v = Q.queque () för alla grannar w av v i diagram G om w inte besöks Q.queque (w) markerar w som besök
I ovanstående kod utförs följande steg:
- (G, s) matas in, här är G grafen och s är rotnoden
- En kö 'Q' skapas och initieras med källnoden 's'
- Alla underordnade noder på 's' är markerade
- Extrahera 's' från kön och besök barnnoderna
- Bearbeta alla barnnoder i v
- Lagrar w (barnnoder) i Q för att ytterligare besöka dess barnnoder
- Fortsätt tills “Q” är tömma
Innan vi avslutar bloggen, låt oss titta på några tillämpningar av algoritmen Breadth-First Search.
Tillämpningar av bredd-första sökalgoritmen
konvertera datumsträng till datum
Bredd-första-sökning är en enkel grafgenomgångsmetod som har ett överraskande utbud av applikationer. Här är några intressanta sätt som Bread-First Search används:
Sökrobotar i sökmotorer: Breadth-First Search är en av de viktigaste algoritmerna som används för indexering av webbsidor. Algoritmen börjar korsa från källsidan och följer alla länkar som är associerade med sidan. Här kommer varje webbsida att betraktas som en nod i ett diagram.
GPS-navigationssystem: Breadth-First Search är en av de bästa algoritmerna som används för att hitta närliggande platser med hjälp av GPS-systemet.
Hitta den kortaste sökvägen och det minsta spännande trädet för en oviktad graf: När det gäller en ovägd graf är det enkelt att beräkna den kortaste vägen eftersom tanken bakom den kortaste vägen är att välja en väg med minst antal kanter. Bredd-första sökning kan tillåta detta genom att korsa ett minimalt antal noder som börjar från källnoden. På samma sätt kan vi använda ett av de två metoderna Breadth-First Search eller Depth-first traversal för ett spännande träd för att hitta ett spännande träd.
Sändning: Nätverk använder det vi kallar paket för kommunikation. Dessa paket följer en genomgångsmetod för att nå olika nätverksnoder. En av de vanligaste traversalmetoderna är Breadth-First Search. Den används som en algoritm som används för att kommunicera sända paket över alla noder i ett nätverk.
Peer to Peer Networking: Bredd-första sökning kan användas som en genomgångsmetod för att hitta alla angränsande noder i ett Peer to Peer-nätverk. Till exempel använder BitTorrent Breadth-First Search för peer to peer-kommunikation.
Så det handlade bara om hur Breadth-First Search-algoritmen fungerar. Nu när du vet hur du går igenom grafer är jag säker på att du är nyfiken på att lära dig mer. Här är några relevanta bloggar för att hålla dig intresserad:
Med detta kommer vi till slutet av den här bloggen. Om du har frågor angående detta ämne, vänligen lämna en kommentar nedan så återkommer vi till dig.
Om du vill anmäla dig till en fullständig kurs om artificiell intelligens och maskininlärning har Edureka en speciell kurator som kommer att göra dig skicklig i tekniker som Supervised Learning, Oövervakat lärande och Natural Language Processing. Det inkluderar utbildning om de senaste framstegen och tekniska tillvägagångssätten inom artificiell intelligens och maskininlärning som djupinlärning, grafiska modeller och förstärkningslärande.