# Recent questions tagged prims-algorithm

1 vote
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
1 vote
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.
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| ??
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.
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.
1 vote
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?
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
1 vote
8
First statement is False because complexity will be O(E2). I think the second statement is true? But not sure
1 vote
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.
10
Explain Prims Algorithm Analysis Of Time Complexity How does $\mathcal{O}(VlogV + ElogV)=\mathcal{O}(ElogV)$
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
1 vote
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.
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 ?
14
I am getting B and C both. Answer is given as C. Where am I wrong?
–1 vote
15
I think all options are wrong
16
Here it is mentioned as a queue and not a priority queue ,what would be the answer ?
17
both B and C correct order of prims algo?
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 .
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??
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?