1
$\begingroup$

I am trying to define the time complexity of Kruskal's algorithm as function dependant on:

  • the number of vertices V
  • the number of edges E
  • the time complexity of verifying, whether two edges don't form a cycle Ec(V)
  • the time complexity of connecting two sets of vertices Vc(V)

The edges are unsorted and I know the time complexity of sorting edges, which is Big O(E * log E).

I don't really know, how to solve this problem and I would be grateful for any help. Thanks!

$\endgroup$
  • $\begingroup$ Welcome to cs.SE! Where did you get stuck on? What did you try? $\endgroup$ – BearAqua May 11 at 19:19
  • $\begingroup$ Also, assuming you use a good union-find algorithm, the time of sorting the edges will dominate. Therefore, $O(E\log E)$ is indeed a correct bound for the entire algorithm. $\endgroup$ – BearAqua May 11 at 19:21
1
$\begingroup$

After sorting the edges, which takes $O(E \log E)$ time, Kruskal's algorithm adds the next cheapest edge which doesn't cause a cycle. The question is what data structure can be used to check if a given edge causes a cycle.

At any given point during the execution of the algorithm, the set of edges chosen by the algorithm forms a forest. Initially, the forest contains $n$ trees, where $n:=|V|$. If the next cheapest edge is $ab$, and vertices $a$ and $b$ belong to different trees in the forest, then the two trees can be combined into a larger tree.

A data structure for storing the above tree information is to store a parent value for each vertex. Following the parent pointer leads to the root node of the tree. If vertices $a$ and $b$ have different roots, then they belong to different trees. One can merge the two trees by making $b$ the parent of $a$. This allows us to maintain a collection of disjoint sets (each set is the vertex set of a tree), whose union is the vertex set of the graph.

So that the merging of two trees into one tree is done efficiently, the smaller tree can be put under the larger tree (i.e. the one with the smaller rank has its root node point to the other root). This ensures that the trees have small heights, and the path that is followed from a node to find its root has small length. Also, in order to not have to follow the same long sequence of parent pointers in subsequent iterations, one can store the root node's value after it is found. These are the "union-by-rank" and "path compression" heuristics, which efficiently implement Kruskal's algorithm, so that it runs in $O(E \log E) = O(E \log V)$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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