Suchen in Graphen

In vielen Anwendungen muss man alle Knoten eines Graphen durchsuchen. Z.B. bei der Suche nach einem Schatz oder dem Ausgang in einem Labyrinth wird man einen Weg weiterverfolgen, bis man in einer Sackgasse landet oder an einer Kreuzung ankommt, von der aus man bereits alle Wege erkundet hat. Dieses Vorgehen nennt man Tiefensuche. Dem gegenüber steht die Breitensuche, die u.a. bei der Bestimmung eines Kürzesten-Wege-Baumes in ungewichteten Graphen verwendet wird. Beide Algorithmen erzeugen aufspannende Bäume in Graphen, deren Gestalt jedoch sehr unterschiedlich ist.
In dem folgenden Applet können Tiefen- und Breitensuche auf einem beliebigen Graphen gestartet und beobachtet werden. Die unterschiedliche Gestalt der jeweiligen Ergebnisse wird besonders gut erkennbar, indem die Algorithmen automatisch ausgeführt werden und dann zwischen Breiten- und Tiefensuche umgeschaltet wird. Lesen Sie mehr...

Random Walks in Graphen

Wir simulieren einen Random Walk in einem Graphen. Dabei startet man in einem vorgegebenen Knoten. In jedem Schritt wird zufällig eine aus diesem Knoten ausgehende Kante gewählt, die dann zum benachbarten Knoten verfolgt wird. Dies wird n-mal Iteriert. Die Wahrscheinlichkeiten, mit denen die ausgehenden Kanten gewählt werden können dabei über Kantengewichte bestimmt werden.
Das Ergebnis der Simulation wird Graphisch dargestellt, in dem die Kanten entsprechend der Häufigkeit, mit der sie gewählt wurden unterschiedlich dick und farbig markiert werden. Lesen Sie mehr...

Animationen: Eine Tour abfahren

Das Visage-Paket erlaubt unter Einsatz von CindyScript auch verschiedene Arten von Animationen. So ist es auch möglich, kleinere Graphiken entlang von Pfaden laufen zu lassen. Lesen Sie mehr...