# Minimum Spanning Trees

Authors: Benjamin Qi, Andrew Wang, Kuan-Hung Chen

Contributor: Neo Wang

Finding a subset of the edges of a connected, undirected, edge-weighted graph that connects all the vertices to each other of minimum total weight.

To review a couple of terms:

- An
**undirected edge**is an edge that goes both ways - A
**connected graph**is a graph of vertices such that each vertex can reach every other vertex using undirected edges. - A
**spanning tree**is a set of edges that forms a tree and contains every vertex in the original graph - A
**minimum spanning tree**is a spanning tree such that the sum of edge weights are minimized

Focus Problem – try your best to solve this problem before continuing!

## Kruskal's

Resources | ||||
---|---|---|---|---|

CPH | ||||

cp-algo | ||||

cp-algo | ||||

CP2 | ||||

alexyd88 |

**Kruskal's Algorithm** finds the MST by greedily adding edges. For all edges
not yet in the MST, we can repeatedly add the edge of minimum weight to the MST
except when adding edges that would forms a cycle. This can be done by sorting
the edges in order of non-decreasing weight.

Furthermore, we can determine whether adding an edge will create a cycle in constant time using a DSU.

Note that since the most expensive operation is sorting the edges, the computational complexity of Kruskal's Algorithm is $\mathcal{O}(E \log E)$.

Here's an animation of how the algorithm works:

### Solution - Road Reparation

Notice that the road that allows for a "decent route between any two cities," with cost "as small as possible" is the definition of a minimum spanning tree. Thus, we can use our favorite minimum spanning tree algorithm to determine the cost of such a tree by calculating $\sum c$ for all edges included in the tree.

However, we must also account for the impossible case, which occurs when any nodes cannot be connected to the tree. Recall that the minimum spanning tree must contain a total of $n-1$ edges, so we can use a variable $cnt$ that is incremented every time we add an edge to the minimum spanning tree. After running Kruskal's, if $cnt \ne n-1$, then we know that we failed to built the tree properly. Furthermore, since our minimum spanning tree algorithm gurantees no edges are counted twice, we cannot "accidentally" count $n-1$ edges.

C++

Resources | ||||
---|---|---|---|---|

Benq (from KACTL) | Disjoint Set Union + Kruskal |

#include <algorithm>#include <iostream>#include <vector>using std::cout;using std::endl;using std::pair;using std::vector;Code Snippet: DSU (from the module) (Click to expand)

Java

import java.io.*;import java.util.*;public class RoadReparation {Code Snippet: Road Class (Click to expand)public static void main(String[] args) throws IOException {BufferedReader read =new BufferedReader(new InputStreamReader(System.in));StringTokenizer initial = new StringTokenizer(read.readLine());

Python

### Warning: Constant Factor

Due to Python's constant factor, the below code will TLE on a couple of test cases.

Code Snippet: DSU (from the module) (Click to expand)city_num, road_num = map(int, input().split())roads = []for _ in range(road_num):a, b, cost = map(int, input().split())roads.append((cost, a - 1, b - 1))roads.sort()

## Prim's

Resources | ||||
---|---|---|---|---|

CPH | ||||

cp-algo | ||||

CP2 |

Similar to Dijkstra's, **Prim's algorithm** greedily adds vertices. On each
iteration, we add the vertex that is closest to the current MST (instead of
closest to the source in Dijkstra's) until all vertices have been added.

The process of finding the closest vertex to the MST can be done efficiently using a priority queue. After removing a vertex, we add all of its neighbors that are not yet in the MST to the priority queue and repeat. To begin the algorithm, we simply add any vertex to the priority queue.

### Complexity

Our implementation has complexity $\mathcal{O}(E \log E)$ since in the worst case every edge will be checked and its corresponding vertex will be added to the priority queue.

Alternatively, we may linearly search for the closest vertex instead of using a priority queue. Each linear pass runs in time $\mathcal{O}(V)$, and this must be repeated $V$ times. Thus, this version of Prim's algorithm has complexity $\mathcal{O}(V^2)$. As with Dijkstra, this complexity is preferable for dense graphs (in which $E \approx V^2$).

### Solution - Road Reparation

C++

#include <algorithm>#include <iostream>#include <limits>#include <queue>#include <vector>using std::cout;using std::endl;using std::pair;using std::vector;

Java

### Warning: Constant Factor

Due to Java's constant factor, the below code will TLE on a couple of test cases.

import java.io.*;import java.util.*;public class RoadReparation {public static void main(String[] args) throws IOException {BufferedReader read =new BufferedReader(new InputStreamReader(System.in));StringTokenizer initial = new StringTokenizer(read.readLine());int cityNum = Integer.parseInt(initial.nextToken());int roadNum = Integer.parseInt(initial.nextToken());

Python

from typing import List, Tupleimport heapqdef prim(neighbors: List[Tuple[int, int]]) -> int:n = len(neighbors) # just a shorthandmin_cost = 0dist = [float("inf") for _ in range(n)]dist[0] = 0

## Problems

The original problem statement for "Inheritance" is in Japanese. You can find a user-translated version of the problem here.

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Old Silver | Easy | ## Show TagsMST | |||

Gold | Easy | ## Show TagsMST | |||

CF | Easy | ## Show TagsMST | |||

CF | Normal | ## Show TagsMST, Math | |||

AC | Normal | ## Show TagsDSU | |||

Gold | Normal | ## Show TagsMST | |||

HR | Normal | ## Show TagsBinary Search, MST | |||

Gold | Normal | ## Show TagsMST | |||

JOI | Normal | ## Show TagsBinary Search, MST | |||

Gold | Normal | ## Show TagsMST | |||

Platinum | Hard | ## Show TagsMST | |||

COCI | Hard | ## Show TagsMST, NT | |||

Google Kickstart | Hard | ## Show TagsMST | |||

APIO | Insane | ## Show TagsBitmasks, MST |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!