Nederlands
Menu

Datastructuren en algoritmen

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?

  1. AA, B, C, D, E, F
  2. BA, B, D, E, C, F
  3. CA, B, D, E, F, C
Antwoord en toelichting tonen

Antwoord: C. A, B, D, E, F, C

Vanuit A gaat de zoekactie naar B en dan naar D, de eerste onbezochte buur van B. De enige buur van D, B, is al bezocht, dus de zoekactie keert terug naar B en gaat verder naar E, dan van E naar de onbezochte F en van F naar haar buur C. De volgorde is dus A, B, D, E, F, C. A, B, C, D, E, F is de volgorde van breedte-eerst zoeken, dat de dichtstbijzijnde knopen eerst bezoekt. A, B, D, E, C, F keert bij E terug zonder naar de onbezochte F te gaan en is dus geen volgorde van diepte-eerst zoeken.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

  1. 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?
  2. Aan welke voorwaarde moet de graaf voldoen opdat het algoritme van Dijkstra juiste kortste paden vindt?
  3. 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)?
  4. 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?
  5. Een functie fib(n) voor Fibonaccigetallen is met recursie gedefinieerd als „als n kleiner dan of gelijk aan 1 is, geef n terug; geef anders fib(n−1) + fib(n−2) terug”. Hoe vaak wordt fib aangeroepen als fib(5) wordt aangeroepen, de eerste aanroep meegerekend?