{"id":524,"date":"2018-07-19T09:41:11","date_gmt":"2018-07-19T09:41:11","guid":{"rendered":"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=524"},"modified":"2018-12-12T12:25:14","modified_gmt":"2018-12-12T12:25:14","slug":"minimum-spanning-trees-kruskal-aigorithm","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/chapter\/minimum-spanning-trees-kruskal-aigorithm\/","title":{"rendered":"Minimum Spanning Trees- Kruskal AIgorithm"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n

Welcome to the e-PG Pathshala Lecture Series on Data Structures. We have understood the Minimum Spanning Trees. In this module we will discuss about Kruskal\u2019s Algorithm in detail.<\/p>\r\n \r\n\r\nLearning Objectives<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of the module are as follows:\r\n\r\n \r\n\r\n\u2022\u00a0 To understand in detail the Kruskal\u2019s Algorithm to find Minimum Spanning Trees\r\n\r\n\u2022\u00a0 To discuss implementation issues associated with Kruskal\u2019s Algorithm\r\n\r\n\u2022\u00a0 To understand Kruskal\u2019s Algorithm through a walkthrough example\r\n\r\n \r\n\r\n35.1\u00a0 Spanning Trees<\/strong>\r\n\r\n \r\n

This is a recap of Spanning trees and minimum spanning trees. When an undirected graph G is connected, a depth first or breadth first search starting at any vertex will visit all vertices in G. A spanning tree is any tree that consists solely of edges in G and that includes all the vertices. The edges of the graph E(G) is as below:<\/p>\r\n \r\n\r\nE(G): T (tree edges) + N (nontree edges) where\r\n\r\nT: set of edges used during search\r\n\r\nN: set of remaining edges\r\n\r\n \r\n

The Minimum Spanning Tree (MST) for a given graph is the Spanning Tree of minimum cost for that graph.<\/p>\r\n \r\n\r\n35.2\u00a0 Greedy Algorithms<\/strong>\r\n\r\n \r\n

Now let us make a simplifying assumption that all edge costs ce are distinct. With this assumption let us now define two properties namely Cut Property and Cycle Property (Figure 35.1).<\/p>\r\n \r\n

Cut property <\/strong>- Let S be any subset of nodes, and let e be the minimum cost edge with exactly one endpoint in S. Then the MST contains e.<\/p>\r\n \r\n

Cycle property - <\/strong>Let C be any cycle, and let f be the maximum cost edge belonging to C. Then the MST does not contain f.<\/p>\r\n\r\n<\/div>\r\n\"\"<\/strong>\r\n

\r\n

Figure 35.2 Kruskal\u2019s Algorithm<\/strong><\/p>\r\n \r\n\r\n35.2.1 Generic Algorithm for growing MST<\/strong>\r\n\r\n \r\n\r\nFirst we will examine the generic MST algorithm.\r\n\r\n \r\n\r\nGENERIC_MST(G,w)\r\n\r\n \r\n\r\n1. A:={} \/* (can be a forest or a single tree \u2013 see section 35.2.2 )\r\n\r\n2. while A does not form a spanning tree do\r\n\r\n3. find an edge (u,v) that is safe for A\r\n\r\n4. A:=A\u222a{(u,v)}\r\n\r\n5. return A\r\n\r\n \r\n

Set A is always a subset of some minimum spanning tree. This property is called the invariant Property. <\/strong>An edge (u,v) is a safe edge <\/strong>for A if adding the edge to A does not destroy the invariant property. A safe edge is<\/strong> just the CORRECT edge to choose to add.<\/p>\r\n \r\n\r\n35.2.2 Kruskal and Prim\u2019s Algorithms<\/strong>\r\n\r\n \r\n

Both Kruskal and Prim\u2019s algorithms are based on the generic algorithm. A specific rule to determine a safe edge is what diffrentiates the two algorithms. Set A is always a subset of some minimum spanning tree<\/p>\r\n \r\n

In Kruskal's algorithm, the set A is a forest. In this algorithm the safe edge added is always a least-weight edge in the graph that connects two distinct components.<\/p>\r\n \r\n

In Prim's algorithm, the set A forms a single tree .<\/strong> The safe edge added is always a least-weight edge connecting the tree to a vertex not in the tree.<\/p>\r\n \r\n

35.3 Kruskal Agorithm in detail<\/strong><\/p>\r\n \r\n

Now we will discuss the Kruskal algorithm in detail. Created in 1957 by Joseph Kruskal, it finds the MST by taking the smallest weight in the graph and connecting the two nodes and repeating until all nodes are connected to just one tree. This is done by creating a priority queue using the weights as keys . It creates a forest of trees. Initially the forest consists of n single node trees (and no edges). At each step, we add one edge (the cheapest one) so that it joins two trees together. If the edge would result in a cycle, it would simply link two nodes that were already part of a single connected tree, so that this edge would not be needed.<\/span><\/p>\r\n \r\n

35.3.1 Concept of Kruskal\u2019s Algorithm<\/strong><\/p>\r\n \r\n

Add the cheapest edge that joins disjoint components as in Fig 35.2. We we select (uv) since that is the cheapest edge, then we select (sb) since that is the next cheapest edge and so on. We do not select edges if they form a cycle a nd stop when all nodes are covered.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n

1.The forest is constructed with each node forming an independent tree. The edges are placed in a priority queue using the weights as keys.<\/p>\r\n

2.Until we have added n-1 edges,<\/p>\r\n \r\n

(a)\u00a0 Extract the cheapest edge from the queue,<\/p>\r\n

(b)\u00a0 If it forms a cycle, reject it,<\/p>\r\n

(c)\u00a0 Else add it to the forest. Adding it to the forest will join two trees together.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\nEvery step Joins - two trees in the forest together, so that at the end, there will only be one tree in T.\r\n\r\n \r\n

The reason the algorithm works is that each added edge is a connection between two sets of vertices, and since we select the edges in order of weight, we are always selecting the minimum edge weight that connects the two sets of vertices.<\/p>\r\n \r\n\r\n35.3.2 Cycle detection<\/strong>\r\n\r\n \r\n\r\nOne important part of Kruskal\u2019s algorithm is the cycle detection. Here the steps are as follows:\r\n\r\n \r\n\r\nKeep track of disjoint sets.\r\n\r\n \r\n