Page 1 Analysis of Algorithms CS 477/677 Minimum Spanning Trees (MST) Instructor: George Bebis Chapter 23 Page 2 Analysis of Algorithms CS 477/677 Minimum Spanning Trees (MST) Instructor: George Bebis Chapter 23 2 Minimum Spanning Trees • Spanning Tree – A tree (i.e., connected, acyclic graph) which contains all the vertices of the graph • Minimum Spanning Tree – Spanning tree with the minimum sum of weights • Spanning forest – If a graph is not connected, then there is a spanning tree for each connected component of the graph a b c d e g g f i 4 8 7 8 11 1 2 7 2 4 14 9 10 6 Page 3 Analysis of Algorithms CS 477/677 Minimum Spanning Trees (MST) Instructor: George Bebis Chapter 23 2 Minimum Spanning Trees • Spanning Tree – A tree (i.e., connected, acyclic graph) which contains all the vertices of the graph • Minimum Spanning Tree – Spanning tree with the minimum sum of weights • Spanning forest – If a graph is not connected, then there is a spanning tree for each connected component of the graph a b c d e g g f i 4 8 7 8 11 1 2 7 2 4 14 9 10 6 3 Applications of MST – Find the least expensive way to connect a set of cities, terminals, computers, etc. Page 4 Analysis of Algorithms CS 477/677 Minimum Spanning Trees (MST) Instructor: George Bebis Chapter 23 2 Minimum Spanning Trees • Spanning Tree – A tree (i.e., connected, acyclic graph) which contains all the vertices of the graph • Minimum Spanning Tree – Spanning tree with the minimum sum of weights • Spanning forest – If a graph is not connected, then there is a spanning tree for each connected component of the graph a b c d e g g f i 4 8 7 8 11 1 2 7 2 4 14 9 10 6 3 Applications of MST – Find the least expensive way to connect a set of cities, terminals, computers, etc. 4 Example Problem • A town has a set of houses and a set of roads • A road connects 2 and only 2 houses • A road connecting houses u and v has a repair cost w(u, v) Goal: Repair enough (and no more) roads such that: 1. Everyone stays connected i.e., can reach every house from all other houses 2. Total repair cost is minimum a b c d e h g f i 4 8 7 8 11 1 2 7 2 4 14 9 10 6 Page 5 Analysis of Algorithms CS 477/677 Minimum Spanning Trees (MST) Instructor: George Bebis Chapter 23 2 Minimum Spanning Trees • Spanning Tree – A tree (i.e., connected, acyclic graph) which contains all the vertices of the graph • Minimum Spanning Tree – Spanning tree with the minimum sum of weights • Spanning forest – If a graph is not connected, then there is a spanning tree for each connected component of the graph a b c d e g g f i 4 8 7 8 11 1 2 7 2 4 14 9 10 6 3 Applications of MST – Find the least expensive way to connect a set of cities, terminals, computers, etc. 4 Example Problem • A town has a set of houses and a set of roads • A road connects 2 and only 2 houses • A road connecting houses u and v has a repair cost w(u, v) Goal: Repair enough (and no more) roads such that: 1. Everyone stays connected i.e., can reach every house from all other houses 2. Total repair cost is minimum a b c d e h g f i 4 8 7 8 11 1 2 7 2 4 14 9 10 6 5 Minimum Spanning Trees • A connected, undirected graph: – Vertices = houses, Edges = roads • A weight w(u, v) on each edge (u, v) ? E a b c d e h g f i 4 8 7 8 11 1 2 7 2 4 14 9 10 6 Find T ? E such that: 1. T connects all vertices 2. w(T) = S (u,v) ?T w(u, v) is minimizedRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!