Bezocht
Op de stapel
Bekeken kanten

  • Huidig
  • Op de stapel
  • Afgerond
  • Pad
Een klik op een knoop kiest

Meer over diepte-eerst zoeken

Diepte-eerst zoeken (DFS)

Diepte-eerst zoeken verkent een graaf zoals iemand die door een doolhof loopt met één hand aan de muur: het volgt één pad zo ver als het gaat, en gaat pas terug als er niets nieuws meer is. Dat doet het met een stapel. Klik op een knoop om daar te starten, kies eventueel een doel, en ga stap voor stap door het zoeken: zie de stapel groeien en krimpen, elke knoop zijn bezoeknummer krijgen, en de kanten die een cykel sluiten. 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 pad ernaartoe te zoeken. Het getal op elke knoop is de volgorde waarin die bezocht is, en de rij onder de graaf is de stapel, van de start tot de knoop bovenaan. 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 stapel onder de graaf en het bezoeknummer op elke knoop. Nieuwe graaf maakt een andere graaf om te proberen.

Hoe diepte-eerst zoeken werkt

Zet de startknoop op de stapel. Herhaal dan: bekijk de volgende buur van de knoop bovenaan de stapel. Een buur die nog niet gezien is, krijgt het volgende bezoeknummer, onthoudt de knoop vanwaar hij bereikt is, en gaat bovenop de stapel, zodat het zoeken daar verdergaat. Als de knoop bovenaan geen buren meer heeft om te bekijken, is hij afgerond en gaat hij van de stapel, en gaat het zoeken terug naar de knoop eronder. Als de stapel leeg is, is elke bereikbare knoop bezocht.

Wat de stapel je vertelt

Omdat het zoeken altijd verdergaat vanaf de nieuwste knoop, is de stapel altijd een pad van de start naar de knoop die bekeken wordt. Wordt het doel bereikt, dan is de stapel een pad ernaartoe, al is dat meestal niet het kortste: dat vindt breedte-eerst zoeken. In een graaf zonder richtingen sluit een kant naar een knoop die nog op de stapel ligt, behalve de knoop waar het zoeken net vandaan kwam, een cykel. De onthouden knopen vormen een boom, de diepte-eerst-boom, en de volgorde waarin knopen worden afgerond is de sleutel tot topologisch sorteren.

Veelgestelde vragen

Wat is diepte-eerst zoeken?

Een manier om een graaf vanaf een startknoop te verkennen door één pad zo diep mogelijk te volgen, en pas terug te gaan om een andere tak te proberen als er niets nieuws meer is. Het gebruikt een stapel, of recursie, om de weg terug te onthouden.

Vindt diepte-eerst zoeken het kortste pad?

Nee. Het vindt een pad naar het doel als dat er is, maar dat pad kan veel langer zijn dan nodig, omdat DFS vasthoudt aan de eerste tak die het probeert. Gebruik breedte-eerst zoeken voor de minste kanten, of het algoritme van Dijkstra als kanten een lengte hebben.

Wat is het verschil tussen DFS en BFS?

Diepte-eerst zoeken gebruikt een stapel en gaat diep langs één pad voordat het teruggaat. Breedte-eerst zoeken gebruikt een wachtrij en breidt gelijkmatig uit, ring na ring. Beide bezoeken elke bereikbare knoop in een tijd die groeit met het aantal knopen plus kanten; BFS vindt kortste paden, terwijl DFS de natuurlijke keuze is voor cykels, doolhoven en topologisch sorteren.

Hoe vindt DFS een cykel?

Als het zoeken in een graaf zonder richtingen een kant tegenkomt naar een knoop die nog op de stapel ligt, en dat is niet de knoop waar het net vandaan kwam, dan sluit die kant een lus. In de app meldt de statusregel dat wanneer het gebeurt.

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