Minimaler Spannbaum

Aufgabenstellung:

Gegeben ein ungerichteter Graph aus Kanten E und Knoten V und Kosten für jede Kante. Finde die billigste Menge an Kanten, so dass alle Knoten verbunden sind.

Prim's Algorithmus

Betrachte alle Knoten ohne Kanten. Beginne mit beliebigem Knoten.

Füge immer den Knoten+Kante zum Spannbaum hinzu, der über die billigste Kante mit einem Knoten aus dem Spannbaum verbunden ist.

Kruskal Algorithmus

Alternative a.) Verwende immer die billigste Kante um zwei Knoten zu verbinden, es sei denn es entsteht ein Zykel.

Alternative b.) Betrachte den Graph als Menge von unverbundenen Bäumen. Verbinde immer mittels der billigsten Kante zwei unverbundene Bäume.

Implementierung

Achtung: Nicht schnell genug für alle Anforderungen.

public class Prim {

    class E implements Comparable {
      int v1, v2, cost;

      public E(int from, int to, int cost) {
         v1 = from;
         v2 = to;
         this.cost = cost;
      }

      public int compareTo(E e) {
         return cost - e.cost;
      }
   }

   public void doit() throws Exception {
      BufferedReader br = new BufferedReader(new FileReader("data/jungle.in"));
      PrintStream ps = new PrintStream(new FileOutputStream("flow.out"));

      while (true) {
         int n = Integer.parseInt(br.readLine());
         if (n == 0)
            break;

         boolean[] vs = new boolean[n];
         vs[0] = true;

         ArrayList es = new ArrayList();

         for (int i = 0; i < n - 1; i++) {
            String[] s = br.readLine().split(" ");
            for (int j = 2; j < s.length; j++) {
               int to = s[j++].charAt(0) - 'A';
               int cost = Integer.parseInt(s[j]);
               es.add(new E(i, to, cost));
            }
         }

         Collections.sort(es);

         int cost = 0;
         next: for (int i = 1; i < n; i++) {
            for (E e : es) {
               if (vs[e.v1] ^ vs[e.v2]) {
                  cost += e.cost;
                  vs[e.v2] = true;
                  vs[e.v1] = true;
                  es.remove(e);
                  continue next;
               }
            }
         }

         ps.println(cost);
      }
      ps.close();
   }

   public static void main(String[] args) throws Exception {
      (new Prim()).doit();
   }
}

Comments