The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Categories
Users
Ask a Question
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged primsalgorithm
+1
vote
0
answers
1
Cormen 23.23
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
asked
Aug 24, 2018
in
Algorithms
by
srestha
Veteran
(
113k
points)

61
views
algorithms
primsalgorithm
+1
vote
0
answers
2
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.
asked
Aug 19, 2018
in
Algorithms
by
aambazinga
Active
(
3.2k
points)

102
views
algorithms
graphalgorithms
primsalgorithm
+2
votes
1
answer
3
cormen 2nd edition excercise 2325
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 ... DECREASEKEY speed up to O(lg lg V). Doubt 2 : why doubly linked list is used for range 1.... W ??
asked
Jul 21, 2018
in
Algorithms
by
Sandy Sharma
Active
(
1.2k
points)

69
views
algorithms
primsalgorithm
+2
votes
0
answers
4
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)? PQ, QR, RW, RS, VX, VU, WV, ST PQ, QR, RW, WV, VX, VU, RS, ST PQ, PX, XV, VU, UR, RS, RW, ST PQ, PX, XV, VU, UR, RW, RS, ST PLEASE EXPLAIN.
asked
Jan 8, 2018
in
Algorithms
by
ankit_thawal
Active
(
1.4k
points)

254
views
primsalgorithm
spanningtree
minimumspanningtrees
greedyalgorithm
+5
votes
1
answer
5
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.
asked
Jan 2, 2018
in
Algorithms
by
sunil sarode
Active
(
1.2k
points)

423
views
algorithms
spanningtree
kruskalsalgorithm
primsalgorithm
+1
vote
2
answers
6
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?
asked
Nov 24, 2017
in
DS
by
JPranavc
(
351
points)

68
views
algorithms
primsalgorithm
+2
votes
3
answers
7
Prims algorithm
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 in which they are added to construct Minimum Spanning Tree (MST)? PQ, PX, XV, VU, UR, RS, RW, ST PQ, PX, XV, VU, UR, RW, RS, ST PQ, QR, RW, WV, VX, VU, RS, ST PQ, QR, RW, RS, VX, VU, WV, ST
asked
Nov 17, 2017
in
Algorithms
by
Parshu gate
Active
(
3.1k
points)

454
views
algorithms
primsalgorithm
graphalgorithms
+1
vote
0
answers
8
MST Kruskal
First statement is False because complexity will be O(E2). I think the second statement is true? But not sure
asked
Nov 2, 2017
in
Algorithms
by
Shivam Chauhan
Loyal
(
8.7k
points)

126
views
algorithms
mst
timecomplexity
primsalgorithm
+1
vote
0
answers
9
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.
asked
Oct 30, 2017
in
Algorithms
by
just_bhavana
Boss
(
12k
points)

236
views
primsalgorithm
algorithms
+3
votes
1
answer
10
Analysis Of Prims Algorithm Time Complexity
Explain Prims Algorithm Analysis Of Time Complexity How does $\mathcal{O}(VlogV + ElogV)=\mathcal{O}(ElogV)$
asked
Sep 22, 2017
in
Algorithms
by
pC
Boss
(
21.2k
points)

1.1k
views
algorithms
primsalgorithm
timecomplexity
0
votes
0
answers
11
Self Doubt (Graphs)
How to understand this: For a connected graph, V = O(E)) SOURCE http://www.geeksforgeeks.org/greedyalgorithmsset5primsmstforadjacencylistrepresentation/ prims algorithm time complexity for adjacency list representation. Also same is given in CLRS but no reason
asked
Sep 12, 2017
in
Algorithms
by
Anshul Shankar
Active
(
1k
points)

81
views
primsalgorithm
clrs
+1
vote
0
answers
12
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.
asked
Aug 5, 2017
in
Algorithms
by
bhuv
Active
(
4.6k
points)

263
views
graphalgorithms
primsalgorithm
algorithms
+3
votes
2
answers
13
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 ?
asked
Jan 24, 2017
in
Algorithms
by
Kapil
Veteran
(
50.4k
points)

1.9k
views
algorithms
graphalgorithms
kruskalsalgorithm
primsalgorithm
0
votes
0
answers
14
Prim's Algorithm
I am getting B and C both. Answer is given as C. Where am I wrong?
asked
Jan 24, 2017
in
Algorithms
by
Samujjal Das
Loyal
(
9.2k
points)

501
views
primsalgorithm
algorithms
–1
vote
3
answers
15
Virtual Gate Test Series: Algorithms  Minimum Spanning Tree
I think all options are wrong
asked
Jan 11, 2017
in
Algorithms
by
Purple
Active
(
2.9k
points)

272
views
algorithms
spanningtree
minimumspanningtrees
primsalgorithm
virtualgatetestseries
0
votes
0
answers
16
Targate
Here it is mentioned as a queue and not a priority queue ,what would be the answer ?
asked
Jan 5, 2017
in
Algorithms
by
Harsh181996
Active
(
4.3k
points)

62
views
algorithms
graphalgorithms
primsalgorithm
0
votes
0
answers
17
Virtual Gate Test Series: Algorithms  Prim's Algorithm
both B and C correct order of prims algo?
asked
Dec 30, 2016
in
Algorithms
by
firki lama
Junior
(
651
points)

88
views
algorithms
primsalgorithm
virtualgatetestseries
+2
votes
0
answers
18
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 .
asked
Dec 18, 2016
in
Algorithms
by
PEKKA
Active
(
1.9k
points)

454
views
algorithms
primsalgorithm
+2
votes
3
answers
19
#algorithm
Can Prim's and Kruskal's algorithm yield different minimum spanning trees? Explain why or why not.
asked
Oct 26, 2016
in
Algorithms
by
Geet
(
169
points)

523
views
minimumspanningtrees
algorithms
kruskalsalgorithm
primsalgorithm
+1
vote
1
answer
20
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??
asked
Oct 18, 2015
in
Algorithms
by
admin
Active
(
2.4k
points)

313
views
minimumspanningtrees
primsalgorithm
To see more, click for the
full list of questions
or
popular tags
.
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
ISI MTECH CS 2019 INTERVIEW EXPERIENCE
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
Follow @csegate
Recent questions tagged primsalgorithm
Recent Blog Comments
received the GO books in good conditions!! thanks
Sir please update your stocks, when it will be...
Yes. Stock is over with Indiapost.
But on Amazon the stock is there and a way too...
49,829
questions
54,735
answers
189,349
comments
80,095
users