Prolog-Das Haus des Nikolaus
Aus ProgrammingWiki
Vollständiger Graphendurchlauf
|
Problem: Das bekannte Nikolaushaus soll in einem Zug gezeichnet werden, d.h. jede Kante wird dabei genau einmal durchlaufen. Im Gegensatz zum Königsberger Brückenproblem (Eulerzyklus) müssen dabei Start- und Zielknoten nicht übereinstimmen. Wie viele Möglichkeiten des vollständigen Durchlaufs dieses Graphen gibt es? Lösungsidee: Zunächst werden alle in Frage kommenden Strecken aus der Datenbasis herausgesucht und in einer Streckenliste gesammelt. Das erste Element der gewünschten Reiseroute (Knotenliste) soll der Startknoten des vollständigen Graphendurchlaufs sein. Durch Tiefensuche werden nun die entsprechenden Kanten ermittelt und dabei aus der Streckenliste herausgestrichen. Eine vollständiger Durchlauf ist dann gefunden, wenn die vorgegebene Streckenliste leer ist. |
 |
