Talk:Kruskal's algorithm

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|\alpha (|E|))$, where $\alpha$ 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)