Week 3: Minimum Spanning Trees e Definition of mst Generic Mst algorithm Kruskal's algorithm Prim's algorithm
1 Week 3: Minimum Spanning Trees •Definition of MST •Generic MST algorithm •Kruskal's algorithm •Prim's algorithm
Problem: Laying Telephone Wire Central office
2 Problem: Laying Telephone Wire Central office
Wiring: Naive Approach 可 Central office Expensive
3 Wiring: Naïve Approach Central office Expensive!
Wiring: Better Approach 可 Central office Minimize the total length of wire connecting the customers
4 Wiring: Better Approach Central office Minimize the total length of wire connecting the customers
Definition of mst Input: connected, and undirected Graph G=V,E) Each edge (u, v)in e carries a weight w(u, v) Also referred to as cost (length of edge) to connect u and v Output: a subset Tof e that connects all of the vertices in V and whose total weight is minimized Since the total weight is minimized the subset T must be acyclic(no circuit Thus, T'is a tree. We call it a spanning tree The problem of determining the tree t is called the minimum-spanning-tree problem
5 Definition of MST • Input: connected, and undirected Graph G=(V,E) – Each edge (u,v) in E carries a weight w(u,v) • Also referred to as cost (length of edge) to connect u and v. • Output: A subset T of E that connects all of the vertices in V and whose total weight is minimized. • Since the total weight is minimized, the subset T must be acyclic (no circuit). – Thus, T is a tree. We call it a spanning tree. • The problem of determining the tree T is called the minimum-spanning-tree problem