1. Kurzbeschreibung:
Graphische Darstellung von Algorithmen zur Bestimmung von minimalen spannenden Bäumen in einem Graphen (minimal spanning trees).
Die Simulation soll folgende Elemente umfassen:
ein Eingabemodul für die Spezifikation eines gewichteten Graphen
eine graphische Darstellung des Graphen (Knoten und gewichtete Kanten)
eine animierte Darstellung der Ermittlung eines minimalen spannenden Baums in dem Graphen nach einem bestimmten Algorithmus (z.B. Boruvka oder Kruskal)
Was kann das Applet?
Dieses Applet vereint eine Darstellung eines (ungerichteten) gewichteten Graphen mit der Ermittlung
von einem minimalspannendem Baum nach zwei (unterschiedlichen, wählbaren) Algorithmen.
Wie gebe ich einen Graphen ein?
Durch drücken des Buttons Graph editieren öffnet ein Eingabefenster.
Geben Sie Start- und Zielknoten sowie das Gewicht der Kante (Wert zwichen 1 und 999) ein und drücken sie
Hinzufügen. Zum Löschen einer Kante markieren Sie sie und drücken Entfernen, zum Ändern markieren Sie die
betreffende Kante und geben die Änderungen in die Felder von, nach und Gewicht ein, drücken Sie dann
Ändern.
Mit Graph neu können Sie den ganzen Graphen löschen.
Durch drücken der Buttons Beispiel 1, Beispiel 2 und Beispiel 3 können sie vorbereitete Beispielgraphen
hinzufügen.
Mit OK übernehmen sie die Eingabe, mit Abbrechen verwerfen Sie sie. Das Eingabefenster wird geschlossen.
Nun wird Ihr Graph aufgebaut und angezeigt.
Wie beeinflusse ich die Darstellung des Graphen?
Der Zeichenalgorithmus versucht ihren Graphen optimal darzustellen. Es kann aber passieren, das sich Knoten und
Kanten überlagern oder eine ungünstige Darstellung entsteht. Sie haben nun mehrere Möglichkeiten:
Mit Neu anordnen können sie den Algorithmus zu einem neuen Zeichenversuch zwingen.
Mit Rütteln wird jeder Knoten etwas bewegt, um den Graphen aus einer eventuell ungünstigen Balance zu befreien.
Weiterhin können Sie jeden Knoten mit der Maus bewegen und durch Klicken beider Maustasten (Rechte und Linke) an einer Position
befestigen. Drücken Sie Festhalten, um alle Knoten zu befestigen und Alle loslassen, um die
Befestigung wieder aufzuheben.
Minimal spannende Bäume ermitteln
Um aus ihrem Graphen einem minimal spannenden Baum zu ermitteln, drücken Sie Alg. von Kruskal oder
Alg. von Boruvka, je nach dem, welchen Algorithmus sie verwenden wollen.
Wenn es einen solchen minimal spannenden Baum gibt, werden alle Kanten, die zu ihm gehören, farbig hervorgehoben.