Question? Leave a message!




Kruskal’s algorithm

Kruskal’s algorithm
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
Comment
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 © 2006-2013 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 sub-graphsKruskal’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/parker-brothers/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/parker-brothers/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/parker-brothers/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 sub-trees 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, F