Deutsch
Menü

Datenstrukturen und Algorithmen

In einem Graphen mit ungewichteten Kanten soll die kleinste Zahl von Kanten vom Startknoten zu jedem anderen Knoten bestimmt werden. Welche Kombination aus Suchverfahren und Datenstruktur ist geeignet?

  1. ABreitensuche mit einer Warteschlange
  2. BTiefensuche mit einem Stack
  3. CBreitensuche mit einem Stack
Antwort und Erläuterung anzeigen

Antwort: A. Breitensuche mit einer Warteschlange

Die Breitensuche besucht die Knoten nach ihrer Entfernung: zuerst die eine Kante vom Start entfernten, dann die zwei Kanten entfernten und so weiter. Jeden neu gefundenen Knoten hinten in eine Warteschlange einzufügen und die Knoten vorn zu entnehmen, bewahrt diese Reihenfolge „Nächste zuerst“; die Zahl der Kanten beim ersten Erreichen eines Knotens ist daher die kürzeste. Die Tiefensuche (mit Rekursion oder einem Stack) geht auf einem Pfad so weit wie möglich und kann einen Knoten zuerst auf einem Umweg erreichen; kürzeste Entfernungen sind daher nicht garantiert. Verwendet man statt einer Warteschlange einen Stack, wird der Durchlauf einer Tiefensuche ähnlich.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. 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?
  2. 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?
  3. Welche Bedingung an den Graphen ist erforderlich, damit der Dijkstra-Algorithmus korrekte kürzeste Wege findet?
  4. 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)?
  5. 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?