# Minimum Spanning Trees

Authors: Benjamin Qi, Andrew Wang

A subset of the edges of a connected, undirected, edge-weighted graph that connects all the vertices to each other of minimum total weight, where no cycles are allowed.

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 – read through this problem before continuing!

## Kruskal's

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

CPH | |||

cp-algo | |||

cp-algo | |||

CP2 |

**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 easily determine whether adding an edge will create a cycle in constant time using Union Find. Note that since the most expensive operation is sorting the edges, the computational complexity of Kruskal's Algorithm is $O(E \log E)$.

### Implementation

C++

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

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

1#include "DSU.h"23template<class T> T kruskal(int N, vector<pair<T,pi>> ed) {4 sort(all(ed));5 T ans = 0; DSU D; D.init(N); // edges that unite are in MST6 trav(a,ed) if (D.unite(a.s.f,a.s.s)) ans += a.f;7 return ans;8}

Java

1public static HashMap<Integer, ArrayList<Integer>> MST;2public static PriorityQueue<Edge> pq; //contains all edges34//Assumes that DSU code is included5public static void kruskal() {6 while (!pq.isEmpty()) {7 Edge e = pq.poll();8 if (find(e.start) != find(e.end)) {9 MST.get(e.start).add(e.end);10 MST.get(e.end).add(e.start);

### Solution - Road Reparation

C++

1#include <iostream>2#include <vector>3#include <algorithm>4using namespace std;56typedef long long ll;7typedef pair<int, int> pi;8typedef vector<int> vi;910#define trav(a,x) for (auto& a: x)

Java

1import java.io.*;2import java.util.*;34class kruskal {5 static int comp;6 static int disjoint[];7 static int size[];8 public static void main(String[] args) throws IOException {9 BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));10 PrintWriter out = new PrintWriter(System.out);

## 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 $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 $O(V)$, and this must be repeated $V$ times. Thus, this version of Prim's algorithm has complexity $O(V^2)$. As with Dijkstra, this complexity is preferable for dense graphs (in which $E \approx V^2$).

### Solution - Road Reparation

C++

1#include <iostream>2#include <vector>3#include <set>4using namespace std;56typedef long long ll;7typedef pair<ll, int> pl;8typedef vector<int> vi;910#define pb push_back

Java

1import java.io.*;2import java.util.*;34class prim {5 static Map<Integer, ArrayList<Edge>> tree;6 static int N, ct;7 static long[] dist;8 static long max = 10000000000000000 L;9 public static void main(String[] args) throws IOException {10 BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));

## USACO Problems

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

Old Silver | Easy | ## Show TagsMST | External Sol | ||

Gold | Easy | ## Show TagsMST | External Sol | ||

Gold | Normal | ## Show TagsMST, Prim | |||

HR | Normal | ## Show TagsMST, Binary Search | Check HR | ||

Plat | Hard | ## Show TagsMST | External Sol |