Kruskal’s Algorithm

Kruskal’s Algorithm is an #202204151143 which used to solve the #202204272006. It uses Disjoint Set as its basic data structure and utilises the Union or Find algorithm.

The basic idea is to select the edges in order of the smallest weight and only accept the edge if it does not result in a cycle. To check this, we need to know whether the two vertices are in the same set. If they are, we reject them, otherwise we will add them into the spanning tree. Do this until all the edges are examined.

Analysis

• It is advised to build a 202202062259 for it. To further optimise it, use an array of pointers instead of edges.
• The worst-case running time is \(O(\vert E \vert log \vert V \vert)\)

Implementation

void Kruskal(Graph G)
{
  int EdgesAccepted;
  DisjSet S;
  PriorityQuue H;
  Vertex U, V;
  SetType Uset, Vset;
  Edge E;

  Initialize(S);
  ReadGraphIntoHeapArray(G, H);
  BuildHeap(H);

  EdgesAccepted = 0;
  while (EdgesAccepted < NumVertex - 1) {
    E = DeleteMin(H); // E = (U,V)
    Uset = Find(U, S);
    Vset = Find(V, S);
    if (Uset != Vset) {
      // Accept the edge
      EdgesAccepted++;
      SetUnion(S, USet, VSet);
    }
  }
}