Deutsch
Menü

Datenstrukturen und Algorithmen

In einem ungerichteten Graphen sind die Nachbarn der Knoten A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. Eine rekursive Tiefensuche beginnt bei Knoten A. Die Nachbarn werden in der angegebenen Reihenfolge geprüft, und sobald ein unbesuchter Knoten gefunden wird, geht die Suche zu ihm weiter. In welcher Reihenfolge werden die Knoten besucht?

  1. AA, B, C, D, E, F
  2. BA, B, D, E, C, F
  3. CA, B, D, E, F, C
Antwort und Erläuterung anzeigen

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

Von A geht die Suche zu B und dann zu D, dem ersten unbesuchten Nachbarn von B. Der einzige Nachbar von D, nämlich B, ist bereits besucht; die Suche kehrt zu B zurück, geht weiter zu E, von E zum unbesuchten F und von F zu dessen Nachbarn C. Die Reihenfolge ist daher A, B, D, E, F, C. A, B, C, D, E, F ist die Reihenfolge der Breitensuche, die die nächstgelegenen Knoten zuerst besucht. A, B, D, E, C, F kehrt bei E um, ohne zum unbesuchten F zu gehen, und ist daher keine Reihenfolge einer Tiefensuche.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. In einem ungerichteten Graphen haben die Kanten die Gewichte (Entfernungen) S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 und A−T: 6. Welcher kürzeste Weg von S nach T und welche Länge ergeben sich mit dem Dijkstra-Algorithmus?
  2. Welche Bedingung an den Graphen ist erforderlich, damit der Dijkstra-Algorithmus korrekte kürzeste Wege findet?
  3. Für die Aufgaben A bis E gelten die Reihenfolgebedingungen „A vor C“, „B vor C“, „C vor D“, „B vor E“ und „E vor D“. Welche Reihenfolge erfüllt alle Bedingungen (ein Ergebnis der topologischen Sortierung)?
  4. Eine Funktion f(x, y) ist definiert als „ist y gleich 0, gib x zurück; andernfalls gib f(y, x mod y) zurück“. Welchen Rückgabewert liefert der Aufruf f(84, 36), und wie oft wird f aufgerufen, den ersten Aufruf eingeschlossen?
  5. Eine Funktion fib(n) für die Fibonacci-Zahlen ist rekursiv definiert als „ist n kleiner oder gleich 1, gib n zurück; andernfalls gib fib(n−1) + fib(n−2) zurück“. Wie oft wird fib beim Aufruf von fib(5) aufgerufen, den ersten Aufruf eingeschlossen?