Questions tagged [prims-algorithm]
Prim's algorithm is a greedy algorithm which forms minimum spanning tree for the given graph. During execution, Prim's algorithm grows single tree by adding edges to it, unlike Kruskal's algorithm in which there can be multiple minimum spanning trees during execution.
19
questions
3
votes
2answers
69 views
Why do basic graph algorithms (BFS, DFS, Prim, Kruskal) have a similar structure?
This is my first post on CS Stack Exchange. For some time, I have been studying basic graph algorithms, mainly BFS, DFS, minimum spanning trees and their basic algorithms (Kruskal and Prim). One thing ...
2
votes
0answers
23 views
Minimum unrooted binary spanning tree
Given a graph $G$ with $n$ tip vertices, $n-2$ internal vertices and a cost on each edge $C(v)$, find a minimum spanning tree subject to degree constraints:
tips have degree $1$
internal vertices ...
0
votes
0answers
20 views
MST - Every edge visited once
I know that every vertex is visited exactly once but In Prim’s algorithm to find the MST, does every edge of the input graph is checked exactly once?How do I prove this? Although this look false but ...
1
vote
0answers
39 views
The Cut Lemma for graphs with non-distinct edges
In my introductory algorithms class I recently learned about the Cut Lemma and how it can be used to prove correctness for many Minimum Spanning Tree algorithms like Kruskal's and Prim's.
In class, to ...
1
vote
1answer
105 views
Find MST on grid graph with only weight of 1 and 2 in $O(|V|+|E|)$
Given a grid graph $G=(V,E)$ which has only two different integer costs/weights of 1 and 2. Find Minimum Spanning Tree in $O(|V|+|E|)$.
I tried the following:
Changing Kruskal using a counting Sort ...
0
votes
1answer
198 views
Best algorithm (Time Complexity) to find Minimum spanning tree of an complete, positive weighted, undirected, graph
Suppose that we have a complete undirected positive weighted graph $G = \langle V, E\rangle$. What is the most efficient algorithm, in terms of time complexity, to find an MST for $G$?
The best prime ...
0
votes
0answers
43 views
Improve Prim's algorithm runtime
Assume we run Prim’s algorithm when we know all the weights are
integers in the range {1, ...W} for W, which is logarithmic in |V|. Can you improve Prim’s running time?
When saying 'Improving', it ...
1
vote
1answer
65 views
Minimum Spanning Tree with one particular edge minimised(continued)
I have recently encountered a coding problem, specifically, the CCC problem S4.
In the problem, it states that you are given a spanning tree, or otherwise a "valid plan of pipes", that connect each ...
1
vote
2answers
246 views
Minimum spanning tree such that one edge can be minimised
During a computer coding exam, I have encountered such a problem.
Given a list of vertexes and edges between the vertexes,and a positive number, D, what is the minimum spanning tree between the ...
3
votes
3answers
658 views
MST: Is there such an example of a graph with unique mst and not unique light edge?
The problem is the following:
Give an example of a graph that has a unique minimum spanning tree but for every cut of the graph, there is not a unique light edge crossing the cut.
I am trying to ...
1
vote
2answers
424 views
Why the time complexity of Prim's algorithm is not $|V||E|lg|V|$ but $|E|lg|V|$?
In the CLRS, time complexity of Prim's algorithm is $O(|V|lg|V|+|E|lg|V|)=O(|E|lg|V|)$.
But, for my understanding, Prim's algorithm iterates $|E|$ times for DECREASE-KEY operation which takes $O(lg|V|...
1
vote
1answer
4k views
Minimum spanning tree - Prim's algorithm
I have to demonstrate Prim's algorithm for an assignment and I'm surprised that I found two different solutions, with different MSTs as an outcome. Now I now that shouldn't happen, so I wonder what I ...
1
vote
0answers
106 views
n'th cheapest MST in a graph, with multiple edges that can have the same weight
I'm trying to think about an algorithm for this problem.
I know there is an algorithm for the second cheapest MST in a graph, but
if I understood it correctly it only solves cases in which every ...
1
vote
2answers
7k views
Time complexity of Prim's algorithm
There is this Prim's algorithm I am studying, the time complexity of which is $O(n^2)$ (in the adjacency matrix).
As far as I have understood,that is because we have to ckeck all the nodes per every ...
2
votes
1answer
1k views
MST for a finite number of weights
Let $F$ be a finite set of real numbers say $\{w_1,\dots,w_k\}$.
Let $G=(V,E)$ be an undirected connected graph and let $w\colon E\to F$ be a weight function.
Describe a linear time algorithm that ...
3
votes
2answers
433 views
Minimum path - robot motion problem combined with freeze tag problem
Alright, I am not entirely sure if this is the right place to ask this, but here goes:
I have a map of coordinates of robots and obstacles. The first robot is awake from the start of the problem and ...
1
vote
1answer
591 views
Prim's algorithm on graph with weights of only $1$ and $2$ on each edge
I have this version of Prim's algorithm
Prim$(G=(V,E),s\in V,w)\\
1.\ d(s)\leftarrow 0;\forall u \neq s:d(u)\leftarrow \infty\quad \color{red}{O(|V|)}\\
2.\ \forall u \in V:p(u)\leftarrow \text{...
8
votes
1answer
6k views
Finding MST after adding a new vertex
Let $G=(V,E)$ which is undirected and simple. We also have $T$, an MST of $G$. We add a vertex $v$ to the graph and connect it with weighted edges to some of the vertices. Find a new MST for the new ...
3
votes
4answers
3k views
