Skip to main content

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
0 votes
1 answer
32 views

Lightest Paths Tree that is 10 times heavier than an MST of the same graph

Something I was asked to solve and tried to come up with a formula or some method to solve it after I did and couldn't. Given is a graph G=(V,E) that is undirected and weighted. Say we want to find ...
Eddie's user avatar
  • 1
1 vote
1 answer
331 views

Find MST with bounded edge weight in O(|V|+|E|)

I need to describe (even in words) an algorithm that gets a connected, undirected, weighted graph so that the weight of each edge is either 1,2 or 3; and returns MST of that graph is time complexity O(...
DR_2001's user avatar
  • 25
1 vote
1 answer
425 views

Why Prim algorithm may fail to return minimum spanning forest on disconnected undirected graph

I am trying to address the following claim- "running prim algorithm on a disconnected undirected graph returns minimum spanning forest". I thing that the claim may be false (i.e there might ...
DR_2001's user avatar
  • 25
1 vote
1 answer
176 views

MST with weights in {1, 2, 3, 4, 5}

I am given an undirected connected graph with $n$ nodes, average degree $\sqrt{\log n}$, and each edge having integer weight in $\{1,..,5\}$. I am asked to describe MST algorithm which is as efficient ...
NiRvanA's user avatar
  • 159
1 vote
0 answers
22 views

How to find if there's an MST where vertex $v$ has degree 2 in it? [duplicate]

I've faced this question and I hope that someone can help with it. Question: We're given an undirected graph $G=(V,E,w)$ where $w\colon E\rightarrow \mathbb{Q}$ and vertex $v$. We want to find if ...
Mohamad S.'s user avatar
4 votes
2 answers
650 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 ...
George1917's user avatar
2 votes
0 answers
74 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 a degree of $1$ internal ...
user157116's user avatar
3 votes
0 answers
560 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 ...
Andrew Bell's user avatar
1 vote
1 answer
319 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 ...
OuttaSpaceTime's user avatar
0 votes
1 answer
772 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 ...
hossein torki's user avatar
0 votes
0 answers
102 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 ...
Osure's user avatar
  • 1
1 vote
1 answer
81 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 ...
Aarony Jamesys's user avatar
1 vote
2 answers
493 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 ...
Aarony Jamesys's user avatar
4 votes
3 answers
2k 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 ...
LukacsE's user avatar
  • 43
1 vote
2 answers
647 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|...
molamola's user avatar
  • 353
1 vote
1 answer
7k 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 ...
Phreneticus's user avatar
1 vote
0 answers
156 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 ...
mathkid's user avatar
  • 29
1 vote
2 answers
8k 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 ...
parvin's user avatar
  • 629
3 votes
1 answer
2k 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 ...
Don Fanucci's user avatar
3 votes
2 answers
467 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 ...
Alexandru Chiriac's user avatar
1 vote
1 answer
849 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{...
Error 404's user avatar
  • 211
10 votes
2 answers
8k 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 ...
LiorGolan's user avatar
  • 213
3 votes
4 answers
4k views

Confusion in CLRS's version of Prim's algorithm

The algorithm is as follows: ...
Mahesha999's user avatar
  • 1,773