CS61B Guide

Searchâ€¦

Object Oriented Programming

Abstract Data Types

Sorting

Algorithms

Minimum Spanning Trees

Special thanks to Arin for writing this page!

Spanning Tree Definition

A **spanning tree** T is a subgraph of a graph G where T:

- Is connected (there's a path to every vertex)
- Is acyclic (no cycles)
- Includes every vertex (spanning property)

A **minimum spanning tree** is a spanning tree with minimum total edge weight.

Example: I want to connect an entire town with wiring and would like to find the optimal wiring connection that connects everyone but uses the least wire.

MST vs. Shortest Path Tree

In contrast to a shortest path tree, which is essentially the solution tree to running Dijkstraâ€™s with root node = source vertex, a MST has no source. However, it is possible for the MST to be the same as the SPT.

We can think of the MST as a global property for the entire graph, as opposed to SPT which depends on which node is the source node.

If the edges of the graph are not unique, thereâ€™s a chance that the MST is not unique.

Cuts Property

- A
**cut**is defined as assigning the nodes in a graph into two sets. - A
**crossing edge**is an edge that connects two nodes that are in different sets - The smallest crossing edge is the crossing edge with smallest weight

The **Cut Property** states that the smallest crossing edge is always going to be in the MST, no matter how the cut is made.

Last modified 2yr ago

Copy link

On this page

Spanning Tree Definition

MST vs. Shortest Path Tree

Cuts Property