Minimum Spanning Trees

Introduction

Given a connected graph G = (V, E) with real-valued edge weights (costs) ce, an MST is a subset of the edges T ??? E such that T is a spanning tree (contains all nodes of G) whose sum of edge weights is minimized.

Use

Network design, telephone, electrical, hydraulic, TV cable, computer, road

A Generic MST Algorithm: GENERIC-MST(G) A = null while A does not form a spanning tree Find an edge (u, v) that is a safe choice A = A U {(u, v)} return A