---
# System prepended metadata

title: 'Lab: Spanning Trees'

---

# Lab: Spanning Trees

## Problem: Minimum Spanners

**a**.
- A B F H G E C D
- A C E G H F B D
- A B D F H G E C

**b**.
Edges: (A B) (A C) (C D) (D F) (C E) (E G) (G H)
Tree: A B C D F E G H

**c**.
Start with a MST of one node find the lowest costing edge
traverse then look at all picked nodes find lowest costing edge which touches a new node and repeat

**d**.
Algorithm:
1. Choose a node with the least costly connections
2. Take least costly connection to not previously connected node.
3. Repeat step two until all nodes are connected.