The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+9 votes
1.7k views
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 _______
asked in Algorithms by Veteran (68.8k points) | 1.7k views

3 Answers

+18 votes
Best answer

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|))$

answered by Veteran (13.8k points) 1 flag
edited by
PLease tell me the source to read this.
is it right to say O(V+E)   ??
in one of the madeeasy test ans given O(V+E) ,
When the edges are already sorted then, The problem of finding the minimum spanning tree reduces to detecting if there is a cycle in the graph or not.

I mean since edges are already sorted, take each edge one by one and add to mst (if no cycle is formed).

Now, detecting whether an undirected graph has a cycle or not can be done ::

1) Either using DFT or BFT :: O(V+E)

2)Using Union-Find :: O(ElogV)
can u clarify it?
@suvasish pal

What exactly you need clarification on ??
@ VS:-

How many times you will apply BFS?It needs to be applies for every egde.

Also, for you point it should be E*loge ,because e times we will apply cycle detection algorithm and each time it takes log e time.

so it should be eloge
@rahul,

Same doubt,
@Vikrant singh time complexity of union-find is O(ElogV) according to geeksforgeeks. How is it being said as Elog^*(n)??
@rahul

E=V(V-1)/2

E=V^2 (Approx)

taking log both sides

O(lgE)=O(lgV)
so it should be mlogn ,right? Union find works in log n time and for each edge we traverse we check if cycle is there or not(in a graph of n vertices) ,taking logn time.

So answer mLogn is correct?m edges and n vertices.

I think the answer should simply be O(E)

https://en.wikipedia.org/wiki/Proof_of_O(log*n)_time_complexity_of_union%E2%80%93find

According to wikipedia amortized time complexity of unoin find is O(log*V), as Arjun said in one other answer log*n is practically a constant. For E  unoin find operations, the answer would simply be E*O(1), Therefore O(E)

Complexity of kruskal is O(ElogE + E) .... ElogE for sorting the edges  and E for union operation of E edges ...

So here it is sorted ... so O(E) ... correct me if i am wrong ... Refer this ...

 

 

–1 vote
Though edges are sorted still due to union find operation complexity is O(mlogn).
answered by Loyal (4k points)
–1 vote
ANSWER SHOULD BE O(V+E).
answered by Boss (7.8k points)
Answer will be O(E LogV)  because we have to check for all the edges if there is any cycle while including in MST.

Some have given answer O(E+V) which is wrong.


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

32,442 questions
39,188 answers
108,794 comments
36,561 users