Kruskal's Algorithm

Pseudo code

MST-KRUSKAL(G, w)
  A = ∅ 
  for each vertex v ∈ G.V
    MAKE-SET(v)
  create a single list of the edges in G.E
  sort the list of edges into monotonically increasing order by weight w
  for each edge (u, v) taken from the sorted list in order
    if FIND-SET(u) != FIND-SET(v)
      A = A ∪ {u, v}
      UNION(u, v)
  return A

Time complexity

$O(ElgE)$。

在$MST-KRUSKAL$中，MAKE-SET(v)的time complexity為$O(V)$，create $E$的list為$O(E)$，因此兩者的time complexity為$O(V+E)$，因為graph $G$ connected，所以 $E > V$，所以time compleixty為$O(E)$。

接著根據weight來sort E，這一步驟的time complexity為$O(ElgE)$。

最後的for-loop執行了$(V+E)$遍，如果我們這邊的實作用disjoint forest來實作，time complexity為$O(V+E\alpha(V))$，而$\alpha(V)$成長緩慢，可以視為為常數，所以time complexity為$O(V+E)$ => $O(E)$。

因此可以知道整個演算法的bound在$O(ElogE)$，而因為是undiredcted graph，所以$|E| < |V|^2$ => $O(lg|E|) = O(lg|V|)$，將此結果帶入$O(ElogE)$得到$O(ElgV)$。

Golang Implementation

kruskal.go

import (
  "sort"
)
type DisjointSet struct {
    Parent *DisjointSet
    Rank int
    Vertex int
  }

func (set *DisjointSet) Find() *DisjointSet {
  if set.Parent == set {
    return set
  }

  // path compression
  set.Parent = set.Parent.Find()

  return set.Parent
}

func (set *DisjointSet) Union(another *DisjointSet) {
  setRepresentative := set.Find()
  anotherSetRepresentative := another.Find()

  if setRepresntaetive.Rank <= anotherSetRepresentative.Rank {
    setRepresentative.Parent = anotherSetRepresentative

    // if the ranks tie, then anotherSetRrepresentative grows by 1 after merge
    if setRepresntaetive.Rank == anotherSetRepresentative.Rank {
      anotherSetRepresentative.Rank++
    }
  } else {
    anotherSetRepresentative.Parent = setRepresentative
  }
}

type ByWeight [][]int

func (w ByWeight) Len() int           { return len(a) }
func (w ByWeight) Swap(i, j int)      { w[i], w[j] = w[j], w[i] }
func (w ByWeight) Less(i, j int) bool { return w[i][2] < w[j][2] }

func kruskal(graph [][]int) [][]int {
  // Assume graph is an adjacent list. Each edge in the list contains 
  // connected vertex number and weight.

  // make sets & collect edges
  vertices := make([]*DisjointSet, len(graph))
  edges := [][]int{}
  for v, edge := range graph {
    vertices[v] = &Disjoint{
      Rank: 1,
      Vertex: v,
    }

    vertices[v].Parent = vertices[v]
    edges = append(edges, []int{v, edge[0], edge[1]})
  }

  // sort edges
  sort.Sort(ByWeight(edges))

  mst := [][]int{}
  for _, edge := range edges {
    u := edge[0]
    v := edge[1]

    uSet := vertices[u]
    vSet := vertices[v]

    if uSet.Find() != vSet.Find() {
      uSet.Union(vSet)
      mst = append(mst, edge)
    }
  }

  return mst
}