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.

Filter by
Sorted by
Tagged with
1
vote
1answer
35 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
59 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
107 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
209 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
948 views

Prim's algorithm - misunderstanding

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
69 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
4k 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
293 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
409 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
463 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{...
6
votes
1answer
3k 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
2k views

Confusion in CLRS's version of Prim's algorithm

The algorithm is as follows: ...