Talk:Kruskal's algorithm

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class Low Priority  Field: Discrete mathematics

Many problems with this proof. Confusion between vertices and edges, etc., etc.. --zero 05:56, 13 Oct 2003 (UTC)

There was actually also a problem with the running time. Kruskal's can run in O(|E| log |V|) where E is the set of edges and V the set of vertices. It should be obvious that |E| >= |V| in any graph that connects all vertices (though not necessarily fully connected).

Hell, using a better UNION-FIND paradigm, Kruskal's algorithm will run in expected time O( | E | α( | E | )), where α is the inverse Ackermann function. (If memory serves right. It's certainly better than O( | E | log | V | )). Grendelkhan 08:46, 2004 Apr 20 (UTC)

Contents

[edit] Merge the min spanning tree algorithms into one article

The three pages Kruskal's algorithm, Boruvka's algorithm and Prim's algorithm should be merged into one article (possibly named minimum weight spanning tree algorithm), because they are all very similar greedy algorithms (the underlying concept is the same, they only differ, if at all, in use of data structures), which were discovered independently. Also, there are some other confusions. Jarnik, mentioned in Prim's algorithm, cooperated on this problem with Boruvka, so they should be mentioned on the same page. Also, originally, their definiton of "graph" (for this problem) was a set of points in Euclidean space, and the weights were distances among points and the tree was called skeleton (the lightest possible construction needed to rigidly connect the points - so, due to this tradition, in Czech, the problem is called "problem of minimum skeleton"). So, if anyone doesn't object to this, I'll try to merge them. Samohyl Jan 17:29, 11 Jan 2005 (UTC)

I don't think they need to be merged. Each is already mentioned in the Minimum spanning tree article and they seem different enough to have their own articles. Cockroachbill
It may be worthwhile merging Kruskal's with Prim's, as these are pretty similar, but Boruvka's is (I think) different. After all, textbooks often treat them simultaneously. Even for those two, I could go either way. The "minimum skeleton" you refer to is now called the Euclidean minimum spanning tree, which has its own article, and in fact has considerably more efficient specialized algorithms than any of these three. Consider adding a redirect. Deco 18:33, 1 December 2005 (UTC)
I, too, see no reason for merging. grendel|khan 19:15, 1 December 2005 (UTC)

[edit] caption on figure

The caption should not describe the figure as a complete network - in a complete network, all edges are present. —The preceding unsigned comment was added by 69.159.78.115 (talk • contribs) 21:15, 4 February 2006 (UTC)

I've gone ahead and fixed it up. It said "complete network", which might be someone's jargon for "a graph in which all vertices form a single well-connected component". A quick Google search suggested it is not. In the future, be bold and fix things as you see them! --Mgreenbe 19:31, 4 February 2006 (UTC)

[edit] Minimum Spanning Forest

Minimum Sppaning Forest is a subset of edges that "cover" all vertexs, not a set of minimum spanning trees of each connected component —The preceding unsigned comment was added by 201.129.158.57 (talk • contribs) 23:13, 12 February 2006 (UTC)

You are fundamentally correct, but watch: minimal such subsets of edges in a connected graph induce trees. In a disconnected graph, each component treated individually is spanned by a tree; the union of these is a forest. Thus a minimal spanning forest is a forest of minimal spanning trees. --Mgreenbe 21:47, 12 February 2006 (UTC)

[edit] Pseudocode?

If anyone has sufficient skill, it would be nice to have pseudocode for Kruskal's algorithm. 67.171.14.239 11:06, 4 June 2006 (UTC)

I added the psuedocode from my textbook, I edited it a bit to try and make it look more like the psuedocode on Dijkstra's algorithm but it is still more "psuedo" than most of what I see on wiki; feel free to change it.Tokataro 19:07, 9 November 2006 (UTC)

[edit] What is the difference between Kruskal's and Borůvka's algorithms?

What is the difference between Kruskal's and Borůvka's algorithms? Some study material I have describes some algorithm which is labeled as Borůvka/Kruskal. And I see no difference between the two. Can someone point to the difference?--Alvin-cs ✉ 13:20, 8 September 2007 (UTC)

[edit] Proof of correctness

May be I'm just stupid, but I found the proof un-clear. --Weedrat (talk) 14:21, 10 March 2008 (UTC)

You're not - we'd appreciate specific feedback on what parts confused you. Dcoetzee 20:03, 10 March 2008 (UTC)
I also found the argument (edit: that is, the argument before Mikkalai fixed it) confusing. I think I've managed to recast the argument in a way which makes its key ideas more explicit. Specifically,
  1. subforests of a graph form a matroid (the graphic matroid), so we have the exchange property, and
  2. by appropriately changing the edge order, one can produce any desired spanning tree (although the spanning tree is only minimal if edges with smaller weights appear before edges with larger weights).
This suggests that we can move one step at a time from a spanning tree produced by the algorithm to a given minimum spanning tree while maintaining the weight at each step. Here is my attempted revision:
Let T be the spanning tree produced by the algorithm for a given edge order, and let M be a minimum spanning tree. Assume that T contains k > 0 edges which do not occur in M, and let e be the smallest such edge. By the exchange property, there is an edge f which occurs in M but not in T such that T \ e ∪ f is a spanning tree. Since M is a minimum spanning tree, the weight of f is less than or equal to the weight of e. Let F be the forest constructed by the algorithm just prior to encountering the edge e. If f has already been encountered and rejected, then F ∪ f contains a cycle, contradicting the claim that T \ e ∪ f is a tree. Hence e is encountered before f, implying that the weight of e is less than or equal to the weight of f. Consequently, the spanning treeT \ e ∪ f has the same weight as T, but contains only k − 1 edges which do not occur in M. The algorithm can be coaxed to produce the spanning tree T \ e ∪ f by swapping the positions of e and f in the edge order. Repeatedly applying this procedure eventually produces M. Hence T and M have the same weight. Michael Slone (talk) 06:04, 11 March 2008 (UTC)