CS61B Guide
  • This site is now deprecated
  • Object Oriented Programming
    • Inheritance
    • Access Control
    • Dynamic Method Selection
    • Java Objects
    • Generic Types
  • Asymptotics
    • Asymptotic Analysis Basics
    • Amortization
    • Asymptotics Practice
  • Abstract Data Types
    • Collections
      • Arrays
      • Linked Lists
      • Sets
      • Stacks and Queues
    • Binary Trees
      • Heaps
      • Balanced BSTs
      • Tries
    • Graphs
    • Hashing and Hash Tables
    • Union Find (Disjoint Sets)
    • Comparables and Comparators
  • Sorting
    • Sorting
  • Algorithms
    • Minimax Algorithm
    • Searching
      • Binary Search
      • Depth First Search (DFS)
      • Breadth First Search (BFS)
    • Shortest Paths
      • Dijkstra's Algorithm
      • A* Search
    • Minimum Spanning Trees
      • Prim's Algorithm
      • Kruskal's Algorithm
  • Misc Topics
    • Modular Arithmetic and Bit Manipulation
    • Exceptions
    • More Resources
Powered by GitBook
On this page
  • Spanning Tree Definition
  • MST vs. Shortest Path Tree
  • Cuts Property

Was this helpful?

  1. 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)

Notice: the first two properties defines a tree structure, and the last property makes the tree spanning.

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.

PreviousA* SearchNextPrim's Algorithm

Last updated 5 years ago

Was this helpful?