Inleiding tot BFS-algoritme
Om efficiënt toegang te krijgen tot de gegevens en deze te beheren, kunnen ze worden opgeslagen en georganiseerd in een speciaal formaat dat de gegevensstructuur wordt genoemd. Er zijn veel datastructuren zoals Stack, Array, Linked List, Queues, Trees en Graphs etc. In lineaire datastructuren, zoals Stack, Array, Linked List en Queue, worden de data georganiseerd in lineaire volgorde terwijl, in niet- lineaire gegevensstructuren zoals bomen en grafieken, gegevens zijn hiërarchisch georganiseerd, niet in een reeks. De grafiek is een niet-lineaire gegevensstructuur met knooppunten en randen. Nodes in Graph kunnen ook worden aangeduid als vertices die eindig zijn in aantal en randen zijn de verbindingslijnen tussen twee willekeurige nodes.
In de bovenstaande grafiek kunnen hoekpunten worden weergegeven als V = (A, B, C, D, E) en kunnen randen worden gedefinieerd als
E = (AB, AC, CD, BE)
Wat is het BFS-algoritme?
Er zijn over het algemeen twee algoritmen die worden gebruikt voor het doorkruisen van een grafiek. Het zijn BFS (Breadth-First Search) en DFS (Depth First Search) algoritmen. Doorkruisen van de grafiek bezoekt precies één hoekpunt of knooppunt en rand, in een goed gedefinieerde volgorde. Het is ook erg belangrijk om de bezochte hoekpunten bij te houden, zodat hetzelfde hoekpunt niet twee keer wordt doorkruist. In het Breath First Search-algoritme begint de verplaatsing vanaf een geselecteerd knooppunt of bronknooppunt en gaat de verplaatsing door de knooppunten die rechtstreeks zijn verbonden met het bronknooppunt. In eenvoudiger bewoordingen, in het BFS-algoritme moet men eerst de huidige laag horizontaal verplaatsen en doorkruisen, waarna naar de volgende laag moet worden verplaatst.
Hoe werkt BFS-algoritme?
Laten we het voorbeeld van de onderstaande grafiek nemen.
De belangrijke taak bij de hand is om het kortste pad in een grafiek te vinden terwijl u de knooppunten doorkruist. Wanneer we door een grafiek gaan, gaat het hoekpunt van onontdekte staat naar ontdekte staat en wordt uiteindelijk volledig ontdekt. Opgemerkt moet worden dat het mogelijk is om op een bepaald moment vast te lopen terwijl u door een grafiek loopt en een knooppunt twee keer kan worden bezocht. We kunnen dus een methode gebruiken om de knooppunten te markeren nadat het de status van onontdekt verandert in volledig ontdekt worden.
We kunnen in de onderstaande afbeelding zien dat de knooppunten in de grafieken kunnen worden gemarkeerd als ze volledig worden ontdekt door ze met zwart te markeren. We kunnen beginnen bij het bronknooppunt en naarmate de doorgang door elk knooppunt vordert, kunnen ze worden gemarkeerd om te worden geïdentificeerd.
De verplaatsing begint vanaf een hoekpunt en reist vervolgens naar de uitgaande randen. Wanneer een rand naar een niet-ontdekt hoekpunt gaat, wordt deze gemarkeerd als ontdekt. Maar wanneer een rand naar een volledig ontdekt of ontdekt hoekpunt gaat, wordt het genegeerd.
Voor een gerichte grafiek wordt elke rand één keer bezocht en voor niet-gerichte grafiek wordt deze twee keer bezocht, dwz één keer tijdens het bezoeken van elke knoop. Het te gebruiken algoritme wordt bepaald op basis van de manier waarop de gevonden hoekpunten worden opgeslagen. In het BFS-algoritme wordt de wachtrij gebruikt waar het oudste hoekpunt eerst wordt ontdekt en zich vervolgens door de lagen van het startpunt verspreidt.
Stappen worden uitgevoerd voor een BFS-algoritme
De onderstaande stappen worden uitgevoerd voor een BFS-algoritme.
- Laten we in een gegeven grafiek beginnen met een hoekpunt, dwz in het bovenstaande diagram is dit knooppunt 0. Het niveau waarin dit hoekpunt aanwezig is, kan worden aangeduid als laag 0.
- De volgende stap is om alle andere hoekpunten te vinden die grenzen aan het startpunt, dat wil zeggen knooppunt 0 of er direct vanaf toegankelijk zijn. Vervolgens kunnen we deze aangrenzende hoekpunten markeren om aanwezig te zijn op Laag 1.
- Het is mogelijk om naar hetzelfde hoekpunt te komen vanwege een lus in de grafiek. We moeten dus alleen reizen naar die hoekpunten die in dezelfde laag aanwezig moeten zijn.
- Vervolgens wordt het bovenliggende hoekpunt van het huidige hoekpunt waar we ons bevinden gemarkeerd. Hetzelfde moet worden uitgevoerd voor alle hoekpunten in laag 1.
- Dan is de volgende stap om al die hoekpunten te vinden die een enkele rand verwijderd zijn van alle hoekpunten die zich in Laag 1 bevinden. Deze nieuwe reeks hoekpunten zal zich in Laag 2 bevinden.
- Het bovenstaande proces wordt herhaald totdat alle knooppunten zijn doorlopen.
Voorbeeld:
Laten we het voorbeeld van de onderstaande grafiek nemen en begrijpen hoe het BFS-algoritme werkt. Over het algemeen wordt in een BFS-algoritme een wachtrij gebruikt om de knooppunten in een wachtrij te plaatsen terwijl ze de knooppunten doorkruisen.
In de bovenstaande grafiek moet eerst het knooppunt 0 worden bezocht en wordt dit knooppunt in de wachtrij geplaatst in de onderstaande wachtrij:
Na een bezoek aan het knooppunt 0, staat het aangrenzende knooppunt van 0, 1 en 2 in de wachtrij. De wachtrij kan als volgt worden weergegeven: 
Vervolgens wordt het eerste knooppunt in de wachtrij van 2 bezocht. Nadat het knooppunt 2 is bezocht, kan de wachtrij als volgt worden weergegeven:
Na een bezoek aan knooppunt 2, zal 5 in de wachtrij staan en omdat er geen niet-bezochte aangrenzende knooppunten zijn voor knooppunt 5, hoewel 5 in de wachtrij staat maar niet tweemaal zal worden bezocht.
Vervolgens is het eerste knooppunt in de wachtrij 1 die zal worden bezocht. De aangrenzende knooppunten 3 en 4 staan in de wachtrij. De wachtrij wordt weergegeven zoals hieronder
Vervolgens is het eerste knooppunt in de wachtrij 5, en voor dit knooppunt zijn er geen niet-bezochte aangrenzende knooppunten meer. Hetzelfde geldt voor knooppunten 3 en 4 waarvoor ook geen niet-bezochte aangrenzende knooppunten meer zijn.
Dus alle knooppunten worden doorlopen en uiteindelijk wordt de wachtrij leeg.
Conclusie
Het breedte-zoekalgoritme heeft een aantal grote voordelen om het aan te bevelen. Een van de vele toepassingen van het BFS-algoritme is het berekenen van het kortste pad. Het wordt ook gebruikt in netwerken om aangrenzende knooppunten te vinden en is te vinden op sociale netwerksites, netwerkuitzendingen en afvalinzameling. De gebruikers moeten de vereiste en het gegevenspatroon begrijpen om het te gebruiken voor betere prestaties.
Aanbevolen artikelen
Dit is een leidraad geweest voor het BFS-algoritme. Hier bespreken we het concept, de werking, de stappen en het voorbeeld van prestaties in BFS-algoritme. U kunt ook onze andere voorgestelde artikelen doornemen voor meer informatie -
- Wat is een hebzuchtig algoritme?
- Ray Tracing Algorithm
- Algoritme voor digitale handtekeningen
- Wat is Java Hibernate?
- Digitale handtekeningcryptografie
- BFS VS DFS | Top 6 verschillen met infographics