home

Die Klasse Graph und der Graphen-Editor

K12
Der vollständige Graph K12
mathGUIde: Graph.complete(12)

Die folgenden Beispiele zeigen einige Möglichkeiten der Klasse Graph, des Graphen-Editors und des Wechselspiels zwischen beiden.

Ein Graph besteht aus Knoten und Kanten. Eine Kante verbindet zwei Knoten.
Zwar gehört zur Definiton eines Graphen keine Information über eine geometrische Anordnung. In der Praxis hilft es aber oft, wenn man einen Graphen als Punkte (Knoten) und Verbindungslinien (Kanten) zeichnet.

Wir definieren zunächst einen Graphen mit drei Knoten (1, 2, 3) und zwei Kanten, die Knoten 1 mit den beiden anderen Kanten verbinden. Die statische Methode Graph.fromShortRepr verlangt als Parameter einen String, in dem durch | getrennt die Knoten und die Kanten (von, nach), jeweils durch Semikolon getrennt, angegeben werden.

Dieser „reine“ Graph enthält keine geometrischen Informationen. Damit man alle Knoten sehen kann, hat mathGUIde sie willkürlich aufgereiht.

Man kann aber auch zu jedem Knoten zwei Koordinaten (x und y) angeben:

Jetzt definieren wir einen gewichteten Graphen. Dazu wird bei den Kanten als dritter Wert das Gewicht angegeben.

Nach „Ausführen“ sehen Sie eine Darstellung des Graphen mit seinen Gewichten.

Um mit Hilfe des Algorithmus von Kruskal einen „minimalen Spannbaum“ zu ermitteln, entfernen Sie bitte in Zeile 1 die Kommentierung (//) und klicken nochmals auf „Ausführen“. Wenn Sie auch noch die Zeile 2 auskommentieren, wird der Graph auf den Spannbaum reduziert.

Mit dem Dijkstra-Algorithmus berechnen wir einen kürzesten Weg von Knoten 2 nach Knoten 6:

home