What Determines the Running Time of Kruskal's Algorithm?

[evinda]

Hello! (Wave)

The Kruskal's algorithm is the following:

MST-KRUSKAL(G,w)
1. A={}
2. for each vertex v∈ G.V
3.      MAKE-SET(v)
4. sort the edges of G.E into nondecreasing order by weight w
5. for each edge (u,v) ∈ G.E, taken in nondecreasing order by weight w
6.      if FIND-SET(u)!=FIND-SET(v)   
7.         A=A U {(u,v)}  
8.         Union(u,v)
9. return A

According to my textbook:Initializing the set [m]A[/m] in line 1 takes $O(1)$ time, and the time to sort the edges in line 4 is $O(E \lg E)$. The for loop of lines 5-8 performs $O(E)$ FIND-SET and UNION operations on the disjoint-set forest. Along with the $|V|$ MAKE-SET operations, these take a total of $O((V+E)\alpha(V))$ time, where $\alpha$ is a very slowly growing function. Because we assume that $G$ is connected, we have $|E| \geq |V|-1$, and so the disjoint-set operations take $O(E \alpha(V))$ time. Moreover, since $\alpha(V)=O(\lg V)=O(\lg E)$, the total running time of Kruskal's algorithm is $O(E \lg E)$. Observing that $|E|<|V|^2$, we have $\lg |E|=O(\lg V)$, and so we can restate the running time of Kruskal's algorithm as $O(E \lg V)$.Could you expain me why we deduce that the time to sort the edges in line 4 is $O(E \lg E)$?
Also how do we get that the total time complexity is $O((V+E)\alpha(V))$ ?
In addition, suppose that all edge weights in a graph are integers from $1$ to $|V|$. How fast can you make Kruskal's algorithm run? What if the edges weights are integers in the range from $1$ to $W$ for some constant $W$?How does the time complexity depend on the weight of the edges?

 

[Future Bruno]

For the first question, the time to sort the edges in line 4 is $O(E \lg E)$ because the sorting algorithm is using a comparison sort, which has a time complexity of $O(n \log n)$. For the second question, the total time complexity is $O((V+E)\alpha(V))$ because the disjoint-set operations take $O(E \alpha(V))$ time, and the MAKE-SET operations take $O(V)$ time.For the third question, if all edge weights are integers from 1 to |V|, then Kruskal's algorithm can be implemented to run in linear time, $O(E + V)$, using counting sort. If the edge weights are integers in the range from 1 to W for some constant W, then Kruskal's algorithm can still be implemented to run in linear time, $O(E + V)$, using bucket sort.