Snel naar content
lieselotte zit voor haar computer scherm

Let’s learn about algorithms: Breadth first search

Mijn naam is Lieselotte en ik ben developer bij Inergy. Elke dag programmeer ik voor toffe projecten bij verschillende klanten. Ik spijker mijzelf continu bij op wat meer algemene basis kennis van de IT. Aangezien onze slogan luidt: “Let’s play create and grow together”, dacht ik: “OK! Let’s learn together”. Of je nu net als ik nieuwsgierig bent naar deze IT onderwerpen of dat je wel houdt van een recap momentje, lees dan lekker verder. In deze blog ga ik dieper in op het breadth first search algoritme.

Momenteel ben ik bezig met het bestuderen van verschillende algoritmes. Ik begon mijn zoektocht met het boek “Algorithms – An illustrated guide for programmers and other curious people” door Aditya Y. Bhargava. In dit boek worden bekende algoritmes op een makkelijke manier uitgelegd (vol met plaatjes en voorbeelden, perfect!).

Wat is een algoritme?

Laten we kort even herhalen wat een algoritme ook al weer is. Een algoritme wordt beschreven als een set van instructies om een bepaald doel te bereiken. Elk stuk code dat geschreven word is dus een algoritme. Algoritmes worden interessant wanneer ze een efficiënte oplossing bieden voor complexe problemen.

In deze blog gaan we het Breadth-first search door een bedachte probleemstelling bekijken.

Een algoritme wordt beschreven als een set van instructies om een bepaald doel te bereiken.

Breadth first search algoritme

Stel je voor dat we bij Inergy hard opzoek zijn naar een nieuwe developer. Deze persoon willen wij het liefst vinden via onze eigen connecties op LinkedIn. Om onze recruiters te helpen gaan we een stukje code schrijven die deze persoon aandraagt.

Probleem: Is er een developer in onze connecties die nog niet voor Inergy werkt? Is het antwoord ja, dan willen we als eerst de dichtstbijstaande connectie krijgen.

Om dit voor elkaar te krijgen, zullen we eerst moeten zoeken in jouw eigen set van connecties (of de persoon die de software gebruikt). Heb jij geen developer in jouw connecties dan moeten we gaan zoeken in de connecties van jouw connecties (tweedegraads connecties) en daarna verder zoeken in de derdegraads connecties, enzovoorts.
Om deze zoektocht te doen, maken we een lijstje van onze connecties. We beginnen bij onze eigen connecties en kijken bij elk persoon of dit een developer is. Is het antwoord ja, dan zijn we klaar. Zo niet dan voegen we al zijn connecties toe aan onze lijst en gaan we naar de volgende op ons lijstje en strepen we de gecheckte connectie door. Hieronder heb ik een voorbeeld van zo’n netwerk gevisualiseerd.

Schematisch voorbeel dweergave breadth first search algoritme

Gebruik een queue

Het algoritme werkt alleen wanneer we gebruik maken van een speciale lijst, een zogeheten “queue”. De naam verklapt zijn eigenschap: het is een soort wachtrij waar de eerste die erin komt ook de eerste is die eruit gaat. In een queue worden nieuwe “items” altijd achteraan de rij toegevoegd. Kijk nu nog een keer naar het plaatje van connecties. Stel je voor dat in ons voorbeeld Mark was toegevoegd vóór Anne. Het gevolg zou zijn dat Mark uit ons algoritme komt terwijl Anne een eerstegraads connectie is en Mark een tweedegraads.

Het breadth first search algoritme in code

Oke, laten we nu het algoritme schrijven in een stukje code. Ik heb gekozen om het stukje in Python te schrijven, aangezien de meeste mensen Python makkelijk lezen en anders is het ook een relatief makkelijke taal om mee te beginnen! Tip: mocht je geen Python geïnstalleerd hebben maar je wilt wel even spelen met het algoritme, gebruik dan Jupyter Notebook of Replit in de browser (geen installatie nodig).

Stuur ons gerust een e-mail als je deze code in tekst wil ontvangen.

Breadth first search algoritme voorbeeld

Voorkom een oneindige cirkel

Als je goed kijkt naar de code, dan zie je dat ik nog iets heb verzwegen. We houden ook bij wie we al hebben onderzocht. Probeer te beredeneren waarom dit noodzakelijk is, voordat je verder leest. Als we niet bij houden wie we hebben onderzocht, zouden we terecht kunnen komen in een oneindige cirkel. Stel je voor dat jij een connectie hebt met Jan. Dan heeft Jan ook een connectie met jou. Wanneer het algoritme Jan heeft gecheckt, voegt hij al zijn vrienden toe, waaronder jijzelf. Zonder te checken of het algoritme jou al heeft gecheckt, checkt hij jou opnieuw en zal hij daarna weer alle vrienden toevoegen inclusief Jan! We vermijden dus een oneindige loop door bij te houden wie al onderzocht zijn.

Het Breadth first search algoritme is inzetbaar voor veel meer problemen dan alleen dit voorbeeld. Het algoritme beantwoordt de soort vraag is er een weg van A naar B en zo ja, wat is dan de weg met het minst aantal stappen?

Bedankt voor het lezen van deel 1!

Dit was deel 1 van de serie Let’s Learn about algorithms. In deel 2 kijken we naar het Dijkstra algoritme. We kijken dan naar de verschillen tussen Breadth first search en het Dijkstra algoritme, onderzoeken we welke van de twee soorten algoritmes je gebruikt in welke situatie en schrijven we een voorbeeld-Dijkstra-algoritme.

Blijf op de hoogte

De auteur

Inergy
Inergy

Wij eten, drinken en ademen data – en wat je ermee kan doen. Dat delen we graag met jou. Meer weten over Inergy? Neem contact met ons op via 0348 45 76 66 of info@inergy.nl.

Meer berichten

Alle berichten

Een audit is veel meer dan het invullen van een checklist

Een audit is veel meer dan het invullen van een checklist

Het uitvoeren van een audit is een belangrijk instrument in het beheersen van processen. Een audit is meer dan vinkjes zetten op een checklist. Het uitvoeren van een audit begint met het inzicht krijgen in de processen en bijbehorende werkzaamheden. Wordt er gewerkt volgens de gemaakte afspraken? Zijn er verbeteringen mogelijk? Een audit uitvoeren helpt om dit inzicht te verkrijgen.

Lees verder

Houd een vinger aan de pols: 4 redenen waarom je de prestaties van jouw dataplatform moet monitoren

Houd een vinger aan de pols: 4 redenen waarom je de prestaties van jouw dataplatform moet monitoren

Jouw dataplatform is het hart van je organisatie. Je gaat er iedere dag vanuit dat het blijft kloppen. Maar hoe weet je zeker of dat het geval is? Controleer je die hartslag weleens? In deze blog legt David van Helm, Data Engineer bij Inergy, uit waarom het zo belangrijk is om te weten hoe je een platform presenteert - en hoe je dat voor elkaar krijgt.

Lees verder

Een dag uit het leven van Michel Maters, LIAS Consultant bij Inergy

Een dag uit het leven van Michel Maters, LIAS Consultant bij Inergy

Bij Inergy werken ruim 160 collega’s. Hoe zien hun werkdagen eruit? Deze keer geeft Arjan van Honk, Senior BI Developer/Consultant bij Inergy, een kijkje in zijn werkdag. Een BI-developer is iemand die verantwoordelijk is voor het bouwen en onderhouden van data-oplossingen van onze klanten. Lees over zijn dynamische werkdag in Barcelona in deze blog!

Lees verder