Depth First Search und Labyrinthe
Ein Algorithmus, von dem jeder schoneinmal gehört haben sollte, ist die
Tiefensuche (Depth First Search). Wenn man Zusammenhangskomponenten in einem
Graphen finden will oder nach einem bestimmten Knoten in einem Graphen sucht,
ist die Tiefensuche meist der einfachste und oft ein geeigneter Algorithmus
mit einer Zeitkomplexität
- Man startet die Tiefensuche an einem beliebigen Knoten.
- Bei jedem noch nicht besuchten Nachbarn startet man wieder eine Tiefensuche.
Aber was macht man im Alltag mit einer Tiefensuche? Meine Antwort darauf ist: Labyrinthe bauen.
Bei dieser Gelegenheit muss NetworkX
erwähnt werden. Ein Python
Modul, das sehr schöne Klassen für Graphen bereitstellt und perfekt geeignet
ist, um schnell Prototypen von Graphalgorithmen zu testen.
Der Code ist als Gist auf GitHub verfügbar.