Question? Leave a message!




Kruskal’s algorithm

Kruskal’s algorithm
ECE 250 Algorithms and Data Structures Kruskal’s Douglas Wilhelm Harder, M.Math. LEL algorithm Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Kruskal’salgorithm 2 Outline This topic covers Kruskal’s algorithm: – Finding a minimum spanning tree – The idea and the algorithm – An example – Using a disjoint set data structureKruskal’salgorithm 3 Kruskal’s Algorithm Kruskal’s algorithm sorts the edges by weight and goes through the edges from least weight to greatest weight adding the edges to an empty graph so long as the addition does not create a cycle The halting point is: – When V – 1 edges have been added • In this case we have a minimum spanning tree – We have gone through all edges, in which case, we have a forest of minimum spanning trees on all connected subgraphsKruskal’salgorithm 4 Example Consider the game of Risk from Parker Brothers – A game of world domination – The world is divided into 42 connected regions http://thunderbird37.com/tag/parkerbrothers/Kruskal’salgorithm 5 Example Consider the game of Risk from Parker Brothers – A game of world domination – The world is divided into 42 connected regions – The regions are vertices and edges indicate adjacent regions http://thunderbird37.com/tag/parkerbrothers/Kruskal’salgorithm 6 Example Consider the game of Risk from Parker Brothers – A game of world domination – The world is divided into 42 connected regions – The regions are vertices and edges indicate adjacent regions – The graph is sufficient to describe the gameKruskal’salgorithm 7 Example Consider the game of Risk from Parker Brothers – Here is a more abstract representation of the game board – Suddenly, it’s less interesting: “I’ve conquered the graph”Kruskal’salgorithm 8 Example We’ll focus on Asia http://thunderbird37.com/tag/parkerbrothers/Kruskal’salgorithm 9 Example Here is our abstract representationKruskal’salgorithm 10 Example Let us give a weight to each of the edgesKruskal’salgorithm 11 C, E Example H, I G, I F, G First, we sort the edges based on weight B, E E, H B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 12 C, E Example H, I G, I F, G We start by adding edge C, E B, E E, H B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 13 C, E Example H, I G, I F, G We add edge H, I B, E E, H B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 14 C, E Example H, I G, I F, G We add edge G, I B, E E, H B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 15 C, E Example H, I G, I F, G We add edge F, G B, E E, H B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 16 C, E Example H, I G, I F, G We add edge B, E B, E E, H B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 17 C, E Example H, I G, I F, G We add edge E, H B, E – This coalesces the two spanning subtrees into one E, H B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 18 C, E Example H, I G, I F, G We try adding B, C, but it creates a cycle B, E E, H B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 19 C, E Example H, I G, I F, G We add edge H, K B, E E, H B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 20 C, E Example H, I G, I F, G We add edge H, L B, E E, H B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 21 C, E Example H, I G, I F, G We add edge D, E B, E E, H B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 22 C, E Example H, I G, I F, G We try adding G, H, but it creates a cycle B, E E, H B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 23 C, E Example H, I G, I F, G We try adding I, K, but it creates a cycle B, E E, H B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 24 C, E Example H, I G, I F, G We try adding B, D, but it creates a cycle B, E E, H B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 25 C, E Example H, I G, I F, G We try adding D, F, but it creates a cycle B, E E, H B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 26 C, E Example H, I G, I F, G We try adding E, G, but it creates a cycle B, E E, H B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 27 C, E Example H, I G, I F, G By observation, we can still add edges J, K and A, B B, E E, H B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 28 C, E Example H, I G, I F, G Having added A, B, we now have 11 edges B, E – We terminate the loop E, H – We have our minimum spanning tree B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 29 Analysis Implementation – We would store the edges and their weights in an array – We would sort the edges using either quicksort or some distribution sort – To determine if a cycle is created, we could perform a traversal • A runtime of O(V) – Consequently, the runtime would be O(E ln(E) + E·V) 2 2 – However, E = O(V ), so ln(E) = O(ln(V )) = O(2 ln(V)) = O(ln(V)) – Consequently, the runtime would be O(E ln(V) + EV) = O(E·V) The critical operation is determining if two vertices are connectedKruskal’salgorithm 30 Analysis Instead, we could use disjoint sets – Consider edges in the same connected subgraph as forming a set B, C, E, F, G, H, IKruskal’salgorithm 31 Analysis Instead, we could use disjoint sets – Consider edges in the same connected subgraph as forming a set – If the vertices of the next edge are in different sets, take the union of the two sets Add edge (E, H) B, C, E, F, G, H, IKruskal’salgorithm 32 Analysis Instead, we could use disjoint sets – Consider edges in the same connected subgraph as forming a set – If the vertices of the next edge are in different sets, take the union of the two sets Add edge (E, H) B, C, E, F, G, H, I B, C, E, F, G, H, IKruskal’salgorithm 33 Analysis Instead, we could use disjoint sets – Consider edges in the same connected subgraph as forming a set – If the vertices of the next edge are in different sets, take the union of the two sets – Do not add an edge if both vertices are in the same set Add edge (E, H) B, C, E, F, G, H, I B, C, E, F, G, H, IKruskal’salgorithm 34 Analysis The disjoint set data structure has the following average runtimes: – Checking if two vertices are in the same set is Q(a(V)) – Taking the union of two disjoint sets is Q(a(V)) – For all possible sizes of V, a(V) = Q(1)Kruskal’salgorithm 35 Analysis Thus, checking and building the minimum spanning tree is now O(E) The dominant time is now the time required to sort the edges: – Using quicksort, the runtime is O(E ln(E)) = O(E ln(V)) – If there is an efficient Q(E) sorting algorithm, the runtime is then Q(E)Kruskal’salgorithm 36 Example Going through the example again with disjoint setsKruskal’salgorithm 37 C, E Example H, I G, I F, G We start with twelve singletons B, E E, H A, B, C, D, E, F, G, H, I, J, K, L B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 38 C, E Example H, I G, I F, G We start by adding edge C, E B, E E, H A, B, C, E, D, F, G, H, I, J, K, L B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 39 C, E Example H, I G, I F, G We add edge H, I B, E E, H A, B, C, E, D, F, G, H, I, J, K, L B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 40 C, E Example H, I G, I F, G Similarly, we add G, I, F, G, B, E B, E E, H A, B, C, E, D, F, G, H, I, J, K, L B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 41 C, E Example H, I G, I F, G The vertices of E, H are in different sets B, E E, H A, B, C, E, D, F, G, H, I, J, K, L B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 42 C, E Example H, I G, I F, G Adding edge E, H creates a larger union B, E E, H A, B, C, E, F, G, H, I, D, J, K, L B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 43 C, E Example H, I G, I F, G We try adding B, C, but it creates a cycle B, E E, H A, B, C, E, F, G, H, I, D, J, K, L B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 44 C, E Example H, I G, I F, G We add edge H, K, H, L and D, E B, E E, H A, B, C, D, E, F, G, H, I, K, L, J B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 45 C, E Example H, I G, I F, G Both G and H are in the same set B, E E, H A, B, C, D, E, F, G, H, I, K, L, J B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 46 C, E Example H, I G, I F, G Both I, K are in the same set B, E E, H A, B, C, D, E, F, G, H, I, K, L, J B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 47 C, E Example H, I G, I F, G Both B, D are in the same set B, E E, H A, B, C, D, E, F, G, H, I, K, L, J B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 48 C, E Example H, I G, I F, G Both D, F are in the same set B, E E, H A, B, C, D, E, F, G, H, I, K, L, J B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 49 C, E Example H, I G, I F, G We end when there is only one set, having added (A, B) B, E E, H A, B, C, D, E, F, G, H, I, K, L, J B, C H, K H, L D, E G, H I, K B, D D, F E, G K, L J, K J, I J, G A, B A, D E, FKruskal’salgorithm 50 Summary This topic has covered Kruskal’s algorithm – Sort the edges by weight – Create a disjoint set of the vertices – Begin adding the edges onebyone checking to ensure no cycles are introduced – The result is a minimum spanning tree – The run time is O(E ln(V)Kruskal’salgorithm 51 References Wikipedia, http://en.wikipedia.org/wiki/Minimumspanningtree Wikipedia, http://en.wikipedia.org/wiki/Kruskal’salgorithm These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
Website URL
Comment