Kruskalův algoritmus

Kruskalův algoritmus slouží k nalezení minimální kostry grafu (kostry takové, že součet vah jejích hran je minimální). Algoritmus byl poprvé publikován v roce 1956 Josephem Kruskalem.

Princip

Kruskalův algoritmus nejprve setřídí hrany dle jejich váhy (od nejmenší) a následně přidává hrany do grafu takovým způsobem, aby nevznikl žádný cyklus (tj. procedura terminuje po přidání $\\vert U \\vert -1$ hran).

K zajištění acykličnosti si algoritmus pomocí datové struktury disjoint set udržuje pro každý uzel informaci o příslušnosti ke komponentě souvislosti. Disjoint set poskytuje dvě operace: union (spojí dvě komponenty souvislosti) a find (zjistí pro daný uzel příslušnost ke komponentě souvislosti).

Asymptotická složitost algoritmu

Časová složitost algoritmu je v případě použití řadicího algoritmu založeného na porovnávání $O(\\vert H\\vert \\cdot \\log \\vert H \\vert)$ . Pokud jsou hrany již předřazeny, nebo je možno k jejich seřazení použít řadicí algoritmus s lineární složitostí (např. counting sort), tak je složitost Kruskalova algoritmu rovna $O(\\vert H\\vert \\cdot \\alpha(\\vert H \\vert))$ , kde $\\alpha$ je inverzní Ackermannova funkce (odpovídá složitosti operací union a find).

 /**
  * Kruskaluv algoritmus
  * @param graph graf
  * @param w vahy jednotlivych hran
  * @return minimalni kostra grafu
  */
 SpanningTree kruskalAlgorithm(Graph graph, weights w)
     SpanningTree tree //kostra
     for Node n : graph do
         makeSet(n) //kazdy uzel je v samostatnem setu
     List edges = sort(graph.getEdges(), w) //seradi hrany podle vah
     
     for Edge e in edges do
         if findSet(e.start) != findSet(e.end) //pokud jsou pocatecni a koncovy uzel v ruznych setech (netvorime cyklus)
             tree.add(e) //pridej hranu do kostry
             union(e.start, e.end) //sety spojime v jeden
             if tree.edgeCount() == graph.nodeCount() - 1 //pokud uz je kostra cela
                 break //konec pridavani hran
     return tree

 /**
  * Kruskaluv algoritmus
  * @author Pavel Micka
  */
 public class KruskalAlgorithm {
     /**
      * Nalezne minimalni kostru neorientovaneho grafu o n uzlech (cisla uzlu
      * 0, 1, ..., n-1)
      * @param edges hrany neorientovaneho grafu
      * @param nodeCount pocet uzlu neorientovaneho grafu (n)
      * @return minimalni kostra
      */
     public static List<Edge> kruskalAlgorithm(List<Edge> edges, int nodeCount) {
         DisjointSet ds = new DisjointSet(nodeCount);
         List<Edge> spanningTree = new ArrayList<Edge>();
         Collections.sort(edges);
         int i = 0;
         while (i != edges.size() && spanningTree.size() != nodeCount - 1) {
             Edge e = edges.get(i);
             if(ds.find(e.getFrom()) != ds.find(e.getTo())){
                 spanningTree.add(e);
                 ds.union(e.getFrom(), e.getTo());
             }
             i++;
         }
         return spanningTree;
     }
 }
 
 
 // ***************************** //
 // *     DATOVE STRUKTURY      * //
 // ***************************** //
 
 
 /**
  * Hrana neorientovaneho grafu
  * @author Pavel Micka
  */
 class Edge implements Comparable<Edge> {
     private int from; //uzel z
     private int to; //uzel do
     private int weight; //vaha
     public Edge(int from, int to, int weight) {
         this.from = from;
         this.to = to;
         this.weight = weight;
     }
     /**
      * Provede porovnani hran dle vahy (vyssi vaha == vetsi)
      * @param o
      * @return
      */
     public int compareTo(Edge o) {
         if (this.getWeight() > o.getWeight()) {
             return 1;
         } else if (this.getWeight() < o.getWeight()) {
             return -1;
         } else {
             return 0;
         }
     }
 
     /**
      * @return the from
      */
     public int getFrom() {
         return from;
     }
 
     /**
      * @param from the from to set
      */
     public void setFrom(int from) {
         this.from = from;
     }
 
     /**
      * @return the to
      */
     public int getTo() {
         return to;
     }
 
     /**
      * @param to the to to set
      */
     public void setTo(int to) {
         this.to = to;
     }
 
     /**
      * @return the weight
      */
     public int getWeight() {
         return weight;
     }
 
     /**
      * @param weight the weight to set
      */
     public void setWeight(int weight) {
         this.weight = weight;
     }
 }
 /**
  * Jednoducha implementace Union-Find problemu
  * @author Pavel Micka
  */
 class DisjointSet {
 
     private Node[] nodes;
 
     public DisjointSet(int nodeCount) {
         nodes = new Node[nodeCount];
         for (int i = 0; i < nodeCount; i++) {
             nodes[i] = new Node();
             nodes[i].id = i;
         }
     }
 
     /**
      * Provede sjednoceni komponent, ve kterych jsou uzly "a" a "b"
      * Union provadi vzdy do A
      * @param a cislo uzlu a
      * @param b cislo uzlu b
      * @return cislo reprezentanta sjednocene komponenty
      */
     public int union(int a, int b) {
         Node repA = nodes[find(a)];
         Node repB = nodes[find(b)];
 
         repB.parent = repA;
         return repA.id;
     }
 
     /**
      * Vrati reprezentanta zadaneho uzlu
      * @param a cislo uzlu, jehoz reprezentanta hledame
      * @return cislo reprezentanta uzlu
      */
     public int find(int a) {
         Node n = nodes[a];
         int jumps = 0;
         while (n.parent != null) {
             n = n.parent;
             jumps++;
         }
         if (jumps > 1) repair(a, n.id);
         return n.id;
     }
 
     /**
      * Provede opravu (compression) cesty
      * @param a
      * @param rootId
      */
     private void repair(int a, int rootId) {
         Node curr = nodes[a];
         while (curr.id != rootId) {
             Node tmp = curr.parent;
             curr.parent = nodes[rootId];
             curr = tmp;
         }
     }
 
     @Override
     public String toString() {
         StringBuilder builder = new StringBuilder();
         for (int i = 0; i < nodes.length; i++) {
             builder.append(find(i) + " ");
         }
         return builder.toString();
     }
 
     /**
      * Uzel n-arniho stromu
      */
     private static class Node {
         /**
          * Rodic
          */
         Node parent;
         /**
          * Identifikator uzlu
          */
         int id;
     }
 }

Literatura

KOLÁŘ, Josef. Teoretická informatika. 2. vyd. Praha : Česká informatická společnost, 2004. 205 s. ISBN 80-900853-8-5.

Princip

Asymptotická složitost algoritmu

Kód

Literatura

Doporučujeme