Kruskal-Algorithmus

Greedy-Algorithmus zur Berechnung eines minimalen aufspannenden Baumes. Er untersucht in jedem Schritt eine billigste unbehandelte Kante und wählt diese, falls sie keinen Kreis schließt.

Aufgabe a)
Aufgabe b) Applet , mit dem ein Graph erzeugt werden kann, an dem der Kruskal-Algorithmus demonstriert wird

Aufgabe c) Erzeugen Sie in diesem Applet einen Graphen mit 10 Knoten.
- 10 Knoten mit der Maus setzen
- rechts auf Pfeil neben Add Vertex und dann Add Undirected Edge auswählen
- Knoten durch Anklicken miteinander verbinden
- Modify Edge or Vertex rechts auswählen
- Kästchen auf der Kante anklicken - ein Fenster öffnet sich
- im Fenster ein Gewicht (zum Beispiel Kilometer) für die Kante eingeben
- links Kruskal's Algorithm auswählen, dann Next, Next, ... , bis der minimale Spannbaum gefunden ist

Aufgabe d) Kleiner Kurs zum Kruskal-Algorithmus