Minimum Spanning TreesProblem: Laying Telephone WireWiring: Naive ApproachWiring: Better ApproachMinimum-cost spanning treesMinimum Spanning Tree (MST)How Can We Generate a MST?Prim’s algorithmPrim-Jarnik’s AlgorithmExampleExample (contd.)Slide 13Slide 14Slide 15Slide 16Slide 17Prim’s Algorithm InvariantCorrectness of Prim’sSlide 20Slide 21Slide 22Another ApproachKruskal’s algorithmKruskal ExampleSlide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 381Minimum Spanning TreesLongin Jan LateckiTemple Universitybased on slides byDavid Matuszek, UPenn,Rose Hoberman, CMU,Bing Liu, U. of Illinois,Boting Yang, U. of Regina2Problem: Laying Telephone WireCentral office3Wiring: Naive ApproachCentral officeExpensive!4Wiring: Better ApproachCentral officeMinimize the total length of wire connecting the customers5Minimum-cost spanning treesSuppose you have a connected undirected graph with a weight (or cost) associated with each edgeThe cost of a spanning tree would be the sum of the costs of its edgesA minimum-cost spanning tree is a spanning tree that has the lowest costA BE DF C161921 113314181065A connected, undirected graphA BE DF C16111865A minimum-cost spanning tree6Minimum Spanning Tree (MST)it is a tree (i.e., it is acyclic)it covers all the vertices Vcontains |V| - 1 edgesthe total cost associated with tree edges is the minimum among all possible spanning treesnot necessarily uniqueA minimum spanning tree is a subgraph of an undirected weighted graph G, such that8How Can We Generate a MST? acedb24596455acedb245964559Prim’s algorithm T = a spanning tree containing a single node s;E = set of edges adjacent to s;while T does not contain all the nodes { remove an edge (v, w) of lowest cost from E if w is already in T then discard edge (v, w) else { add edge (v, w) and node w to T add to E the edges adjacent to w } }An edge of lowest cost can be found with a priority queueTesting for a cycle is automaticHence, Prim’s algorithm is far simpler to implement than Kruskal’s algorithm10Prim-Jarnik’s AlgorithmSimilar to Dijkstra’s algorithm (for a connected graph)We pick an arbitrary vertex s and we grow the MST as a cloud of vertices, starting from sWe store with each vertex v a label d(v) = the smallest weight of an edge connecting v to a vertex in the cloud At each step: We add to the cloud the vertex u outside the cloud with the smallest distance label We update the labels of the vertices adjacent to u11ExampleBDCAFE7428573980728BDCAFE74285739807257BDCAFE74285739807257BDCAFE74285739807254712Example (contd.)BDCAFE742857398032547BDCAFE74285739803254713Prim’s algorithmacedb24596455d b c a4 5 5 Vertex Parente -b ec ed eThe MST initially consists of the vertex e, and we updatethe distances and parent for its adjacent verticesVertex Parente -b -c -d -d b c a   e014Prim’s algorithmacedb24596455a c b2 4 5Vertex Parente -b ec dd ea dd b c a4 5 5 Vertex Parente -b ec ed e15Prim’s algorithmacedb24596455c b4 5Vertex Parente -b ec dd ea da c b2 4 5Vertex Parente -b ec dd ea d16Prim’s algorithmacedb24596455b5Vertex Parente -b ec dd ea dc b4 5Vertex Parente -b ec dd ea d17Prim’s algorithmVertex Parente -b ec dd ea dacedb24596455The final minimum spanning treeb5Vertex Parente -b ec dd ea d18Prim’s Algorithm InvariantAt each step, we add the edge (u,v) s.t. the weight of (u,v) is minimum among all edges where u is in the tree and v is not in the treeEach step maintains a minimum spanning tree of the vertices that have been included thus farWhen all vertices have been included, we have a MST for the graph!19Correctness of Prim’sThis algorithm adds n-1 edges without creating a cycle, so clearly it creates a spanning tree of any connected graph (you should be able to prove this). But is this a minimum spanning tree? Suppose it wasn't. There must be point at which it fails, and in particular there must a single edge whose insertion first prevented the spanning tree from being a minimum spanning tree.20Correctness of Prim’s•Let V' be the vertices incident with edges in S •Let T be a MST of G containing all edges in S, but not (x,y). •Let G be a connected, undirected graph•Let S be the set of edges chosen by Prim’s algorithm before choosing an errorful edge (x,y)xy21Correctness of Prim’sxyvw•There is exactly one edge on this cycle with exactly one vertex in V’, call this edge (v,w) •Edge (x,y) is not in T, so there must be a path in T from x to y since T is connected. •Inserting edge (x,y) into T will create a cycle22Correctness of Prim’sSince Prim’s chose (x,y) over (v,w), w(v,w) >= w(x,y). We could form a new spanning tree T’ by swapping (x,y) for (v,w) in T (prove this is a spanning tree). w(T’) is clearly no greater than w(T)But that means T’ is a MSTAnd yet it contains all the edges in S, and also (x,y) ...Contradiction23Another Approachacedb24596455•Create a forest of trees from the vertices•Repeatedly merge trees by adding “safe edges” until only one tree remains•A “safe edge” is an edge of minimum weight which does not create a cycleforest: {a}, {b}, {c}, {d}, {e}24Kruskal’s algorithm T = empty spanning tree;E = set of edges;N = number of nodes in graph; while T has fewer than N - 1 edges { remove an edge (v, w) of lowest cost from E if adding (v, w) to T would create a cycle then discard (v, w) else add (v, w) to T }Finding an edge of lowest cost can be done just by sorting the edgesEfficient testing for a cycle requires a fairly complex algorithm (UNION-FIND) which we don’t cover in this course25Kruskal ExampleJFKBOSMIAORDLAXDFWSFOBWIPVD86727041871258849144740139118494610901121234218466218021464123533726JFKBOSMIAO RDLAXD FWSFOBWIPVD867270418712588491447401391184946109011212342184662180214641235337Example27ExampleJFKBOSMIAO RDLAXD FWSFOBWIPVD86727041871258849144740139118494610901121234218466218021464123533728ExampleJFKBOSMIAO RDLAXD FWSFOBWIPVD86727041871258849144740139118494610901121234218466218021464123533729ExampleJFKBOSMIAORDLAXD FWSFOBWIPVD86727041871258849144740139118494610901121234218466218021464123533730ExampleJFKBOSMIAORDLAXD FWSFOBWIPVD86727041871258849144740139118494610901121234218466218021464123533731ExampleJFKBOSMIAORDLAXD FWSFOBWIPVD86727041871258849144740139118494610901121234218466218021464123533732ExampleJFKBOSMIAORDLAXD