Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged prims-algorithm
2
votes
0
answers
1
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
by
sandip_1999
180
views
kruskals-algorithm
prims-algorithm
minimum-spanning-tree
0
votes
1
answer
2
Prim Algorithm
What is the time complexity of Prim algorithm without using min heap?
Alakhator
asked
in
Algorithms
Oct 11, 2018
by
Alakhator
614
views
algorithms
graph-algorithms
prims-algorithm
time-complexity
1
vote
0
answers
3
Cormen 23.2-3
For a sparse graph $G=(V,E)$ where $|E|=\Theta (V)$ ... Plz tell me difference between Sparse and Dense graph here? How Dense graph implemented and how it make difference for this question
srestha
asked
in
Algorithms
Aug 24, 2018
by
srestha
704
views
algorithms
prims-algorithm
1
vote
0
answers
4
CLRS INTRODUCTION TO ALGORITHMS 3rd Edition, CHAPTER 23 QUESTION 23.2.7
suppose that a graph G has MST already computed. How quickly can we update the MST if we add a new vertex and incident edges to it. I know for the best case scenario when a single edge is incident from the ... up being linear time since we can reuse part of the DFS that we had already computed before detecting each cycle.
aambazinga
asked
in
Algorithms
Aug 19, 2018
by
aambazinga
922
views
algorithms
graph-algorithms
prims-algorithm
2
votes
1
answer
5
cormen 2nd edition excercise 23-2-5
Suppose that all edge weights in a graph are integers in the range from 1 to |V|. How fast can you make Prim's algorithm run? What if the edge weights are integers in the range from 1 to W for some constant W? Answer given :- The running time of Prims ... DECREASE-KEY speed up to O(lg lg V). Doubt 2 : why doubly linked list is used for range 1.... |W| ??
Sandy Sharma
asked
in
Algorithms
Jul 21, 2018
by
Sandy Sharma
1.1k
views
algorithms
prims-algorithm
2
votes
2
answers
6
Gradeup Test series
Suppose prim’s algorithm is implemented using array as queue for a graph $G(V,E)$. Then what is the time complexity of Prim’s algorithm? $O (E \hspace{0.1cm}log\hspace{0.1cm} V)$ $O (V^2 \hspace{0.1cm}log\hspace{0.1cm} V)$ $O(V^2)$ $O(VE)$
Aishwarya Gujrathi
asked
in
Algorithms
Mar 27, 2018
by
Aishwarya Gujrathi
829
views
test-series
prims-algorithm
time-complexity
2
votes
0
answers
7
TEST SERIES
Consider the following graph and Assume node ‘P’ as the starting vertex for Prim’s algorithm. Which of the following can be the correct order of edges to which they are added to construct Minimum Spanning Tree (MST)? P-Q, Q-R, R-W, R-S, V-X, V-U, W-V, S-T P-Q, Q-R, R-W, W-V, V-X, V-U, R-S, S-T P-Q, P-X, X-V, V-U, U-R, R-S, R-W, S-T P-Q, P-X, X-V, V-U, U-R, R-W, R-S, S-T PLEASE EXPLAIN.
ankit_thawal
asked
in
Algorithms
Jan 8, 2018
by
ankit_thawal
919
views
prims-algorithm
spanning-tree
minimum-spanning-tree
greedy-algorithm
5
votes
1
answer
8
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
1.5k
views
algorithms
spanning-tree
kruskals-algorithm
prims-algorithm
1
vote
2
answers
9
Regarding prims algo
Hello, I have doubt regarding prims algorithm 1)should we choose the lowest cost edge and then implement algo further? 2)Or we choose any vertex and then lowest cost edge of that vertex?
JPranavc
asked
in
DS
Nov 24, 2017
by
JPranavc
304
views
algorithms
prims-algorithm
2
votes
2
answers
10
Which of the following is the possible sequence of edges when Prim's algorithm is applied ?
(a,b),(b,c),(a,d),(e,f),(d,g),(c,e) (g,f),(f,c),(g,d),(c,e),(d,b),(d,a) (c,f),(c,e),(e,d),(a,b),(d,g),(b,c) None of the above
techbrk3
asked
in
Algorithms
Nov 17, 2017
by
techbrk3
294
views
graph-connectivity
prims-algorithm
1
vote
0
answers
11
MST Kruskal
First statement is False because complexity will be O(E2). I think the second statement is true? But not sure
Shivam Chauhan
asked
in
Algorithms
Nov 2, 2017
by
Shivam Chauhan
528
views
algorithms
minimum-spanning-tree
time-complexity
prims-algorithm
1
vote
0
answers
12
Prim's algorithm for MST
Assuming that the graph can contain repeated edge weights, we have a single tree at any instance when applying Prim's algorithm. Justify this statement.
just_bhavana
asked
in
Algorithms
Oct 30, 2017
by
just_bhavana
606
views
prims-algorithm
algorithms
3
votes
1
answer
13
Analysis Of Prims Algorithm Time Complexity
Explain Prims Algorithm Analysis Of Time Complexity How does $\mathcal{O}(VlogV + ElogV)=\mathcal{O}(ElogV)$
pC
asked
in
Algorithms
Sep 22, 2017
by
pC
2.3k
views
algorithms
prims-algorithm
time-complexity
0
votes
0
answers
14
Self Doubt (Graphs)
How to understand this: For a connected graph, V = O(E)) SOURCE http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-mst-for-adjacency-list-representation/ prims algorithm time complexity for adjacency list representation. Also same is given in CLRS but no reason
Anshul Shankar
asked
in
Algorithms
Sep 12, 2017
by
Anshul Shankar
218
views
prims-algorithm
clrs
1
vote
0
answers
15
prims algo from cormen
Here the graph that I was trying to find MST using algo in cormen.(If you need algo to ask, I supposed you have it) Algorithms uses min queue in process, my dobut is when it came to choice b/w vertex 'c' and 'd' as at that time both will ... wrong answer, so prism deal with this case? If you need algo I will given you, or just please refer chapter 23 cormen prim's algorithm.
bhuv
asked
in
Algorithms
Aug 5, 2017
by
bhuv
755
views
graph-algorithms
prims-algorithm
algorithms
5
votes
3
answers
16
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
2.8k
views
algorithms
graph-algorithms
kruskals-algorithm
prims-algorithm
0
votes
0
answers
17
Prim's Algorithm
I am getting B and C both. Answer is given as C. Where am I wrong?
Samujjal Das
asked
in
Algorithms
Jan 24, 2017
by
Samujjal Das
1.7k
views
prims-algorithm
algorithms
–1
vote
3
answers
18
Virtual Gate Test Series: Algorithms - Minimum Spanning Tree
I think all options are wrong
Purple
asked
in
Algorithms
Jan 11, 2017
by
Purple
667
views
algorithms
spanning-tree
minimum-spanning-tree
prims-algorithm
virtual-gate-test-series
0
votes
0
answers
19
Targate
Here it is mentioned as a queue and not a priority queue ,what would be the answer ?
Harsh181996
asked
in
Algorithms
Jan 5, 2017
by
Harsh181996
201
views
algorithms
graph-algorithms
prims-algorithm
0
votes
0
answers
20
Virtual Gate Test Series: Algorithms - Prim's Algorithm
both B and C correct order of prims algo?
firki lama
asked
in
Algorithms
Dec 30, 2016
by
firki lama
242
views
algorithms
prims-algorithm
virtual-gate-test-series
2
votes
0
answers
21
Analysis Of Prims Algorithm
I have seen many varients of complexities using diferent data structures in implementing Prims 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
797
views
algorithms
prims-algorithm
2
votes
3
answers
22
#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.3k
views
minimum-spanning-tree
algorithms
kruskals-algorithm
prims-algorithm
0
votes
1
answer
23
some1 plz explain why the time complexity of Prims algorithm using arrays is O(v^2+2E)...thanks in advance
anonymous
asked
in
Algorithms
Jun 26, 2016
by
anonymous
364
views
prims-algorithm
time-complexity
0
votes
1
answer
24
Algorithms
Can anyone explain me the time complexity of Prim's algorithm?
divya_theodore
asked
in
Algorithms
Jan 22, 2016
by
divya_theodore
526
views
time-complexity
prims-algorithm
1
vote
1
answer
25
Is array implementation better or the min heap in case of Prims algorithm
For prim's algorithm array implementation takes $O(V^2)$ while min heap implementation takes $O((E+V)\log V)$ time. For dense graph $E = O(V^2).$ So is array implementation considered better or the min heap one??? Does the min heap implementation run better for graph with less edges??
admin
asked
in
Algorithms
Oct 18, 2015
by
admin
1.5k
views
minimum-spanning-tree
prims-algorithm
3
votes
1
answer
26
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
by
Pooja Palod
2.4k
views
algorithms
descriptive
cormen
minimum-spanning-tree
kruskals-algorithm
prims-algorithm
1
vote
2
answers
27
Prim's Algorithm
Which one of following statement is false about prim's algorithm? a) It use a running time of O(Elog2V) using binary heap b) It may use a binomial max-heap to represent the priority queue. c) A fibonacci heap imlementation require O(E+V log2V) d) Initially all keys of nodes in priority queue are set to infinity . The root's key is set to 0.
dhingrak
asked
in
Algorithms
Jan 5, 2015
by
dhingrak
1.8k
views
prims-algorithm
heap
time-complexity
To see more, click for the
full list of questions
or
popular tags
.
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
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
Recent Posts
ISRO RECRUITMENT FOR SCIENTIST B THROUGH GATE
POWER GRID CORPORATION OF INDIA LIMITED
INSTITUTE OF BANKING PERSONNEL SELECTION
GATE Overflow books for TIFR, ISRO, UGCNET and NIELIT
RECRUITMENT IN OIL AND GAS CORPORATION LIMITED
Subjects
All categories
General Aptitude
(2.4k)
Engineering Mathematics
(9.1k)
Digital Logic
(3.2k)
Programming and DS
(5.8k)
Algorithms
(4.5k)
Theory of Computation
(6.6k)
Compiler Design
(2.3k)
Operating System
(4.9k)
Databases
(4.5k)
CO and Architecture
(3.7k)
Computer Networks
(4.5k)
Non GATE
(1.3k)
Others
(2.4k)
Admissions
(647)
Exam Queries
(841)
Tier 1 Placement Questions
(17)
Job Queries
(74)
Projects
(9)
Unknown Category
(855)
Recent questions tagged prims-algorithm
Recent Blog Comments
@abir_banerjee Thanks Abir. I'm third year...
@nolan_keats Currently I am in third year...
@abir_banerjee thank you Abir.Supposing you...
@nolan_keats just a suggestion as I also...
@abir_banerjee Hope I can do this in span of one...