Dark Mode

Recent questions tagged kruskals-algorithm

0 votes

1 answer

1

UGC NET CSE | June 2008 | Part 2 | Question: 2
The complexity of Kruskal's minimum spanning tree algorithm on a graph with ' $n$ ' nodes and ' $e$ ' edges is : $\mathrm{O}(n)$ $\mathrm{O}(n \log n)$ $\mathrm{O}(e \log n)$ $\mathrm{O}(e)$

admin asked in Others Jan 6

by admin

85 views

0 votes

0 answers

2

Çșȇ ʛấẗẻ asked in Mathematical Logic Aug 28, 2023

by Çșȇ ʛấẗẻ

63 views

2 votes

2 answers

3

Gate@Zeal Booklet
Can anyone help in solving the question 105 to 109. I don't have answer key I want to confirm my answer ...i will update my answer in the comments.

Psy Duck asked in Algorithms Jun 24, 2023

940 views

2 votes

0 answers

4

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?

sandip_1999 asked in Algorithms May 11, 2022

668 views

0 votes

1 answer

5

Churchill Khangar asked in Algorithms Nov 22, 2018

by Churchill Khangar

551 views

0 votes

2 answers

6

please explain also..

Mak Indus asked in Algorithms Nov 10, 2018

379 views

1 vote

1 answer

7

Kruskal Algorithm
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 unsorted is _______ ______________________________________________________________________________ If elements are sorted we do with Union Find algo with ... is $log^{*}V$ Now from here can we derive it for unsorted edges? for ref: here

srestha asked in Algorithms Jun 30, 2018

1.6k views

1 vote

1 answer

8

#Graphs
Is there any best method for implementing kruskal algorithm without using priority queue?? and can we use min heap here??

G Shaheena asked in Algorithms Apr 5, 2018

201 views

5 votes

1 answer

9

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 missing ? Edit:I had confirmed with it and answer is only one tree possible.

sunil sarode asked in Algorithms Jan 2, 2018

by sunil sarode

2.0k views

0 votes

0 answers

10

Kruskal time complexity
Solve this

saumya mishra asked in Algorithms Sep 25, 2017

by saumya mishra

582 views

0 votes

1 answer

11

cormen
calculating time complexity of kruskal algorithm by this way is right? build min heap- storing edges - O(n) extracting edges V-1 times - O((v-1) log E) ~ O(V log E) so total time complexity is O(E +V log E) or O(E+ E log E) while extracting edges if first V-1 edges ... it is best case- O(E+ V log E) and if need to extract all edges because only last edge is not creating cycle - O(E+ E log V)

shebya nautiyal asked in Algorithms Apr 10, 2017

by shebya nautiyal

286 views

5 votes

3 answers

12

Difference between Kruskal's and Prim's algorithm ?
It may be the case that "Kruskal's Algorithm may not maintain connectivity while Prim's algorithm always does that" ? Any example which favours this ?

Kapil asked in Algorithms Jan 24, 2017

by Kapil

3.4k views

2 votes

1 answer

13

Analysis OF Kruskal's Algorithm
I have seen many varients of complexities using diferent data structures in implementing Kruskal Agorithm. Can you pls post standard algorithm and tells me in details how to derive the complexities. Please also mention the variations possibles when data structure changes and How will effect the complexity taking Best case and Worst case senarios .

PEKKA asked in Algorithms Dec 18, 2016

by PEKKA

4.7k views

0 votes

2 answers

14

Kruskals MST
Consider a graph with V vertices and e edges,What is the worst case time complexity for kruskal's algorithm when implemented using array data structure? a.) E+ElogV b.)VlogV c.)V^2 d.)Vlog^2V

rahul sharma 5 asked in Algorithms Dec 15, 2016

by rahul sharma 5

797 views

2 votes

3 answers

15

#algorithm
Can Prim's and Kruskal's algorithm yield different minimum spanning trees? Explain why or why not.

Geet asked in Algorithms Oct 26, 2016

by Geet

1.6k views

2 votes

1 answer

16

Made Easy
what will be the change in time when quick sort is used over the heap sort to sort the edges in order to find the MST using kruskal algorithm...no of edges = 16

cse23 asked in Algorithms Oct 8, 2016

by cse23

1.3k views

3 votes

1 answer

17

Cormen Edition 3 Exercise 23.2 Question 6 (Page No. 637)
Suppose that edge weights are uniformly distributed over half open interval $[0,1)$. Which algorithm kruskal's or prim's can make you run faster?

Pooja Palod asked in Algorithms Oct 15, 2015

3.0k views

0 votes

2 answers

18

How does Kruskal algorithm detect cycle in the graph and what is the time taken ?
Does it tale constant time or the time taken proportional to search in the entire partition of elements to find whether the component lies in that same component or not ?

radha gogia asked in Algorithms Aug 5, 2015

2.1k views

To see more, click for the full list of questions or popular tags.

Recent questions tagged kruskals-algorithm