search
Log In

Recent questions tagged prims-algorithm

1 vote
0 answers
1
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 srestha 172 views
1 vote
0 answers
2
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 newly added vertex. but for the worst case, when ... many edges. This will end 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 aambazinga 279 views
2 votes
1 answer
3
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 algorithm is composed of : ... - MIN and DECREASE-KEY 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 Sandy Sharma 222 views
2 votes
0 answers
4
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.
asked Jan 8, 2018 in Algorithms ankit_thawal 362 views
5 votes
1 answer
5
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 sunil sarode 670 views
1 vote
2 answers
6
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 JPranavc 106 views
2 votes
3 answers
7
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)? 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 P-Q, Q-R, R-W, W-V, V-X, V-U, R-S, S-T P-Q, Q-R, R-W, R-S, V-X, V-U, W-V, S-T
asked Nov 17, 2017 in Algorithms Parshu gate 749 views
1 vote
0 answers
8
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 Shivam Chauhan 201 views
1 vote
0 answers
9
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 just_bhavana 289 views
3 votes
1 answer
10
Explain Prims Algorithm Analysis Of Time Complexity How does $\mathcal{O}(VlogV + ElogV)=\mathcal{O}(ElogV)$
asked Sep 22, 2017 in Algorithms pC 1.5k views
0 votes
0 answers
11
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
asked Sep 12, 2017 in Algorithms Anshul Shankar 140 views
1 vote
0 answers
12
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 have 8 has key ... we get 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 bhuv 370 views
3 votes
2 answers
13
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 Kapil 2k views
0 votes
0 answers
14
I am getting B and C both. Answer is given as C. Where am I wrong?
asked Jan 24, 2017 in Algorithms Samujjal Das 711 views
0 votes
0 answers
16
Here it is mentioned as a queue and not a priority queue ,what would be the answer ?
asked Jan 5, 2017 in Algorithms Harsh181996 81 views
2 votes
0 answers
18
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 PEKKA 555 views
2 votes
3 answers
19
Can Prim's and Kruskal's algorithm yield different minimum spanning trees? Explain why or why not.
asked Oct 26, 2016 in Algorithms Geet 697 views
1 vote
1 answer
20
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 admin 478 views
2 votes
1 answer
21
To see more, click for the full list of questions or popular tags.
...