Talk:Kruskal's algorithm
From Wikipedia, the free encyclopedia
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)
[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)
