Nederlands
Menu

Wat is Breedte-eerst zoeken (breadth-first search)?

Manier om een graaf of boom te doorzoeken die knopen bezoekt in volgorde van afstand tot het startpunt: eerst die op één kant afstand, dan die op twee kanten, enzovoort. Ze wordt geïmplementeerd met een wachtrij en vindt in een graaf zonder gewichten op de kanten het kleinste aantal kanten van het startpunt naar elke knoop. Afgekort als BFS.

Japanse benaming: 幅優先探索

“Breedte-eerst zoeken (breadth-first search)” komt voor in 4 oefenvragen uit 1 onderwerpen, bijv. Datastructuren en algoritmen.

Vakgebied: Datastructuren en algoritmen

Nu oefenen: vragen over Breedte-eerst zoeken (breadth-first search)

In een lege wachtrij worden de elementen A, B en C in deze volgorde geplaatst. Daarna wordt er één element uitgehaald, wordt D toegevoegd en weer één uitgehaald, en wordt E toegevoegd en nog één uitgehaald. In welke volgorde worden de elementen uitgehaald?

  1. AA, B, C
  2. BC, D, E
  3. CC, B, A
Antwoord en toelichting tonen

Antwoord: A. A, B, C

Een wachtrij is een first-in-first-out-structuur (FIFO): elementen worden uitgehaald in de volgorde waarin ze zijn toegevoegd. Nadat A, B en C zijn toegevoegd, haalt de eerste bewerking A eruit. Ook al worden D en E daarna achteraan toegevoegd, B en C staan vooraan en gaan eerst, dus de volgorde is A, B, C, en D en E blijven over. C, D, E is de volgorde van een stack (LIFO), die telkens het laatst toegevoegde element verwijdert. Wachtrijen worden gebruikt voor afdrukopdrachten, voor message queues die gegevens tussen taken doorgeven en voor breedte-eerst zoeken.

Wat is een geschikte manier om een ijle graaf, een graaf met weinig kanten in verhouding tot het aantal knopen, in het geheugen op te slaan, zoals een wegennet met ongeveer 1 miljoen knopen en 3 miljoen kanten?

  1. AEen adjacentiematrix: die controleert in O(1) of twee knopen verbonden zijn en gebruikt ook het minste geheugen
  2. BAdjacentielijsten: het geheugen is evenredig met het aantal knopen plus het aantal kanten, en ze zijn geschikt om de kanten vanuit een knoop één voor één te volgen
  3. CEen adjacentiematrix: het geheugen is alleen evenredig met het aantal kanten
Antwoord en toelichting tonen

Antwoord: B. Adjacentielijsten: het geheugen is evenredig met het aantal knopen plus het aantal kanten, en ze zijn geschikt om de kanten vanuit een knoop één voor één te volgen

Een adjacentiematrix gebruikt voor V knopen een tabel van V × V, dus 1 miljoen knopen vragen 10¹² elementen, ongeveer 125 GB, zelfs met 1 bit per element. Adjacentielijsten bevatten per knoop alleen de buren, dus het geheugen is O(V + E), in dit voorbeeld maar enkele miljoenen elementen. Een adjacentiematrix heeft het voordeel dat een kant in O(1) kan worden gecontroleerd, en is geschikt voor dichte grafen of grafen met weinig knopen. Voor bewerkingen die de kanten vanuit elke knoop één voor één volgen, zoals breedte-eerst zoeken en het algoritme van Dijkstra, zijn adjacentielijsten efficiënter.

“Breedte-eerst zoeken (breadth-first search)” in de toelichting

Vragen met “Breedte-eerst zoeken (breadth-first search)” (4)

  1. In een lege wachtrij worden de elementen A, B en C in deze volgorde geplaatst. Daarna wordt er één element uitgehaald, wordt D toegevoegd en weer één uitgehaald, en wordt E toegevoegd en nog één uitgehaald. In welke volgorde worden de elementen uitgehaald?
  2. Wat is een geschikte manier om een ijle graaf, een graaf met weinig kanten in verhouding tot het aantal knopen, in het geheugen op te slaan, zoals een wegennet met ongeveer 1 miljoen knopen en 3 miljoen kanten?
  3. In een graaf waarvan de kanten geen gewicht hebben, wil je vanaf een startknoop het kleinste aantal kanten naar elke andere knoop bepalen. Welke combinatie van zoekmethode en datastructuur is geschikt?
  4. In een ongerichte graaf zijn de buren van elke knoop A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. Diepte-eerst zoeken met recursie begint bij knoop A. De buren worden in de vermelde volgorde onderzocht, en zodra een nog niet bezochte knoop wordt gevonden, gaat de zoekactie daarheen. In welke volgorde worden de knopen bezocht?

Verwante termen

Wachtrij (queue) Stack (stapelgeheugen) Diepte-eerst zoeken (depth-first search) Recursie Algoritme van Dijkstra Binair zoeken (binary search) Binaire heap (binary heap) Binaire zoekboom (binary search tree) Dynamisch programmeren (dynamic programming) Gelinkte lijst (linked list)

Naar de woordenlijst