Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.
share|improve this question
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?) –  Pete L. Clark Jun 14 '11 at 23:47
    
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. –  Gerry Myerson Jun 15 '11 at 0:27
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. –  ShreevatsaR Jun 15 '11 at 6:12
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. –  user11775 Jun 15 '11 at 7:35
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. –  Chris Taylor Jun 15 '11 at 8:40

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.