Der Kruskal-Algorithmus

Der Algorithmus von Kruskal

Der Algorithmus von Kruskal basiert auf den Eigenschaften eines minimalen Spannbaumes. Man beginnt mit der sortierten Liste von Kanten, welche in aufsteigender Reihenfolge sortiert sei. Eine Kante (Verbindungsstrecke) gehört zur Lösung, wenn sie zwei verschiedene Bäume verbindet (wenn die Kante also hinzugefügt werden kann, ohne dass ein Zyklus entsteht). Die Kanten werden dann einzelnt und nacheinander betrachtet. Man entscheidet dann, ob die Kante zur Lösung gehört oder nicht.

Zusammenfassend:

-       Kein Zyklus erlaubt

-       Kanten müssen Minimalbedingung erfüllen

  • Dadurch realisierbar, dass man sich die Kanten nacheinander anschaut.

Krusal Algorithmus in Java:

public class Kruskal

{

// Kanten aufsteigend sortieren

List<Edge> edges = g.getSortedEdgesList();

Graph spanningTree = new Graph();

Edge newEdge;

while(!edges.istEmpty())

{

newEdge = edges.getFirst();

 

if(!containsCycles(spanningTree, newEdge))

{

spanningTree.add(newEdge);

}

}

}