# Minimum Spanning Trees

## Table of contents

- Minimum spanning trees
- Prim’s algorithm
- Prim’s demo
- Kruskal’s algorithm
- Kruskal’s demo
- MST algorithms
- MST vs SPT
- Negative edge weights

## Minimum spanning trees

## Prim’s algorithm

## Prim’s demo

## Kruskal’s algorithm

## Kruskal’s demo

## MST algorithms

Consider the following undirected weighted graph.

### Question 1

Give the order in which Prim’s algorithm selects edges starting from s as a comma-separated list e.g. `1, 2, 3, 4, 5, 6, 7, 8, 9`

. Not all edges may be needed.

### Question 2

After adding the edge with weight 1 to the known set in Prim’s algorithm, which edges are on the cut between the known and unknown vertices?

- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9

## Explanation

The 4 vertices on the left side of the graph are separated from the 2 vertices on the right edge of the graph. There are 3 edges on the cut between these two sets of vertices.

### Question 3

Give the order in which Kruskal’s algorithm selects edges as a comma-separated list e.g. `1, 2, 3, 4, 5, 6, 7, 8, 9`

. Not all edges may be needed.

### Question 4

Suppose we want to connect all apartments to the internet. An apartment will receive internet so long as it has either a router installed or a fiber connection. We want to minimize the cost of installation. Give a reduction algorithm to minimum spanning trees for this problem.

The above example contains 6 apartments and 10 possible fiber connections. The optimal solution installs a router in apartments **1** and **4** (for a cost of 50) and builds fiber connections **0–1**, **1–6**, **3–4**, **4–5** (for a cost of 65).

## MST vs SPT

Let’s compare and contrast minimum spanning trees (MSTs) with shortest paths trees (SPTs).

### Question 1

Compare and contrast the shortest paths problem and the minimum spanning tree problem.

### Question 2

Compare and contrast Prim’s algorithm and Dijkstra’s algorithm.

## Negative edge weights

Dijkstra’s algorithm is not guaranteed to return a valid shortest paths tree if the graph contains negative edge weights. How about Prim’s algorithm? Let’s also consider a new strategy for resolving the problem.

### Question 1

Consider a graph with negative edge weights. Suppose we added the same constant value to each edge weight such that all of the edges now have non-negative weights.

True/False: If we run Dijkstra’s algorithm on this modified graph, is it guaranteed to return a valid shortest paths tree for the original graph?

## Explanation

By increasing each edge weight, we’re inadvertently penalizing paths with more edges! A path from s to t with 2 edges would receive 2 times the constant value to its cost, whereas a direct edge between s and t would only receive a single constant value increase.

### Question 2

Consider the same setup as in the prior question.

True/False: If we run Prim’s algorithm on this modified graph, is it guaranteed to return a valid minimum spanning tree for the original graph?

## Explanation

This actually does work because Prim’s algorithm does not consider path lengths. Another way to see this is that the cost of any spanning tree is increased by |*E*| times the constant value, so the minimum spanning tree in the modified graph will be the same as the minimum spanning tree in the original graph.

### Question 3

True/False: Prim’s algorithm computes a valid minimum spanning tree in any undirected graph, even ones with negative edge weights.

## Explanation

Dijkstra’s algorithm struggled with negative-weight shortcut edges hidden behind otherwise expensive paths. However, since Prim’s algorithm orders the priority queue by lowest-known edge weight rather than lowest-known path cost, these hidden edges will not be a problem. They’ll eventually be added to the minimum spanning tree later if applicable.