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.
  • 3
    Could you please provide some more context? Does "Kruskal and Prim" refer to a paper or a result? Which one? The general algorithm *for what*? (Something about **spanning trees**, perhaps?)2011-06-14
  • 0
    I'll hazard a guess that OP is asking about finding minimal weight spanning trees in a weighted graph; there are two well-known algorithms, one of Kruskal, one of Prim; they have enough in common to suggest that there is a "general algorithm" of which both can be seen as special cases. A perfectly reasonable question, though perhaps OP could have supplied some of this information instead of assuming everyone knows it.2011-06-15
  • 0
    There is a general "cut property" that allows one to make such a recurrence statement: given a subgraph contained in a minimal spanning tree that cuts the graph into two pieces, then the minimum edge between these two pieces can always be added to this subgraph; one will get something still contained in a MST. See http://amathew.wordpress.com/2011/02/12/spanning-trees-the-cut-property-and-kruskals-algorithm/2011-06-15
  • 2
    Some of the people asking questions here may not be native speakers of English, and may not be internet savvy. Or they may just be poor communicators. I think that when it's obvious what the question is, we should just edit the question to make it clearer instead of so many downvotes.2011-06-15
  • 0
    @Shreevatsa, thanks, you've done a good job of editing, a job that I should have done. I would like user11775 to come back to tell us what it means for a cut to "respect" a set of edges. I can see how Prim's algorithm is a special case of the general algorithm, but I can't see how to select the cut so Kruskal's algorithm fits, even with Akhil Mathew's comment. I'm probably missing something simple....2011-06-15
  • 2
    A cut respects a set of edges A when the cut doesn't crosses the edges in A. Thanks for the comments, I'm not good at english so often I try to keep the text very simple.2011-06-15
  • 1
    +1 for the (newly edited) question and for ShreevatsaR. When an ambiguity in a question can be cleared up by a Google 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.