Rešitev: Kruskalov algoritem (Mathematica)

Iz MaFiRaWiki

Naloga: Kruskalov algoritem


(* Podprogrami za delo s seznamom povezav - podatkovna struktura Edges *)

InitEdges[] := {} (* Inicializacija seznama *)
SortEdges[l_List] := l[[Ordering[l[[All, {3}]]]]] (* Sortiranje seznama *)
EdgeVertex1[e_List] := e[[1]] (* Prvo vozlišče povezave e *)
EdgeVertex2[e_List] := e[[2]] (* Drugo vozlišče povezave e *)

(* Podprogrami za delo s seznamom podmnožic vozlišč - pod. str. UnionFind *)

InitUF[l_List] := Map[{#} &, Union[Flatten[Map[{#[[1]], #[[2]]} &, l]], {}] (* Inicializacija UnionFind - a *)
FindUF[l_List, x_] := For[i = 1, i ≤ Length[l], i++, If[MemberQ[l[[i]], x], 
Return[i],];] (* Iskanje podmnožice vozlišč v seznamu podmnožic l, ki vsebuje vozlišče x *)
UnionUF[l_List, i1_, i2_] := Delete[Append[l, Union[l[[i1]],l[[i2]]]], {{i1}, {i2}}] 
(* Unija dveh podmnožic z indeksoma i1 in i2 v seznamu l; Iz seznama l se izbrišeta podmnožici, ki smo ju združili v novo množico *)

(* Kruskalov algoritem *)
Kruskal[l_List] :=
  Module[{g, cv, t, n, e, i1, i2},
    cv = InitUF[l]; (* Inicializacija podmnozic vozlišč; Na začetku vsako vozlišče predstavlja svoje drevo *)
    g = SortEdges[l]; (* uredi seznam povezav glede na uteži*)
    t = InitEdges[];(* začnemo s praznim minimalnim vpetim drevesom; V zanki potem dodajamo ustrezne povezave *)
    n = Length[cv];
    While[Length[t] < n - 1,(* vpeto drevo ima eno povezavo manj kot je vozlišč *)
      e = First[g];
      g = Rest[g];
      i1 = FindUF[cv, EdgeVertex1[e]];
      i2 = FindUF[cv, EdgeVertex2[e]];
      If[cv[[i1]] ≠ cv[[i2]], t = Append[t, e];
        cv = UnionUF[cv, i1, i2];,]];
    Return[t]]

Primera

g = {{"a", "b", 7}, {"a", "d", 5}, {"b", "c", 8}, {"b", "d", 9}, {"b","e", 7}, {"c", "e", 5}, {"d", "e", 15}, {"d", "f", 6},
{"e", "f", 8}, {"e", "g", 9}, {"f", "g", 11}}
Kruskal[g]

vrne

{{a, d, 5}, {c, e, 5}, {d, f, 6}, {a, b, 7}, {b, e, 7}, {e, g, 9}},
h = {{"a", "b", 5}, {"a", "f", 3}, {"a", "g", 11}, {"b", "c", 7}, {"b", "d", 10}, {"c", "d", 8}, {"c", "g", 8}, {"d", "e", 2}, 
{"e","f", 5}, {"e", "g", 7}, {"f", "g", 9}};
Kruskal[h]

pa vrne

{{d, e, 2}, {a, f, 3}, {a, b, 5}, {e, f, 5}, {b, c, 7}, {e, g, 7}}.
Osebna orodja