Nederlands
Menu

Datastructuren en algoritmen

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?

  1. ABreedte-eerst zoeken met een wachtrij
  2. BDiepte-eerst zoeken met een stack
  3. CBreedte-eerst zoeken met een stack
Antwoord en toelichting tonen

Antwoord: A. Breedte-eerst zoeken met een wachtrij

Breedte-eerst zoeken bezoekt knopen in volgorde van afstand: eerst die op één kant van de start, dan die op twee kanten, enzovoort. Door elke nieuw gevonden knoop achteraan een wachtrij te zetten en knopen vooraan weg te nemen, blijft deze volgorde (dichtstbijzijnde eerst) behouden, zodat het aantal kanten bij het eerste bereiken van een knoop het kortste is. Diepte-eerst zoeken (met recursie of een stack) gaat langs één pad zo ver mogelijk door en kan een knoop dus eerst via een omweg bereiken; kortste afstanden zijn niet gegarandeerd. Wie een stack gebruikt in plaats van een wachtrij, krijgt een doorloop die op diepte-eerst zoeken lijkt.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

  1. 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?
  2. In een ongerichte graaf zijn de gewichten (afstanden) van de kanten S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 en A−T: 6. Welk kortste pad van S naar T vindt het algoritme van Dijkstra, en wat is de lengte ervan?
  3. Aan welke voorwaarde moet de graaf voldoen opdat het algoritme van Dijkstra juiste kortste paden vindt?
  4. Voor de taken A tot E gelden de volgordebeperkingen „A vóór C”, „B vóór C”, „C vóór D”, „B vóór E” en „E vóór D”. Welke volgorde voldoet aan alle beperkingen (een resultaat van topologisch sorteren)?
  5. Een functie f(x, y) is gedefinieerd als „als y gelijk is aan 0, geef x terug; geef anders f(y, x mod y) terug”. Wat is de teruggegeven waarde van f(84, 36), en hoe vaak wordt f aangeroepen, de eerste aanroep meegerekend?