> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-2/greedy_algorithm/minimum-spanning-tree.md).

# Minimum Spanning Tree

## Problem

Given an undirected graph $$G = (V, E)$$, each edge $$e \in E$$ has an edge cost $$W\_e$$. We want a tree that spans all $$n$$ vertices (has $$n-1$$ edges) with the minimum total cost.

Insert picture examples here

## Preliminaries

Simple Cycle: one cycle only

Cut: cut the graph into two parts.

Cutset: the edges in the cut

## Greedy Algorithm

Blue rule: If there is no blue edge in a cutset, then take any cheapest uncolored edge and color it blue (in this cutset).

Red rule: If there is a simple cycle with no red edges, then take any most expensive uncolored edge in this cycle and color it red.

Algorithm: apply red/blue rules in any order, color all edges until $$n-1$$ edges are colored blue

![](https://3556266963-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LtpqP4Bii7DT_BTd4fN%2F-LtpqQ7GPCPppH_fyCKt%2F-LtpqZRQlr39xeITqTzh%2FScreen%20Shot%202016-12-14%20at%203.25.01%20PM.png?generation=1573935270422685\&alt=media)