# 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.

21 questions
Filter by
Sorted by
Tagged with
1 vote
92 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 ...
• 149
1 vote
19 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 ...
• 313
140 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 ...
53 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 ...
• 121
24 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
123 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
176 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 ...
537 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 ...
56 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
74 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
326 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 ...
917 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 ...
• 33
1 vote
467 views

• 211
7k 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 ...
• 193
4k views

### Confusion in CLRS's version of Prim's algorithm

The algorithm is as follows: ...
• 1,685