Pseudokod

Lekcja 4 z 9 w kursie Algorytm Kruskala — algorytmy grafowe w Coddy.

kruskal(n, edges):
   parent[i] = i for all i          # each vertex its own set
   total = 0
   repeat until all edges considered:
      pick the unused edge (u, v, w) with the smallest w
      ru = find(u); rv = find(v)
      if ru != rv:                   # no cycle
         parent[ru] = rv             # union
         total += w
   return total

find(x):
   while parent[x] != x: x = parent[x]
   return x

Wybieranie najmniejszej nieużytej krawędzi w każdej rundzie (wybór minimum) pozwala uniknąć osobnego sortowania.
find przechodzi w górę do korzenia; union to pojedyncze przypisanie jednego korzenia do drugiego.

Spróbuj swoich sił

Ta lekcja nie zawiera wyzwania z kodem.