Kruskals Algorithmus
Der Spannbaum eines ungerichteten Graphen besteht aus einer Teilmenge der Kanten des Graphen, so dass trotzdem alle Knoten verbunden sind. Für jedes Paar von Knoten besteht die Verbindung zwischen ihnen aus genau einem Pfad.
Kruskals Algorithmus berechnet einen Spannbaum, bei dem die mit den Kanten assoziierten Kosten in der Summe minimal sind. Für Spannbäume allgemein und für solche mit minimalen Kosten kann es für einen Graphen mehrere Möglichkeiten geben.
Instanzen der Klasse edge repräsentieren ungerichtete Kanten mit zugeordneten Kosten. Dem Konstruktor werden eine zwei-elementige Liste (die Knoten des Graphen, die durch die Kante verbunden werden) und eine nicht-negative Zahl (die Kosten) übergeben.
(defclass edge ())
(defmethod initialize ((this edge) between cost)
(and
(= (length between) 2)
(number? cost)
(not (< cost 0)))
(progn
(.= this between between)
(.= this cost cost)
(freeze this)))
Die Methode cheaper? prüft, ob die erste übergebene Kante niedrigere Kosten hat, als die zweite.
(defmethod cheaper? ((this edge) (that edge))
t
(< (. this cost) (. that cost)))
Für die Repräsentation von Graphen werden die Instanzen der Klasse graph genutzt. Dem Konstruktor übergibt man die Liste der Kanten des Graphs.
(defclass graph ())
(defmethod initialize ((this graph) edges)
(every?
(lambda (element) (= edge (class-of element)))
edges)
(progn
(.= this edges edges)
(freeze this)))
Die Hilfsmethode get-sorted-edges liefert die Kanten des Graphen in einer Prioritätswarteschlange. Die Kante mit den niedrigsten Kosten steht zuerst in der Schlange.
(defmethod get-sorted-edges ((this graph))
t
(let
((queue (new pairing-heap cheaper?)))
(dolist (edge (. this edges) queue)
(setq queue (insert-into queue edge)))))
Die Hilfsmethode get-initial-partition liefert eine Partition (siehe Partitionen) der Knoten des Graphen. Die Teilmengen der Partition enthalten jeweils einen Knoten.
(defmethod get-initial-partition ((this graph))
t
(let
((parts (new partition)))
(dolist (edge (. this edges) parts)
(map-with
(lambda (vertex)
(catch nil
(make-set parts (list vertex))))
(. edge between)))))
Kruskals Algorithmus arbeitet die Kanten aus der Prioritätswarteschlange ab. Für jede Kante wird geprüft, ob die beiden Enden in verschiedenen Teilmengen der Partition liegen. Wenn ja, wird die Kante dem Spannbaum hinzugefügt und die beiden Teilmengen der Partition werden verschmolzen. Sobald die Partition nur noch eine Teilmenge enthält, ist der Spannbaum gefunden. Die Methode liefert dessen Kanten als Liste.
(defmethod get-minimum-cost-spanning-edges ((this graph))
t
(let
((parts (get-initial-partition this))
(queue (get-sorted-edges this))
(spanning-tree nil))
(loop
(when (= (get-set-count parts) 1)
(return spanning-tree))
(let
((edge (head queue)))
(with-slots-read-only (between) edge
(unless (in-same-set? parts (first between) (second between))
(join-sets parts (first between) (second between))
(setq spanning-tree (cons edge spanning-tree)))))
(setq queue (tail queue)))))
Links
https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
http://www.carlschroedl.com/blog/comp/kruskals-minimum-spanning-tree-algorithm/2012/05/14/
Kruskals Algorithmus berechnet einen Spannbaum, bei dem die mit den Kanten assoziierten Kosten in der Summe minimal sind. Für Spannbäume allgemein und für solche mit minimalen Kosten kann es für einen Graphen mehrere Möglichkeiten geben.
Instanzen der Klasse edge repräsentieren ungerichtete Kanten mit zugeordneten Kosten. Dem Konstruktor werden eine zwei-elementige Liste (die Knoten des Graphen, die durch die Kante verbunden werden) und eine nicht-negative Zahl (die Kosten) übergeben.
(defclass edge ())
(defmethod initialize ((this edge) between cost)
(and
(= (length between) 2)
(number? cost)
(not (< cost 0)))
(progn
(.= this between between)
(.= this cost cost)
(freeze this)))
Die Methode cheaper? prüft, ob die erste übergebene Kante niedrigere Kosten hat, als die zweite.
(defmethod cheaper? ((this edge) (that edge))
t
(< (. this cost) (. that cost)))
Für die Repräsentation von Graphen werden die Instanzen der Klasse graph genutzt. Dem Konstruktor übergibt man die Liste der Kanten des Graphs.
(defclass graph ())
(defmethod initialize ((this graph) edges)
(every?
(lambda (element) (= edge (class-of element)))
edges)
(progn
(.= this edges edges)
(freeze this)))
Die Hilfsmethode get-sorted-edges liefert die Kanten des Graphen in einer Prioritätswarteschlange. Die Kante mit den niedrigsten Kosten steht zuerst in der Schlange.
(defmethod get-sorted-edges ((this graph))
t
(let
((queue (new pairing-heap cheaper?)))
(dolist (edge (. this edges) queue)
(setq queue (insert-into queue edge)))))
Die Hilfsmethode get-initial-partition liefert eine Partition (siehe Partitionen) der Knoten des Graphen. Die Teilmengen der Partition enthalten jeweils einen Knoten.
(defmethod get-initial-partition ((this graph))
t
(let
((parts (new partition)))
(dolist (edge (. this edges) parts)
(map-with
(lambda (vertex)
(catch nil
(make-set parts (list vertex))))
(. edge between)))))
Kruskals Algorithmus arbeitet die Kanten aus der Prioritätswarteschlange ab. Für jede Kante wird geprüft, ob die beiden Enden in verschiedenen Teilmengen der Partition liegen. Wenn ja, wird die Kante dem Spannbaum hinzugefügt und die beiden Teilmengen der Partition werden verschmolzen. Sobald die Partition nur noch eine Teilmenge enthält, ist der Spannbaum gefunden. Die Methode liefert dessen Kanten als Liste.
(defmethod get-minimum-cost-spanning-edges ((this graph))
t
(let
((parts (get-initial-partition this))
(queue (get-sorted-edges this))
(spanning-tree nil))
(loop
(when (= (get-set-count parts) 1)
(return spanning-tree))
(let
((edge (head queue)))
(with-slots-read-only (between) edge
(unless (in-same-set? parts (first between) (second between))
(join-sets parts (first between) (second between))
(setq spanning-tree (cons edge spanning-tree)))))
(setq queue (tail queue)))))
Links
https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
http://www.carlschroedl.com/blog/comp/kruskals-minimum-spanning-tree-algorithm/2012/05/14/