Register

MST Kruskal

1,375 views
1 1 vote

First statement is False because complexity will be O(E2).

I think the second statement is true? But not sure

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← Previous · Discrete mathematics...Next → · Shortest Path
← Previous in category · algorithmNext in category → · Shortest Path
Position:
Show:

Related questions

5 5 votes
1 1 answer
2.5k
2.5k views
sunil sarode asked Jan 2, 2018
2,545 views
How many MST is possible?
Given graph using Prim’s or Kruskal’s algorithm, find out that how many distinct minimum cost spanning trees are possible___?My answer was 1 and given is 2 ,what I am mi...
2 2 votes
0 0 answers
1.2k
1.2k views
sandip_1999 asked May 11, 2022
1,173 views
Why does Kruskal's algorithm find the minimum spanning tree if it's greedy? Isn't a minimum spanning tree a global optimization problem? Isn't the point of being greedy is that there is a chance you won't find the most optimal solution? So how can Kruskal be able to find the minimum spanning tree while also being greedy?
Please can anyone tell me though Prim’s and Kruskal’s algorithms are greedy algorithms. Greedy algorithms always give local optimum solutions but how Prim’s and Kruskal’s...
0 0 votes
0 0 answers
630
630 views
iarnav asked Apr 11, 2018
630 views
#Algorithms Kruskal Algorithm for MST Doubt.
Time Complexity of Kruskal - O(mlogm + n.O(1) + m.logn)mlogm for sorting edges in increasing order.n.O(1) n UNIONS as we've n nodes in G and each takes O(1)m.logm F...
1 1 vote
1 1 answer
887
887 views
rahul sharma 5 asked Sep 27, 2017
887 views
Algorithm kruskal algorithm MST
Which algorithm does kruskal uses for detecting every cycle and what is the time complexity?