Redirected
retagged by
17,313 views
37 votes
37 votes
Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing $n$ vertices and $m$ edges if the edges are sorted is _______
retagged by

10 Answers

Best answer
38 votes
38 votes

If all edges are already sorted then this problem will reduced to union-find problem on a graph with $E$ edges and $V$ vertices.

for each edge (u,v) in E

    if(FIND-SET(u) != FIND-SET(v))
        UNION(u,v)

FIND-SET$(v)$ and UNION$(u,v)$ runs in $α(|V|)$

where $α(n)$ is inverse ackermann function i.e $\log^*(n)$

So, overall complexity becomes $O(|E|.α(|V|))$

edited by
10 votes
10 votes

Time complexity for the whole 'Krushkal minimum spanning tree' algorithm, i.e, when the edges need to be sorted is O(ElogV). According to the question the edges have already been sorted, so O(ElogV) is irrelevant here. Only need to consider union find operation on the E edges and each union find operation takes a constant amount of time, video posted below explains this. Thus O(1)E (E times O(1)), = O(E). The time complexity of the accepted answer is the case when 'path compression' and 'union by rank' methods have not been implemented. For amortized union find operation which implements 'path compression' and 'union by rank' methods, the time complexity is O(1) [Check geeksforgeeks link below]. Thus time complexity for this question should be O(E)

https://www.youtube.com/watch?v=fAuF0EuZVCk

https://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/

3 votes
3 votes
First of all we need to make set of each vertices. so, that when we ask FIND-SET(v) then it should output v initially.

for each vertex V in graph G

MAKE-SET(V) // make set with only vertex V in it.

// edges are already sorted so, now we have to just add edges in order given if they don't form cycle.

for each edge (u,v) that belong to G

{

if FIND-SET(v) != FIND-SET(u)

T = T U {u,v} // T here is tree that needs to be constructed.

UNION( u,v) // that is unify two sets whose representative are u and v.

}

so , time complexity = |V| time for making subset for each vertex  + |E| time checking whether cycle exists or not. as FIND-SET and UNION runs in O(1) time

=O( |V| + |E|)

=O(m+n)
0 votes
0 votes
Find operation will take at most  ~2m time
& union operation will take at most  ~nlogn
So overall complexity = 2m+nlogn
& the biggest term is mlogn since m>n for connected graph where
 m is no.  of Edges & n is no.of vertices

Related questions

10 votes
10 votes
1 answer
1
Kathleen asked Sep 12, 2014
5,447 views
Maximum number of edges in a planar graph with $n$ vertices is _____
7 votes
7 votes
3 answers
2
Kathleen asked Sep 12, 2014
1,541 views
Macro expansion is done in pass one instead of pass two in a two pass macro assembler because _________
11 votes
11 votes
1 answer
3
Kathleen asked Sep 12, 2014
3,108 views
A simple and reliable data transfer can be accomplished by using the 'handshake protocol'. It accomplishes reliable data transfer because for every data item sent by the ...
7 votes
7 votes
4 answers
4
Kathleen asked Sep 12, 2014
3,031 views
Many of the advanced microprocessors prefetch instructions and store it in an instruction buffer to speed up processing. This speed up is achieved because ________