{ Algorithmus nach Prim }
program prim_algo;

const MAXNODES = 100;

type node = integer;            { Knoten }
type cost = integer;            { Kosten }

type edge = record              { Adjazenzliste mit Kosten der Kanten }
    v       : node;
    k       : cost;
    next    : ^edge;
end;

type adj   = array[1..MAXNODES] of ^edge;   { Adjazenzlisten }
type heap  = array[1..MAXNODES] of node;    { Heap }
type index = array[1..MAXNODES] of integer; { Index der Knoten im Heap }
type keys  = array[1..MAXNODES] of cost;    { Schlüsselwerte }

{ Graph aus Datei einlesen.
  Format: <Knoten1> <Knoten2> <Kosten> }
procedure read_graph(filename:string; var a:adj);
    var graph   : text;
    var u, v    : node;
    var k       : cost;
    var tmp     : ^edge;
begin
    reset(graph, filename);                 { Eingabe öffnen }

    while not EOF(graph) do begin
        readln(graph, u, v, k);
        if a[u] = nil then begin            { Kante (u,v) und }
            new(tmp);
            tmp^.v := v;
            tmp^.k := k;
            tmp^.next := nil;
            a[u] := tmp;
        end else begin
            tmp := a[u];
            while tmp^.next <> nil do
                tmp := tmp^.next;
            new(tmp^.next);
            tmp := tmp^.next;
            tmp^.v := v;
            tmp^.k := k;
            tmp^.next := nil;
        end;
        if a[v] = nil then begin            { Kante (v,u) einfügen }
            new(tmp);
            tmp^.v := u;
            tmp^.k := k;
            tmp^.next := nil;
            a[v] := tmp;
        end else begin
            tmp := a[v];
            while tmp^.next <> nil do
                tmp := tmp^.next;
            new(tmp^.next);
            tmp := tmp^.next;
            tmp^.v := u;
            tmp^.k := k;
            tmp^.next := nil;
        end;
    end;
    close(graph);
end;

{ Minimum aus dem Heap entfernen und zurückgeben.
  Heapeigenschaft wiederherstellen. }
function delete_min(var q:heap; var idx:index; key:keys;
                    var heap_size:integer) : node;
    var parent, left, right : integer;
    var change              : boolean;
    var tmp                 : node;
begin
    delete_min := q[1];     { Kleinstes Emelent an erster Stelle }
    idx[q[1]] := 0;         { Index anpassen }

    { Letztes Element nach oben. }
    q[1] := q[heap_size];
    idx[q[1]] := 1;
    q[heap_size] := 0;
    heap_size := heap_size-1;

    { Einsickern lassen. }
    parent := 1;
    left := 2*parent;
    right := 2*parent+1;
    change := true;

    { Solange die Heapeigenschaft verletzt ist. }
    while change do
    begin
        change := false;
        { Heapeigenschaft verletzt. }
        if ((left <= heap_size) and (key[q[parent]] > key[q[left]])) or
           ((right <= heap_size) and (key[q[parent]] > key[q[right]])) then
        begin
            change := true;
            if (right > heap_size) or (key[q[left]] < key[q[right]]) then
            begin
                { Kein rechtes Kind oder linkes Kind kleiner als rechtes.
                  Vertausche linkes Kind mit Vater. }
                idx[q[parent]] := left;
                idx[q[left]] := parent;
                tmp := q[parent];
                q[parent] := q[left];
                q[left] := tmp;

                { Linkes Kind ist neuer Vater. }
                parent := left;
            end else begin
                { Vertausche rechtes Kind mit Vater. Ist kleiner, da
                  Heapeigenschaft verletzt. }
                idx[q[parent]] := right;
                idx[q[right]] := parent;
                tmp := q[parent];
                q[parent] := q[right];
                q[right] := tmp;

                { Rechtes Kind ist neuer Vater. }
                parent := right;
            end;
        end;

        { Neue Kinder berechnen. }
        left := 2*parent;
        right := 2*parent+1;
    end;
end;

{ Knoten im Heap aufsteigen lassen nachdem der Keywert
  verringert wurde. }
procedure decrease_key(var q:heap; var idx:index; key:keys;
                        heap_size:integer; v:node);
    var parent, child   : integer;
    var tmp             : node;
begin
    parent := idx[v] div 2;
    child := idx[v];
    while (parent > 0) and (key[q[parent]] > key[q[child]]) do
    begin
        idx[q[parent]] := child;
        idx[q[child]] := parent;
        tmp := q[parent];
        q[parent] := q[child];
        q[child] := tmp;

        child := parent;
        parent := parent div 2;
    end;
end;

{ Minimalen Spannbaum bestimmen. }
procedure prim();
    var graph   : adj;                          { Graph }
    var q       : heap;                         { Heap mit Knoten }
    var key     : keys;                         { Schlüsselwerte }
    var kante   : array[1..MAXNODES] of node;   { kleinste Kante }
    var idx     : index;                        { Index der Knoten im Heap }
    var r       : node;                         { Startknoten }

    var i           : integer;
    var heap_size   : integer;
    var tmp         : ^edge;
    var u, w        : node;
    var k           : cost;
begin
    for i := 1 to MAXNODES do       { Initialisierung }
    begin
        graph[i] := nil;
        q[i] := 0;
        key[i] := MAXINT;
        kante[i] := 0;
        idx[i] := 0;
    end;

    read_graph('graph.txt', graph); { Graph einlesen. }

    { Alle Knoten in Heap einfügen. }
    heap_size := 0;
    for i := 1 to MAXNODES do
    begin
        { Neuer Knoten gefunden. }
        if (graph[i] <> nil) and (idx[i] = 0) then
        begin
            heap_size := heap_size+1;
            q[heap_size] := i;
            idx[i] := heap_size;
        end;
    end;

    { Startknoten behandeln, oBdA erster gefundener Knoten }
    r := delete_min(q, idx, key, heap_size);
    tmp := graph[r];

    { Alle Nachbarn des Startknotens behandeln. }
    while tmp <> nil do
    begin
        key[tmp^.v] := tmp^.k;
        kante[tmp^.v] := r;
        decrease_key(q, idx, key, heap_size, tmp^.v);
        tmp := tmp^.next;
    end;

    { Hauptschleife }
    while heap_size > 0 do
    begin
        { Knoten mit kleinster abgehender Kante. }
        w := delete_min(q, idx, key, heap_size);

        { Kante ausgeben. }
        writeln(kante[w], ' -- ', w, '(', key[w], ')');

        tmp := graph[w];
        { Alle Nachbarn des gefundenen Knotens testen, ob neue
          billigste Kante vorhanden. }
        while tmp <> nil do
        begin
            u := tmp^.v;
            k := tmp^.k;

            { Knoten noch im Heap und billigere Kante gefunden. }
            if (idx[u] <> 0) and (k < key[u]) then
            begin
                key[u] := k;
                kante[u] := w;
                decrease_key(q, idx, key, heap_size, u);
            end;

            tmp := tmp^.next;
        end;
    end;
end;

begin

    prim();

end.