Skip to main content
6 votes
Accepted

Finding MST after adding a new vertex

As stated in your post, the idea is to use Prim's algorithm with only the edges from $T$ and the new edges, let's call them $E'$. For the sake of simplicity, let's assume that $T$ is the unique MST. ...
T. Silver's user avatar
  • 176
5 votes

Minimum path - robot motion problem combined with freeze tag problem

Define a fully connected, undirected graph $G$ so that there is a vertex for the initial position of each robot, and an edge between each two vertices whose length corresponds to the time for a robot ...
D.W.'s user avatar
  • 162k
4 votes

Why the time complexity of Prim's algorithm is not $|V||E|lg|V|$ but $|E|lg|V|$?

The pseudocode for Prim's algorithm, as stated in CLRS, is as follows: ...
kevinz's user avatar
  • 141
3 votes
Accepted

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

Let $G_0$ be your input graph, label each edge $(u,v)$ with $(u,v)$ itself. Repeat the following for all values of $i$ from $1$ to $5$: Compute a spanning forest $F_i$ of the subgraph of $G_{i-1}$ ...
Steven's user avatar
  • 29.5k
3 votes
Accepted

Why the time complexity of Prim's algorithm is not $|V||E|lg|V|$ but $|E|lg|V|$?

DECREASE-KEY is called at most $2|E|$ times: it is called at most twice per edge (i.e., for each edge $(u,v)$, we call DECREASE-KEY on $v$ when $u$ leaves the queue, and DECREASE-KEY on $u$ when $v$ ...
D.W.'s user avatar
  • 162k
2 votes
Accepted

Time complexity of Prim's algorithm

The time complexity is $O(n^2)$ because $O(n\cdot(n-1)) = O(n^2)$ The big-O notation is showing the worst-case performance of one algorithm, it is not showing the exact number of steps the algorithm ...
someone12321's user avatar
  • 1,428
2 votes

MST for a finite number of weights

Summary: An algorithm of linear time in $|E|$ can be given by an implementation of Prim's algorithm where its priority queue is $|F|$ queues of equal-weight edges, assuming $|F|$ is a constant. We ...
John L.'s user avatar
  • 39.1k
2 votes
Accepted

Minimum spanning tree such that one edge can be minimised

In the following, I assume the set of all feasible solutions is the set $\{(T,uv):T$ is a not necessarily minimum spanning tree of $G$ and $uv$ is a distinguished edge in $T\}$, with the cost of a ...
j_random_hacker's user avatar
2 votes
Accepted

MST: Is there such an example of a graph with unique mst and not unique light edge?

No. Here is a proof. Suppose $G$ is a weighted undirected graph such that for every cut of the graph, there is not a unique lightest edge crossing the cut. Let $M$ be a (or "the" in case it is ...
John L.'s user avatar
  • 39.1k
2 votes

MST: Is there such an example of a graph with unique mst and not unique light edge?

I found this answer in a book: Consider a graph with 3 vertices a,b,c and weights w(a,b) = w(a,c) = 1 and w(b,c) = 2. The graph has a unique minimal spanning tree (containing edges (a,b) and (a,c)...
Ana Maria Statie's user avatar
2 votes

MST: Is there such an example of a graph with unique mst and not unique light edge?

If there is not a unique light edge crossing any cut, it means that every node has at least 2 edges of minimum weight. If you use Prim's algorithm to build your MST which is: ...
Optidad's user avatar
  • 1,788
2 votes
Accepted

Why do basic graph algorithms (BFS, DFS, Prim, Kruskal) have a similar structure?

When we want to design an algorithm, we mainly consider how our data is organized. When we model a problem with graph for example, the things we could do are restricted to this specified model. For ...
Omid Yaghoubi's user avatar
2 votes
Accepted

Find MST on grid graph with only weight of 1 and 2 in $O(|V|+|E|)$

Let $n=|V|$ and $m=|E|$. Intuitively you want the to return the union of the edges in 1) a maximal spanning forest $F$ of the graph induced by the edges of weight $1$, with 2) a maximal spanning ...
Steven's user avatar
  • 29.5k
2 votes
Accepted

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

You should use Prim's algorithm instead of Kruskal's algorithm. Given a weighted undirected graph $G = (V, E, f)$ with $f(E) \subseteq \{1, 2, 3\}$ as an adjacency lists array, the following should ...
Nathaniel's user avatar
  • 15.8k
1 vote

Why do basic graph algorithms (BFS, DFS, Prim, Kruskal) have a similar structure?

One way to see the similarities between BFS and DFS is to consider them as the same algorithm (or perhaps some sort of "meta algorithm"), but using a different underlying data-structure: BFS ...
Discrete lizard's user avatar
  • 8,303
1 vote
Accepted

Minimum Spanning Tree with one particular edge minimised(continued)

Run Kruskal's algorithm on the weighted graphs of all buildings as vertices and all pipes with original costs as edges with weights, with the following modification. When we are going to select the ...
John L.'s user avatar
  • 39.1k
1 vote
Accepted

Minimum spanning tree - Prim's algorithm

Prim's algorithm could give different solutions (depending on how you resolve "ties"), but all solutions should give a MST with the same (minimal) weight, which is not the case here. Your second ...
user53923's user avatar
  • 453
1 vote

Minimum path - robot motion problem combined with freeze tag problem

Note: This answer was written for a related problem where the goal is to minimize total distance travelled rather than elapsed time. This looks a lot like a minimum spanning tree problem (as your ...
combo's user avatar
  • 131
1 vote
Accepted

Prim's algorithm on graph with weights of only $1$ and $2$ on each edge

The running time depends on how you implement the queue data structure. Hint: Can you think of any way to implement the queue data structures, so that ExtractMin, Remove, and Insert operations are ...
D.W.'s user avatar
  • 162k
1 vote

Finding MST after adding a new vertex

(This is a copy of the answer to the same question on the general StackOverflow) There exist algorithms that can add a vertex with all its edges to a graph with a known MST in linear time, which is ...
Maxim Buzdalov's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible