Dies ist eine alte Version des Dokuments!
Kürzester Pfad nach Kantenzahl
Quacki der Frosch
Quacki sitzt in seinem wunderschönen Seerosenteich gemütlich auf einem Seerosenblatt und wartet auf Fliegen - seine Lieblingsspeise. Gelegentlich hüpft er zu einem anderen Blatt, wenn dort eine Fliege umherfliegt. Um möglichst schnell bei der Fliege zu sein, nimmt er denjenigen Weg, bei dem er am wenigsten Sprünge machen muss. Wie viele Sprünge muss Quacki maximal machen, um auf diese Weise zu einem beliebigen anderen Blatt zu kommen.
Hilf ihm bei der Antwort! Dabei muss die maximale Sprungweite (schwarzer Balken im Bild) berücksichtigt werden. Die Entfernung wird immer von Mitte zur Mitte der Blätter gemessen.
(A1) Modellierung als Graph
Öffne im Graphentester die Datei 03_routenplanung/01_seerosenteich.csv. Sie enthält eine Grafik des Teichs. Du kannst den Graphen im Bearbeitungsmodus des Graphentesters direkt auf den Teich zeichnen.
- Eingabe: Ein Graph und ein Startknoten
- Ausgabe: Die Entfernung in der Einheit "Kanten" zwischen dem Startknoten und jedem Knoten des Graphen.
(A2) Angepasste Breitensuche
Das Problem kann man mit einer angepassten Breiten suche lösen. Wie?
- Schreibe den Algorithmus für die Breitensuche als Pseudocode auf.1)
- Was kannst du ändern, um dir die "Ebenenweise" Bearbeitung der Knoten bei der Breitensuche zunutze zu machen, um den Abstand jedes Knotens vom Startknoten zu ermitteln?