2
$\begingroup$

Can someone explain why Kruskal's algorithm and Prim's algorithm are each a special case of the general algorithm for minimum spanning trees?

The general algorithm:

  • Let A be the set of selected edges.
  • Initially, A = Empty.
  • Select a cut C respecting A.
  • Select a light edge e=(u,v) crossing C and add it to A.
  • Repeat until there is no cut respecting A.
  • 1
    +1 for the (newly edited) question and for ShreevatsaR. When an ambiguity in a question can be cleared up by a $G$oogle search, our first instinct should always be to edit the question rather than jumping straight in with a downvote - particularly when it's a new user.2011-06-15

1 Answers 1

1

Let $G=(V,E,w)$ be a weigthed graph ($w : E \rightarrow \mathbb{R}$ is the weight function).

In Prim's algorithm, we start from an arbitrary vertex and "grow a tree". In each iteration we add a new vertex to the tree. The cut in each iteration is defined by partitioning $V$ into: (Part 1) The vertices in the tree grown so far and (Part 2) All other vertices. The edge chosen is the lightest one crossing that cut.

In Kruskal's algorithm, we start with $|V|$ trees, each made of a single vertex. In each iteration we merge two trees. In each iteration, there is more than one natural way to interpret what the cut is. Consider an iteration of the algorithm. We have a forest of trees $T_1,\dotsc,T_k$ constructed so far, and the algorithm chooses, of all edges connecting two different trees, the lightest one, $(u,v)$. If $(u,v)$ connects trees $T_i$ and $T_j$, then any partition of $V$ in which $T_i$ is contained in one part, $T_j$ is contained in the other part, and any other tree among $T_1,\dotsc,T_k$ is entirely contained in one part or the other, defines a cut respected by the edges chosen so far, and $(u,v)$ is the lightest edge crossing it.