Graph Traversal-methoden hebben me altijd behoorlijk gefascineerd. Van het uitvoeren van effectieve peer-to-peer-communicatie tot het vinden van de dichtstbijzijnde restaurants en cafés met behulp van GPS, verplaatsingsmethoden hebben een gevarieerde reeks toepassingen in het echte scenario. In deze blog over Breadth-First Search Algorithm bespreken we de logica achter graaf-doorloopmethoden en gebruiken we voorbeelden om de werking van het Breadth-First Search-algoritme te begrijpen.
Om diepgaande kennis te krijgen van kunstmatige intelligentie en machine learning, kunt u zich inschrijven voor live door Edureka met 24/7 ondersteuning en levenslange toegang.
Hier is een lijst met onderwerpen die zullen worden behandeld in deze blog:
- Inleiding tot Graph Traversal
- Wat is de breedte-eerste zoekopdracht?
- Inzicht in het Breadth-First Search-algoritme met een voorbeeld
- Breedte-eerste zoekalgoritme Pseudocode
- Toepassingen van breedte-eerste zoekopdracht
Inleiding tot Graph Traversal
Het proces van het bezoeken en verkennen van een grafiek voor verwerking wordt graafdoorgang genoemd. Om specifieker te zijn, gaat het erom elk hoekpunt en elke rand in een grafiek te bezoeken en te verkennen, zodat alle hoekpunten precies één keer worden verkend.
Dat klinkt simpel! Maar er is een addertje onder het gras.
Er zijn verschillende technieken voor het doorlopen van grafieken, zoals Breadth-First Search, Depth First Search enzovoort. De uitdaging is om een grafiek te gebruiken traversale techniek die het meest geschikt is om een bepaald probleem op te lossen. Dit brengt ons bij de techniek Breadth-First Search.
data blending in tableau 10
Wat is het breedte-eerste zoekalgoritme?
Breadth-First Search-algoritme is een techniek voor het doorlopen van grafieken, waarbij u een willekeurig beginknooppunt (bron- of hoofdknooppunt) selecteert en de grafiek zo laagsgewijs doorloopt dat alle knooppunten en hun respectievelijke onderliggende knooppunten worden bezocht en verkend.
Voordat we verder gaan en Breadth-First Search aan de hand van een voorbeeld gaan begrijpen, laten we eerst twee belangrijke termen met betrekking tot het doorlopen van grafieken leren kennen:
- Een knooppunt bezoeken: Zoals de naam al doet vermoeden, betekent het bezoeken van een knooppunt het bezoeken of selecteren van een knooppunt.
- Een knooppunt verkennen: Het verkennen van de aangrenzende knooppunten (onderliggende knooppunten) van een geselecteerd knooppunt.
Raadpleeg de bovenstaande afbeelding om dit beter te begrijpen.
Inzicht in het breedte-eerste zoekalgoritme met een voorbeeld
Het algoritme Breadth-First Search volgt een eenvoudige, op niveaus gebaseerde benadering om een probleem op te lossen. Beschouw de onderstaande binaire boom (dit is een grafiek). Ons doel is om de grafiek te doorlopen met behulp van het Breadth-First Search-algoritme.
Voordat we aan de slag gaan, moet u bekend zijn met de belangrijkste gegevensstructuur van het Breadth-First Search-algoritme.
Een wachtrij is een abstracte gegevensstructuur die de First-In-First-Out-methode volgt (gegevens die als eerste worden ingevoerd, worden eerst geopend). Het is aan beide kanten open, waarbij het ene uiteinde altijd wordt gebruikt om gegevens in te voegen (enqueue) en het andere wordt gebruikt om gegevens te verwijderen (dequeue).
Laten we nu eens kijken naar de stappen die nodig zijn om een grafiek te doorlopen met behulp van Breadth-First Search:
Stap 1: Neem een lege wachtrij.
Stap 2: Selecteer een startknooppunt (bezoek een knooppunt) en plaats het in de wachtrij.
Stap 3: Op voorwaarde dat de wachtrij niet leeg is, extraheert u het knooppunt uit de wachtrij en voegt u de onderliggende knooppunten in (een knooppunt verkennen) in de wachtrij.
Stap 4: Druk het uitgepakte knooppunt af.
wat wordt toegevoegd in java
Maakt u zich geen zorgen als u in de war bent, we zullen dit begrijpen met een voorbeeld.
Bekijk de onderstaande grafiek, we zullen het algoritme Breadth-First Search gebruiken om door de grafiek te bladeren.
In ons geval zullen we knooppunt ‘a’ toewijzen als het hoofdknooppunt en naar beneden gaan en de bovenstaande stappen volgen.
De bovenstaande afbeelding toont het end-to-end-proces van het Breadth-First Search Algorithm. Laat me dit wat dieper uitleggen.
- Wijs ‘a’ toe als het hoofdknooppunt en voeg het in de wachtrij in.
- Extraheer knooppunt ‘a’ uit de wachtrij en voeg de onderliggende knooppunten van ‘a’ in, d.w.z. ‘b’ en ‘c’.
- Knooppunt ‘a’ afdrukken.
- De wachtrij is niet leeg en heeft knooppunt ‘b’ en ‘c’. Omdat ‘b’ het eerste knooppunt in de wachtrij is, gaan we het extraheren en de onderliggende knooppunten van ‘b’ invoegen, d.w.z. knooppunt ‘d’ en ‘e’.
- Herhaal deze stappen totdat de wachtrij leeg is. Merk op dat de knooppunten die al zijn bezocht niet aan de wachtrij mogen worden toegevoegd nog een keer.
Laten we nu eens kijken naar de pseudocode van het Breadth-First Search-algoritme.
Breedte-eerste zoekalgoritme Pseudocode
Hier is de pseudocode om het Breadth-First Search-algoritme te implementeren:
Input: s als het bronknooppunt BFS (G, s) laat Q in de wachtrij staan. Q. wachtrij (s) markeren s als bezocht terwijl (Q is niet leeg) v = Q.dequeue () voor alle buren w van v in grafiek G als w niet bezocht is Q. wachtrij (w) markeer w as bezocht
In de bovenstaande code worden de volgende stappen uitgevoerd:
- (G, s) wordt ingevoerd, hier is G de grafiek en s is het hoofdknooppunt
- Een wachtrij ‘Q’ wordt gemaakt en geïnitialiseerd met het bronknooppunt ‘s’
- Alle onderliggende knooppunten van ‘s’ zijn gemarkeerd
- Pak ‘s’ uit de wachtrij en bezoek de onderliggende knooppunten
- Verwerk alle onderliggende knooppunten van v
- Slaat w (kindknooppunten) op in Q om de onderliggende knooppunten verder te bezoeken
- Ga door tot ‘Q’ is leeg
Laten we, voordat we de blog afronden, eens kijken naar enkele toepassingen van het Breadth-First Search-algoritme.
Toepassingen van het breedte-eerste zoekalgoritme
Breadth-first Search is een eenvoudige methode voor het doorlopen van grafieken met een verrassend scala aan toepassingen. Hier zijn een paar interessante manieren waarop Bread-First Search wordt gebruikt:
Crawlers in zoekmachines: Breadth-First Search is een van de belangrijkste algoritmen die worden gebruikt voor het indexeren van webpagina's. Het algoritme begint met het doorlopen van de bronpagina en volgt alle links die aan de pagina zijn gekoppeld. Hier wordt elke webpagina beschouwd als een knooppunt in een grafiek.
GPS-navigatiesystemen: Breadth-First Search is een van de beste algoritmen die wordt gebruikt om aangrenzende locaties te vinden met behulp van het GPS-systeem.
pl sql tutorial met voorbeelden
Zoek het kortste pad en de minimale overspanningsboom voor een ongewogen grafiek: Als het gaat om een ongewogen grafiek, is het berekenen van het kortste pad vrij eenvoudig, aangezien het idee achter het kortste pad is om een pad te kiezen met het minste aantal randen. Breadth-First Search kan dit mogelijk maken door een minimum aantal knooppunten te doorlopen vanaf het bronknooppunt. Op dezelfde manier kunnen we voor een opspannende boom een van de twee methoden gebruiken, Breedte-eerste zoekactie of Diepte-eerste doorloopmethode om een opspannende boom te vinden.
Uitzenden: Netwerken maakt gebruik van wat we pakketten noemen voor communicatie. Deze pakketten volgen een traversale methode om verschillende netwerkknooppunten te bereiken. Een van de meest gebruikte traversal-methoden is Breadth-First Search. Het wordt gebruikt als een algoritme dat wordt gebruikt om uitgezonden pakketten over alle knooppunten in een netwerk te communiceren.
Peer-to-peer-netwerken: Breadth-First Search kan worden gebruikt als een doorloopmethode om alle aangrenzende knooppunten in een peer-to-peer-netwerk te vinden. BitTorrent gebruikt bijvoorbeeld Breadth-First Search voor peer-to-peer-communicatie.
Dus dat ging allemaal over de werking van het Breadth-First Search-algoritme. Nu je weet hoe je door grafieken moet lopen, ben ik er zeker van dat je nieuwsgierig bent naar meer. Hier zijn een paar relevante blogs om u geïnteresseerd te houden:
Hiermee komen we aan het einde van deze blog. Als je vragen hebt over dit onderwerp, laat dan hieronder een reactie achter en we nemen zo snel mogelijk contact met je op.
Als u zich wilt inschrijven voor een complete cursus over kunstmatige intelligentie en machine learning, heeft Edureka een speciaal samengesteld dat zal je bekwaam maken in technieken zoals begeleid leren, onbewaakt leren en natuurlijke taalverwerking. Het omvat training over de nieuwste ontwikkelingen en technische benaderingen op het gebied van kunstmatige intelligentie en machine learning, zoals diep leren, grafische modellen en versterkend leren.