Minimum Spanning Trees

Analysis and Design of Algorithms

Jesus A. Gonzalez

July 17, 2019

Introduction

Wiring Electronic Circuits Problem (1)

Wiring Electronic Circuits Problem (2)

Algorithms to Cover

Growing an \(MST\)

Loop Invariant - Generic Algorithm - \(MST\)

Generic MST Algorithm

How Can We Find Safe Edges?

Theorem 23.1

Definitions

\(MST\) for a Connected Graph

Examples of a Cut

Theorem 23.1, to Recognize Safe Edges

Proof of Theorem 23.1

Proof of Theorem 23.1

Proof of Theorem 23.1

Proof of Theorem 23.1

Proof of Theorem 23.1

Corolary 23.2

Kruskal’s and Prim’s Algorithms

Kruskal

Kruskal’s Algorithm

Kruskal’s Example (1)

Kruskal’s Example (2)

Kruskal’s Example (3)

Kruskal’s Execution Time

Prim’s

Prim’s Algorithm

Prim’s Algorithm

Homework

Prim’s Example (1)

Prim’s Example (2)

Prim’s Example (3)

Prim’s Execution Time

Exercise