Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
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)$
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)...
admin
78
views
admin
asked
Jan 6
Others
ugcnetcse-june2008-paper2
kruskals-algorithm
minimum-spanning-tree
+
–
0
votes
0
answers
2
Kruskal
Çșȇ ʛấẗẻ
59
views
Çșȇ ʛấẗẻ
asked
Aug 28, 2023
Mathematical Logic
kruskals-algorithm
+
–
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.
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
910
views
Psy Duck
asked
Jun 24, 2023
Algorithms
kruskals-algorithm
greedy-algorithm
prims-algorithm
minimum-spanning-tree
zeal
zeal-workbook
+
–
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?
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 Kru...
sandip_1999
665
views
sandip_1999
asked
May 11, 2022
Algorithms
kruskals-algorithm
prims-algorithm
minimum-spanning-tree
+
–
0
votes
1
answer
5
IIT Delhi
Churchill Khangar
542
views
Churchill Khangar
asked
Nov 22, 2018
Algorithms
spanning-tree
kruskals-algorithm
test-series
+
–
0
votes
2
answers
6
please explain also..
Mak Indus
372
views
Mak Indus
asked
Nov 10, 2018
Algorithms
algorithms
kruskals-algorithm
+
–
1
votes
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
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 __________...
srestha
1.6k
views
srestha
asked
Jun 30, 2018
Algorithms
algorithms
minimum-spanning-tree
kruskals-algorithm
+
–
1
votes
1
answer
8
#Graphs
Is there any best method for implementing kruskal algorithm without using priority queue?? and can we use min heap here??
Is there any best method for implementing kruskal algorithm without using priority queue?? and can we use min heap here??
G Shaheena
197
views
G Shaheena
asked
Apr 5, 2018
Algorithms
kruskals-algorithm
binary-heap
+
–
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.
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 a...
sunil sarode
2.0k
views
sunil sarode
asked
Jan 2, 2018
Algorithms
algorithms
spanning-tree
kruskals-algorithm
prims-algorithm
+
–
0
votes
0
answers
10
Kruskal time complexity
Solve this
Solve this
saumya mishra
577
views
saumya mishra
asked
Sep 25, 2017
Algorithms
kruskals-algorithm
+
–
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)
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...
shebya nautiyal
280
views
shebya nautiyal
asked
Apr 10, 2017
Algorithms
time-complexity
kruskals-algorithm
+
–
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 ?
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
3.4k
views
Kapil
asked
Jan 24, 2017
Algorithms
algorithms
graph-algorithms
kruskals-algorithm
prims-algorithm
+
–
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 .
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 ho...
PEKKA
4.7k
views
PEKKA
asked
Dec 18, 2016
Algorithms
algorithms
kruskals-algorithm
+
–
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
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+ElogVb.)Vlog...
rahul sharma 5
792
views
rahul sharma 5
asked
Dec 15, 2016
Algorithms
data-structures
kruskals-algorithm
time-complexity
+
–
2
votes
3
answers
15
#algorithm
Can Prim's and Kruskal's algorithm yield different minimum spanning trees? Explain why or why not.
Can Prim's and Kruskal's algorithm yield different minimum spanning trees? Explain why or why not.
Geet
1.6k
views
Geet
asked
Oct 26, 2016
Algorithms
minimum-spanning-tree
algorithms
kruskals-algorithm
prims-algorithm
+
–
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
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
1.3k
views
cse23
asked
Oct 8, 2016
Algorithms
time-complexity
sorting
minimum-spanning-tree
kruskals-algorithm
+
–
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?
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
3.0k
views
Pooja Palod
asked
Oct 15, 2015
Algorithms
algorithms
descriptive
cormen
minimum-spanning-tree
kruskals-algorithm
prims-algorithm
+
–
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 ?
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
2.1k
views
radha gogia
asked
Aug 5, 2015
Algorithms
graph-algorithms
time-complexity
kruskals-algorithm
+
–
To see more, click for the
full list of questions
or
popular tags
.
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register