Depth First Search und Labyrinthe

Wenn man alle Knoten eines Graphen besuchen möchte, benutzt meist entweder eine Breitensuche oder eine Tiefensuche. (Übrigens auch, wenn man ein bestimmtes Element sucht. Aber die Knoten einfach nur mal so zu besuchen, ist nett und zeigt, dass man sich um seinen Graphen sorgt.)

1. Man starte an einem Knoten.
2. Man schiebe die noch nicht besuchten Nachbarn auf einen Stack (für die Tiefensuche) oder eine Queue (für die Breitensuche). 
3. Man entnehme einen Knoten vom Stack/Queue und fahre bei 2. fort, bis der Stack/Queue leer ist.

Und weil ich gerade dabei bin, den Wikipedia-Artikel zu wiederholen, mache ich auch weiter damit.

Der beste Anwendungsfall ist nämlich, ein bisschen Zufall in den Algorithmus zu mischen, ein Labyrinth zu bauen und ein Video davon in HD zu posten!

Und weil man dafür weniger als 100 Zeilen Python braucht, spendiere ich auch den Code, falls irgendjemandem das Video nicht reicht. (Oder etwas gegen Youtube hat und sich das Video deshalb lieber selbst bauen würde.)
Außerdem gibt es mir Gelegenheit networkx zu erwähnen. Ein Python Modul, das sehr schöne Klassen für Graphen bereitstellt.

Wer bis hier hin durchgehalten hat, hat es sich verdient, zwei weitere Videos anzusehen.
Hier ist eine Breitensuche, erwartet langweilig:

Und hier bin ich mir nicht sicher, was schief gegangen ist. Aber es ist genial!