Bezocht
In de wachtrij
Bekeken kanten

  • Huidig
  • In de wachtrij
  • Bezocht
  • Pad
Een klik op een knoop kiest

Meer over breedte-eerst zoeken

Breedte-eerst zoeken (BFS)

Breedte-eerst zoeken verkent een graaf in ringen: eerst elke knoop naast de start, dan elke knoop op twee kanten afstand, enzovoort. Dat gebeurt met een wachtrij: eerst erin, eerst eruit. Klik op een knoop om daar te beginnen, kies eventueel een doel en loop stap voor stap door het zoeken. Zo zie je de wachtrij groeien en krimpen, elke knoop zijn afstand krijgen en een kortste pad verschijnen. Druk op Afspelen om het zoeken te volgen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om ergens heen te springen. Klik op een knoop om die de start te maken; zet de klik op Doel en klik op een andere knoop om een kortste pad ernaartoe te zoeken. Het getal op elke knoop is de afstand tot de start, en de rij onder de graaf is de wachtrij. Nieuwe graaf maakt een andere graaf; kies hoeveel knopen en kanten die heeft. Als het bord geselecteerd is, gaan de pijltjestoetsen een stap verder of terug, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het einde.

Hoe het werkt

  1. Klik op een knoop om die de start te maken. Wil je een pad zoeken, zet de klik dan op Doel en klik op een andere knoop.
  2. Druk op Afspelen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om naar elk punt in het zoeken te springen.
  3. Volg de wachtrij onder de graaf en de afstand op elke knoop. Nieuwe graaf maakt een andere graaf om te proberen.

Zo werkt breedte-eerst zoeken

Zet de startknoop in een wachtrij met afstand 0. Herhaal dan: neem de knoop vooraan in de wachtrij en bekijk elk van zijn buren. Een buur die nog niet gezien is, krijgt een afstand die één hoger is dan die van de genomen knoop, onthoudt die knoop als de weg waarlangs hij bereikt is, en gaat achteraan in de wachtrij. Buren die al gezien zijn, worden overgeslagen. Als de wachtrij leeg is, heeft elke bereikbare knoop zijn afstand.

Waarom het kortste paden vindt

De wachtrij geeft knopen af in de volgorde waarin ze gevonden zijn, en knopen worden ring voor ring gevonden: alle knopen op afstand 1 komen in de wachtrij vóór die op afstand 2, enzovoort. Wordt een knoop voor het eerst bereikt, dan dus via een pad met zo weinig mogelijk kanten. Wie de onthouden knopen terugvolgt van het doel naar de start, vindt dat pad. Dit telt alleen kanten; hebben kanten verschillende lengtes, dan is het algoritme van Dijkstra nodig.

Veelgestelde vragen

Wat is breedte-eerst zoeken?

Een manier om een graaf te verkennen vanaf een startknoop: eerst alle buren, dan hun buren, enzovoort, ring voor ring. Een wachtrij houdt de knopen bij in de volgorde waarin ze gevonden zijn.

Vindt breedte-eerst zoeken het kortste pad?

Ja, als elke kant even zwaar telt: als BFS een knoop voor het eerst bereikt, heeft het zo weinig mogelijk kanten gebruikt. Voor kanten met verschillende lengtes gebruik je in plaats daarvan het algoritme van Dijkstra.

Wat is het verschil tussen BFS en DFS?

Breedte-eerst zoeken gebruikt een wachtrij en breidt gelijkmatig uit, ring voor ring. Diepte-eerst zoeken gebruikt een stapel (of recursie) en volgt één pad zo diep mogelijk voordat het terugkeert. BFS vindt kortste paden in kanten; DFS niet, maar het is handig om cycli te vinden en om topologisch te sorteren.

Hoe snel is breedte-eerst zoeken?

Het haalt elke knoop één keer uit de wachtrij en bekijkt elke kant vanaf beide uiteinden, dus het werk groeit met het aantal knopen plus het aantal kanten.

Wordt mijn graaf ergens heen gestuurd?

Nee. De graaf wordt in je browser gemaakt en doorzocht, en je laatste instellingen blijven in de lokale opslag van deze browser.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Ga naar Editor