/************************* Kruskal.java  **************************************/

/** bestimmt einen minimalen Spannbaum nach der Idee von Kruskal              */
/*  verwendet wird eine PriorityQueue zum Verwalten der gewichteten Kanten    */
/*                                                                            */
/*  Um die Suche nach dem Repraesentanten einer Zusammenhangskomponente zu    */
/*  beschleunigen, wird die Technik des Path-halving eingesetzt: auf dem Weg  */
/*  zum Repraesentanten wird jeder Vater durch den Grossvater ersetzt         */

import java.util.*;

public class Kruskal {

  private static UndiVertex findAndUpdateChef(UndiVertex v) { 
    while (v.chef != v) {          // solange der Knoten kein Repraesentant ist
      v.chef = v.chef.chef;        // ersetze Vater durch Grossvater
      v      = v.chef;             // steige zum Grossvater hoch
    }
    return v;                      // liefere den ermittelten Repraesentanten
  }

  public static void kruskal(UndiGraph g) {

    PriorityQueue<UndiEdge> p =            // Priority-Queue zum Verwalten
        new PriorityQueue<UndiEdge>();     // aller Kanten gemaess Gewicht

    p.addAll(g.edges());                   // alle Kanten in die Priority-Queue

    for (UndiVertex v : g.vertices()){     // jeder Knoten
      v.chef = v;                          // ist sein eigender Chef 
    }

    int count = 0;                         // bisher noch keine Kanten gefunden 

    UndiVertex x,y;                        // 2 Knoten
    while (count < g.size()-1) {           // solange noch nicht genug Kanten 
      UndiEdge e   = p.poll();             // besorge die billigste Kante 
      x = findAndUpdateChef(e.left);       // bestimme Repraesentanten links
      y = findAndUpdateChef(e.right);      // bestimme Repraesentanten  rechts
      if (x != y) {                        // falls in verschieden Komponenten
        x.chef = y;                        // vereinige Komponenten
        e.status = true;                   // notiere Kante e
        count++; 
      }
    }
  }
}