{"id":507,"date":"2018-07-19T09:19:18","date_gmt":"2018-07-19T09:19:18","guid":{"rendered":"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=507"},"modified":"2018-12-12T12:23:52","modified_gmt":"2018-12-12T12:23:52","slug":"minimum-spanning-trees-i","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/chapter\/minimum-spanning-trees-i\/","title":{"rendered":"Minimum Spanning Trees-I"},"content":{"raw":"<div><span style=\"float: right\"><a href=\"https:\/\/youtu.be\/T_0SjGCONqg\" target=\"_blank\" rel=\"noopener\"><img src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a>\r\n<\/span><\/div>\r\n<div>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Welcome to the e-PG Pathshala Lecture Series on Data Structures. We have understood the Graph ADT and Graph Traversals BFS and DFS. In this module we will discuss about Minimum Spanning Trees.<\/p>\r\n&nbsp;\r\n\r\n<strong>Learning Objectives<\/strong>\r\n\r\n&nbsp;\r\n\r\nThe learning objectives of the module are as follows:\r\n\r\n&nbsp;\r\n\r\n\u2022\u00a0 To understand the concept of Spanning Trees\r\n\r\n\u2022\u00a0 To discuss Minimum Spanning Trees and its properties\r\n\r\n\u2022\u00a0 To explain the Greedy approach to finding Minimum Spanning Trees\r\n\r\n&nbsp;\r\n\r\n<strong>34.1\u00a0 Spanning Trees<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Suppose you have a connected undirected graph. As you can recall connected means every node is reachable from every other node and undirected means edges of the graph do not have an associated direction. A spanning tree of the graph is a connected sub-graph in which there are no cycles .<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">A spanning tree of a graph is just a sub-graph that contains all the vertices and is a tree. A graph may have many spanning trees. Spanning trees of the complete graph with 4 vertices is given in Figure 34.1. A spanning tree has the fewest number of edges possible while still retaining a connection between all the vertices in the component. If the component contains <em>n<\/em> vertices, the spanning tree contains <em>n<\/em> \u2013 1 edges. When you traverse all the vertices of an undirected graph, you generate a spanning forest.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">To find a spanning tree of a graph, we must pick an initial node and call it part of the spanning tree. Then we do a search (either BFS or DFS) from the initial node and each time you find a node that is not in the spanning tree, add both the new node <em>and <\/em>the edge you followed to get to it to the spanning tree<\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"alignnone size-full wp-image-510 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-328.png\" alt=\"\" width=\"513\" height=\"282\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong>34.2 Minimum Spanning Trees<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">In a weighted graph, the weight of a sub -graph is the sum of the weights of the edges in the sub-graph. A minimum spanning tree (MST) for a weighted undirected graph is a spanning tree with minimum weight.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">The Minimum Spanning Tree for a given graph is the Spanning Tree of minimum cost for that graph as shown below:<\/p>\r\n<img class=\"alignnone size-full wp-image-511 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-329.png\" alt=\"\" width=\"493\" height=\"196\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong>4.3 Creating a Spanning Tree<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Either DFS or BFS can be used to create a spanning tree. When DFS is used, the resulting spanning tree is known as a depth first spanning tree. When BFS is used, the resulting spanning tree is known as a breadth first spanning tree. Adding a non-tree edge into any spanning tree, will create a cycle.<\/p>\r\n&nbsp;\r\n\r\n\u2022\u00a0 Assume you have an undirected graph, G = (V,E)\r\n\r\n\u2022\u00a0 \u00a0Spanning tree of graph G is tree\r\n\r\n&nbsp;\r\n\r\nT\u00a0 = (V,E<sub>T<\/sub> <strong>\u00cd<\/strong> E)\r\n<ul>\r\n \t<li>Tree has same set of nodes<\/li>\r\n \t<li>\u00a0All tree edges are graph edges<\/li>\r\n<\/ul>\r\n<\/div>\r\n<div>\r\n<p style=\"text-align: justify\">For a given tree T in a graph G, the edges and vertices of T are called tree edges and tree vertices, and the edges and vertices of G that are not in T are called non-tree edges and non-tree vertices.<\/p>\r\n&nbsp;\r\n\r\nE(G):T(tree edges) + N(nontree edges)\r\n\r\nwhere T is the set of edges E<sub>T<\/sub> used during search and N is the set of remaining edges\r\n\r\n&nbsp;\r\n\r\n<strong>34.4 Properties of Spanning Trees<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>34.4.1 Property 1 of Spanning Trees<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Given a graph G = (V,E), and spanning tree: T = (V,E T) the property states that for any edge c in G but not in T, there is a simple cycle containing only edge c and edges in spanning tree. This is shown in Figure 34.3.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-512 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-330.png\" alt=\"\" width=\"517\" height=\"199\" \/>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n<strong>34.4.2 Property 2 of Spanning Tree<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Given a graph G = (V,E), and spanning tree: T = (V,E <sub>T<\/sub>) the property states that for any edge c in G but not in T, there is a simple cycle Y containing only edge c and edges in spanning tree. Moreover, inserting edge c into T and deleting any edge in Y gives another spanning tree T\u2019 (Figure 34.4).<\/p>\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-513 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-331.png\" alt=\"\" width=\"529\" height=\"187\" \/>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n<strong>34.5 Building BFS\/DFS Spanning Trees<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Before we build the spanning tree let us define the concept of frontier edge. A frontier edge for a given tree T in a graph is a non-tree edge with one endpoint in T, called its tree endpoint, and one endpoint not in T, its non-tree endpoint.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Let T be a tree subgraph of a graph G, and let S be the set of frontier edges for T. The function nextEdge(G,S) chooses and returns as its value the frontier edge in S\u00a0<span style=\"font-size: 1em;text-align: initial\">that is to be added to tree T. After a frontier edge is added to the current tree, the procedure updateFrontier(G,S) removes from S those edges that are no longer frontier edges and adds to S those that have become frontier edges. Figure 34.5 gives a generic tree growing algorithm.<\/span><\/p>\r\n\r\n<\/div>\r\n<div>\r\n<table style=\"border-collapse: collapse;width: 100%\" border=\"1\">\r\n<tbody>\r\n<tr>\r\n<td style=\"width: 100%\"><strong>Algorithm: Tree-Growing(G, v)<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>Input: a connected graph G, a starting vertex v \u20ac V<\/strong><strong>G<\/strong><strong>, and a selection-function nextEdge.<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>Output: an ordered spanning tree T of G with root v.<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>Initialize tree T as vertex v.<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>Initialize S as the set of proper edges incident on v.<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>While S \u2260 <\/strong><strong>f<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>Let e = nextEdge(G, S).<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>Let w be the non-tree endpoint of edge e.<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>Add edge e and vertex w to tree T.<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>updateFrontier(G,S).<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>Return tree T.<\/strong><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n&nbsp;\r\n<p style=\"text-align: center\"><strong>Figure 34.5 Generic Tree Growing Algorithm <\/strong><\/p>\r\n&nbsp;\r\n\r\n<strong>35.5.1 BFS and DFS as Tree-Growing<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The depth-first and breadth-first searches use opposite versions of nextEdge. The nextEdge version of breadth first search selects a frontier edge whose tree endpoint was discovered earliest (least recently). The nextEdge version of depth first search selects a frontier edge whose tree endpoint have been most recently discovered. Let us consider the example shown in Figure 34.6.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-514 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-332.png\" alt=\"\" width=\"637\" height=\"271\" \/>\r\n\r\n<\/div>\r\nN<span style=\"text-align: initial;font-size: 1em\">ow the graph is shown and we first create the spanning tree using Breadth First search.<\/span>\r\n<div>\r\n\r\n&nbsp;\r\n\r\n<strong>34.5.1 Example: BFS for Spanning Tree Construction<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">BFS uses the queue data structure for maintaining the yet to be discovered edges. Initially the edge from dummy node to A is inserted in the queue. Now since this is the only entry in the queue it is deleted and output as (dummy,A). Now we get all edges from A <strong>[(A,B),(A,G),(A,F)]<\/strong> are added to the queue as shown below and its destination nodes B,G,F are marked as done. These edges are added to the spanning tree. Now the first edge (A,B) from the queue is deleted and edges emanating from B [(B,C)] is inserted at the back of the queue but only if the destination node of edge C is not already done, and edge (B,G) is not added to the queue or the spanning tree. Edge <strong>(B,C)<\/strong> is added to the spanning tree. Now we again delete the edge from the front of the queue (A,G) and add the edges emanating from G [<strong>(G,I),(G,H)<\/strong>] to the queue if the condition explained before is satisfied. These edges are also added to the spanning tree. Note that edge (G,B) is not inserted into the queue since node B has already been processed. Next the edge (A,F) is deleted from the queue and edges emanating from F and satisfying the condition discussed above ( here<strong>(F,E)<\/strong>) is inserted at the back of the queue and added to the spanning .tree. Next edge (B,C) is deleted and edges from C here <strong>(C,D)<\/strong> is marked as done and added to the spanning tree. Now we have covered all the nodes of the graph and the process is complete.<\/p>\r\n\r\n<table style=\"border-collapse: collapse;width: 100%\" border=\"1\">\r\n<tbody>\r\n<tr>\r\n<td style=\"width: 100%\">[(dummy,A)]\r\n\r\n[(A,B),(A,G),(A,F)]\r\n\r\n[(A,G),(A,F),(B,C)]\u2026..\r\n\r\n[(A,F), (B,C), (G,I),(G,H)]\r\n\r\n[(B,C), (G,I),(G,H), (F,E)]\r\n\r\n[(G,I),(G,H),(F,E), (C,D)]\u2026\u2026<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n&nbsp;\r\n<p style=\"text-align: center\"><strong>34.5.2 Example: DFS for Spanning Tree Construction<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">DFS uses the stack data structure and the details are shown below. Here edges are added to stack if edge is not marked or destination node of the edge not marked (Figure 34.7). Initially we start from A and push all edges of A (AB,AF,AG) onto stack and mark A. Now we pop top edge from stack <strong>(AG)<\/strong>, mark edge AG and node G and push all edges of G onto stack if the destination node of the edge is not already marked (GB,GH,GI), note GA is not added since it is marked. Now we pop top edge from stack <strong>(GI)<\/strong>, mark node I and add edges of I (IF, IH, IE) to stack. Now note that IG is not added since it is already marked. Now we pop top edge from stack <strong>(IE)<\/strong>, mark node E and add edges of E (ED, EF) to stack. Now note that EI is not added since it is already marked. Now we pop top edge from stack <strong>(EF)<\/strong>, mark node F and add no edges to stack since destination nodes of edges (FA,FI) are marked and\u00a0<span style=\"text-align: initial;font-size: 1em\">edge FE is marked. Now we pop top edge from stack <\/span><strong style=\"text-align: initial;font-size: 1em\">(ED)<\/strong><span style=\"text-align: initial;font-size: 1em\">, mark node D and add edges of D (DC, DH) to stack. Now note that DE is not added since it is already marked. Now we pop top edge from stack <\/span><strong style=\"text-align: initial;font-size: 1em\">(DH)<\/strong><span style=\"text-align: initial;font-size: 1em\">, mark node H and add edge of H (HC) to stack. Now note that the edge HD is not added to stack since the edge is marked and edges (HG, HI) since their destination nodes are marked. Now we pop top edge from stack <\/span><strong style=\"text-align: initial;font-size: 1em\">(HC)<\/strong><span style=\"text-align: initial;font-size: 1em\">, mark node C and add edge (CB) to stack. Now note that the edges (CH, CB) are not added to stack since the edge are marked and edge CD is not added since its destination node is marked. Now we pop top edge from stack <\/span><strong style=\"text-align: initial;font-size: 1em\">(CB)<\/strong><span style=\"text-align: initial;font-size: 1em\">, mark node B and no more edges to stack since all nodes in the graph have been marked. The process is now complete.<\/span><\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"alignnone size-full wp-image-515 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-333.png\" alt=\"\" width=\"650\" height=\"436\" \/>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n<strong>34.6 Weighted Spanning Trees<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Now let us assume that we have an undirected graph G = (V,E) with weights on each edge. The Spanning tree of graph G is a tree T = (V,E<sub>T<\/sub> <span style=\"text-decoration: underline\">c<\/span> E).<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">The tree has same set of nodes, all tree edges are graph edges and weight of spanning tree = sum of tree edge weights .<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">A Minimal Spanning Tree (MST) is any spanning tree whose weight is minimal. In general, a graph has several MST\u2019s. There are many applications of circuit-board routing, networking, etc. The MST is acyclic because it is a tree. It is <strong><em>spanning<\/em><\/strong> because it covers every vertex and it is <strong><em>minimum<\/em><\/strong> because it has minimum cost.<\/p>\r\n&nbsp;\r\n\r\n<strong>34.6.1 Minimum Spanning Tree<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">If we wish we can have an MST start at a specific node. However, if there are weighted edges and all weighted edges are unique (if all edges have distinct\u00a0<span style=\"text-align: initial;font-size: 1em\">weights), only one MST will exist. In a weighted graph, you can sum the weights for all edges in a spanning tree and attempt to find a spanning tree that minimizes this sum. A generic MST algorithm maintains an acyclic subgraph F of the input graph G. F is a subgraph of the minimum spanning tree of G, and we can use several algorithms for finding a <\/span><strong style=\"text-align: initial;font-size: 1em\">minimum spanning tree<\/strong><span style=\"text-align: initial;font-size: 1em\"> for a component. Repeated application to all the components in a graph yields a <\/span><strong style=\"text-align: initial;font-size: 1em\">minimum spanning forest.<\/strong><\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"alignnone size-full wp-image-516 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-334.png\" alt=\"\" width=\"411\" height=\"281\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong>36.2 Real Life Applications of MST<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The standard application is to a problem like phone network design. You have a business with several offices; you want to lease phone lines to connect them up with each other; and the phone company charges different amounts of money to connect different pairs of cities. You want a set of lines that connects all your offices with a minimum total cost. It should be a spanning tree, since if a network isn\u2019t a tree you can always remove some edges and save If it is constrained to bury the cable only along certain paths, then there would be a graph representing which nodes(cities) are connected by those paths. Some of those paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weights. A <em>minimum spanning tree<\/em> would be the network with the lowest total cost as given above (Figure 34.8).<\/p>\r\n<img class=\"size-full wp-image-517 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-335.png\" alt=\"\" width=\"411\" height=\"281\" \/>\r\n\r\n<\/div>\r\n<p style=\"text-align: justify\">36.2 Real Life Applications of MST The standard application is to a problem like phone network design. You have a business with several offices; you want to lease phone lines to connect them up with each other; and the phone company charges different amounts of money to connect different pairs of cities. You want a set of lines that connects all your offices with a minimum total cost. It should be a spanning tree, since if a network isn\u2019t a tree you can always remove some edges and save If it is constrained to bury the cable only along certain paths, then there would be a graph representing which nodes(cities) are connected by those paths. Some of those paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weights. A minimum spanning tree would be the network with the lowest total cost as given above (Figure 34.8).<\/p>\r\n<strong>\u00a0<\/strong>\r\n\r\n<img class=\"alignnone size-full wp-image-518 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-336.png\" alt=\"\" width=\"563\" height=\"284\" \/>\r\n<div>\r\n<p style=\"text-align: justify\">Another example could be the determination of how an airline can service all cities, while minimizing the total length of the routes it needs to support . In a weighted, undirected graph, it is a tree formed by connecting all of the vertices with minimal cost (Fig 34.9).<\/p>\r\n&nbsp;\r\n\r\n<strong>36.3<\/strong>\u00a0<strong>Single Source Shortest Path (SSSP) tree<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">This tree is constructed the input is a single source vertex in a weighted, directed graph and the job is to compute a shortest path for each possible destination. This is similar to BFS. Thus for a weighted graph <em>G = (V,E,w)<\/em>, the <em>single -source shortest<\/em> <em>paths <\/em>problem is to find the shortest paths from a vertex<em> w <\/em><em>\u2208<\/em><em> V <\/em>to all other vertices in\u00a0<em>V<\/em>. The Single Source Shortest Path (SSSP) has a given fixed start node. However in MST at any point in construction, we have a bunch of nodes that we have reached, and we look at the shortest distance from any one of those nodes to a new node (Figure 34.10).<\/p>\r\n\r\n<\/div>\r\n<img class=\"alignnone size-full wp-image-519 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-337.png\" alt=\"\" width=\"313\" height=\"270\" \/>\r\n<div>\r\n\r\n&nbsp;\r\n\r\n<strong>34.6.4 Property 3 of Minimal Spanning Trees<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Given the Graph: G = (V,E) and the Spanning tree: T = (V,E T). For any edge: c in G but not in T, there is a simple cycle Y containing only edge c and edges in spanning tree (already proved). Moreover, weight of c must be greater than or equal to weight of any edge in this cycle as given in Figure 34.11.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-520 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-338.png\" alt=\"\" width=\"555\" height=\"218\" \/>\r\n\r\n<\/div>\r\n<strong>\u00a0<\/strong><strong style=\"text-align: initial;font-size: 1em\">\u00a0 \u00a0 34.7 MST algorithms<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong style=\"text-align: initial;font-size: 1em\">34.7.1 Bor\u016fvka\u2019s Algorithm<\/strong>\r\n<div>\r\n<p style=\"text-align: justify\">The first MST Algorithm was created by Otakar Bor\u016fvka in 1926. The algorithm was used to create efficient connections between the electricity network in the Czech Republic. This algorithm is no longer used after Prim\u2019s and Kruskal\u2019s algorithms were discovered.<\/p>\r\n&nbsp;\r\n\r\n<strong>34.7.2 Greedy Algorithms for MST<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Let us first understand what is meant by a greedy approach. Greedy algorithms apply to problems with O<em>ptimal substructures<\/em> where optimal solutions contain optimal sub-solutions or has the <em>greedy choice property<\/em> where an optimal solution can be obtained by making the greedy choice at each step. Here we discuss the <strong>greedy-choice property <\/strong>whe<strong>re <\/strong>a globally optimal solution can be arrived at by making a locally optimal (greedy) choice.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">A <strong><em>greedy algorithm<\/em><\/strong> always makes the choice for a locally optimal solution which seems the best at the current moment with the hope of arriving at a globally optimal solution. This approach efficiently computes a solution, works well for a wide range of problems, such as minimum-spanning-tree algorithms, Dijkstra's algorithm for shortest paths from a single source, etc. Greedy algorithms construct a solution to an optimization problem piece by piece through a sequence of choices that are feasible, locally optimal and irrevocable. The greedy approach to MST is an optimization problem where we need to find minimum cost for connecting all vertices. Let us understand the greedy approach (Figure 34.12). Let us assume that we have a set of disjoint components (initially nodes). Now we need to add the cheapest edge that joins disjoint components We first start with node 1, and then choose the edge (1,2) since it is the cheapest edge associated with 1 and does not form a cycle. Now from 2, we choose edge (2,6) the cheapest edge from 2 without counting edge (2,1) (which will result in a cycle). Next we choose (6,3) and then (3,5) and finally (6,4) until we exhaust all the vertices.<\/p>\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-521 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-339.png\" alt=\"\" width=\"542\" height=\"256\" \/>\r\n\r\n&nbsp;\r\n\r\nBoth MST algorithms Kruskal, and Prim, determine an edge to be added to form the MST.\r\n\r\n&nbsp;\r\n\r\n<strong>34.7.2.1<\/strong>\u00a0<strong>Greedy Algorithm 1 \u2013 Kruskal\u2019s Algorithm<\/strong>\r\n\r\n<\/div>\r\n<p style=\"text-align: justify\">Kruskal\u2019s algorithm grows a tree by repeatedly adding the least cost edge that does not introduce a cycle among the edges included so far. The intermediary solution is a spanning forest. Here we add the cheapest edges that join disjoint components . The Kruskal\u2019s algorithm will be discussed in detail in Module 35.<\/p>\r\n&nbsp;\r\n\r\n<strong>34.7.2.2 Greedy Algorithm 2 - Prim\u2019s Algorithm<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Prim\u2019s algorithm grows a single tree by repeatedly adding the least cost edge that connects a vertex in the existing tree to a vertex not in the existing tree . The intermediary solution is a sub-tree. Here we extend the tree by including the cheapest outgoing edge. The Prim\u2019s algorithm will be discussed in detail in Module 36.<\/p>\r\n&nbsp;\r\n\r\n<strong>34.7.3 Why do the Greedy Algorithms work?<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">For simplicity, assume all edge costs are distinct. Let S be a subset of V, and suppose e = (u, v) is the minimum cost edge of E, with u in S and v in V-S and e is in every minimum spanning tree.<\/p>\r\n&nbsp;\r\n\r\n<strong>Summary<\/strong>\r\n<ul>\r\n \t<li>Understood the concept of Spanning Trees<\/li>\r\n \t<li>Discussed Minimum Spanning Trees and its properties<\/li>\r\n \t<li>Explained the Greedy approach to finding Minimum Spanning Trees<\/li>\r\n<\/ul>\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><strong>you can view video on Minimum Spanning Trees-I<\/strong><\/td>\r\n<td><a href=\"https:\/\/youtu.be\/T_0SjGCONqg\" target=\"_blank\" rel=\"noopener\"><img class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n\r\n<img class=\"size-full wp-image-522 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-340.png\" alt=\"\" width=\"662\" height=\"539\" \/>","rendered":"<div><span style=\"float: right\"><a href=\"https:\/\/youtu.be\/T_0SjGCONqg\" target=\"_blank\" rel=\"noopener\"><img decoding=\"async\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a><br \/>\n<\/span><\/div>\n<div>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Welcome to the e-PG Pathshala Lecture Series on Data Structures. We have understood the Graph ADT and Graph Traversals BFS and DFS. In this module we will discuss about Minimum Spanning Trees.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Learning Objectives<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>The learning objectives of the module are as follows:<\/p>\n<p>&nbsp;<\/p>\n<p>\u2022\u00a0 To understand the concept of Spanning Trees<\/p>\n<p>\u2022\u00a0 To discuss Minimum Spanning Trees and its properties<\/p>\n<p>\u2022\u00a0 To explain the Greedy approach to finding Minimum Spanning Trees<\/p>\n<p>&nbsp;<\/p>\n<p><strong>34.1\u00a0 Spanning Trees<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Suppose you have a connected undirected graph. As you can recall connected means every node is reachable from every other node and undirected means edges of the graph do not have an associated direction. A spanning tree of the graph is a connected sub-graph in which there are no cycles .<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">A spanning tree of a graph is just a sub-graph that contains all the vertices and is a tree. A graph may have many spanning trees. Spanning trees of the complete graph with 4 vertices is given in Figure 34.1. A spanning tree has the fewest number of edges possible while still retaining a connection between all the vertices in the component. If the component contains <em>n<\/em> vertices, the spanning tree contains <em>n<\/em> \u2013 1 edges. When you traverse all the vertices of an undirected graph, you generate a spanning forest.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">To find a spanning tree of a graph, we must pick an initial node and call it part of the spanning tree. Then we do a search (either BFS or DFS) from the initial node and each time you find a node that is not in the spanning tree, add both the new node <em>and <\/em>the edge you followed to get to it to the spanning tree<\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-510 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-328.png\" alt=\"\" width=\"513\" height=\"282\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-328.png 513w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-328-300x165.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-328-65x36.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-328-225x124.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-328-350x192.png 350w\" sizes=\"auto, (max-width: 513px) 100vw, 513px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>34.2 Minimum Spanning Trees<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In a weighted graph, the weight of a sub -graph is the sum of the weights of the edges in the sub-graph. A minimum spanning tree (MST) for a weighted undirected graph is a spanning tree with minimum weight.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The Minimum Spanning Tree for a given graph is the Spanning Tree of minimum cost for that graph as shown below:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-511 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-329.png\" alt=\"\" width=\"493\" height=\"196\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-329.png 493w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-329-300x119.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-329-65x26.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-329-225x89.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-329-350x139.png 350w\" sizes=\"auto, (max-width: 493px) 100vw, 493px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>4.3 Creating a Spanning Tree<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Either DFS or BFS can be used to create a spanning tree. When DFS is used, the resulting spanning tree is known as a depth first spanning tree. When BFS is used, the resulting spanning tree is known as a breadth first spanning tree. Adding a non-tree edge into any spanning tree, will create a cycle.<\/p>\n<p>&nbsp;<\/p>\n<p>\u2022\u00a0 Assume you have an undirected graph, G = (V,E)<\/p>\n<p>\u2022\u00a0 \u00a0Spanning tree of graph G is tree<\/p>\n<p>&nbsp;<\/p>\n<p>T\u00a0 = (V,E<sub>T<\/sub> <strong>\u00cd<\/strong> E)<\/p>\n<ul>\n<li>Tree has same set of nodes<\/li>\n<li>\u00a0All tree edges are graph edges<\/li>\n<\/ul>\n<\/div>\n<div>\n<p style=\"text-align: justify\">For a given tree T in a graph G, the edges and vertices of T are called tree edges and tree vertices, and the edges and vertices of G that are not in T are called non-tree edges and non-tree vertices.<\/p>\n<p>&nbsp;<\/p>\n<p>E(G):T(tree edges) + N(nontree edges)<\/p>\n<p>where T is the set of edges E<sub>T<\/sub> used during search and N is the set of remaining edges<\/p>\n<p>&nbsp;<\/p>\n<p><strong>34.4 Properties of Spanning Trees<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>34.4.1 Property 1 of Spanning Trees<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Given a graph G = (V,E), and spanning tree: T = (V,E T) the property states that for any edge c in G but not in T, there is a simple cycle containing only edge c and edges in spanning tree. This is shown in Figure 34.3.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-512 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-330.png\" alt=\"\" width=\"517\" height=\"199\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-330.png 517w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-330-300x115.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-330-65x25.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-330-225x87.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-330-350x135.png 350w\" sizes=\"auto, (max-width: 517px) 100vw, 517px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p><strong>34.4.2 Property 2 of Spanning Tree<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Given a graph G = (V,E), and spanning tree: T = (V,E <sub>T<\/sub>) the property states that for any edge c in G but not in T, there is a simple cycle Y containing only edge c and edges in spanning tree. Moreover, inserting edge c into T and deleting any edge in Y gives another spanning tree T\u2019 (Figure 34.4).<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-513 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-331.png\" alt=\"\" width=\"529\" height=\"187\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-331.png 529w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-331-300x106.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-331-65x23.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-331-225x80.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-331-350x124.png 350w\" sizes=\"auto, (max-width: 529px) 100vw, 529px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p><strong>34.5 Building BFS\/DFS Spanning Trees<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Before we build the spanning tree let us define the concept of frontier edge. A frontier edge for a given tree T in a graph is a non-tree edge with one endpoint in T, called its tree endpoint, and one endpoint not in T, its non-tree endpoint.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Let T be a tree subgraph of a graph G, and let S be the set of frontier edges for T. The function nextEdge(G,S) chooses and returns as its value the frontier edge in S\u00a0<span style=\"font-size: 1em;text-align: initial\">that is to be added to tree T. After a frontier edge is added to the current tree, the procedure updateFrontier(G,S) removes from S those edges that are no longer frontier edges and adds to S those that have become frontier edges. Figure 34.5 gives a generic tree growing algorithm.<\/span><\/p>\n<\/div>\n<div>\n<table style=\"border-collapse: collapse;width: 100%\">\n<tbody>\n<tr>\n<td style=\"width: 100%\"><strong>Algorithm: Tree-Growing(G, v)<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Input: a connected graph G, a starting vertex v \u20ac V<\/strong><strong>G<\/strong><strong>, and a selection-function nextEdge.<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Output: an ordered spanning tree T of G with root v.<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Initialize tree T as vertex v.<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Initialize S as the set of proper edges incident on v.<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>While S \u2260 <\/strong><strong>f<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Let e = nextEdge(G, S).<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Let w be the non-tree endpoint of edge e.<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Add edge e and vertex w to tree T.<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>updateFrontier(G,S).<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Return tree T.<\/strong><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><strong>Figure 34.5 Generic Tree Growing Algorithm <\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>35.5.1 BFS and DFS as Tree-Growing<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The depth-first and breadth-first searches use opposite versions of nextEdge. The nextEdge version of breadth first search selects a frontier edge whose tree endpoint was discovered earliest (least recently). The nextEdge version of depth first search selects a frontier edge whose tree endpoint have been most recently discovered. Let us consider the example shown in Figure 34.6.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-514 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-332.png\" alt=\"\" width=\"637\" height=\"271\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-332.png 637w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-332-300x128.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-332-65x28.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-332-225x96.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-332-350x149.png 350w\" sizes=\"auto, (max-width: 637px) 100vw, 637px\" \/><\/p>\n<\/div>\n<p>N<span style=\"text-align: initial;font-size: 1em\">ow the graph is shown and we first create the spanning tree using Breadth First search.<\/span><\/p>\n<div>\n<p>&nbsp;<\/p>\n<p><strong>34.5.1 Example: BFS for Spanning Tree Construction<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">BFS uses the queue data structure for maintaining the yet to be discovered edges. Initially the edge from dummy node to A is inserted in the queue. Now since this is the only entry in the queue it is deleted and output as (dummy,A). Now we get all edges from A <strong>[(A,B),(A,G),(A,F)]<\/strong> are added to the queue as shown below and its destination nodes B,G,F are marked as done. These edges are added to the spanning tree. Now the first edge (A,B) from the queue is deleted and edges emanating from B [(B,C)] is inserted at the back of the queue but only if the destination node of edge C is not already done, and edge (B,G) is not added to the queue or the spanning tree. Edge <strong>(B,C)<\/strong> is added to the spanning tree. Now we again delete the edge from the front of the queue (A,G) and add the edges emanating from G [<strong>(G,I),(G,H)<\/strong>] to the queue if the condition explained before is satisfied. These edges are also added to the spanning tree. Note that edge (G,B) is not inserted into the queue since node B has already been processed. Next the edge (A,F) is deleted from the queue and edges emanating from F and satisfying the condition discussed above ( here<strong>(F,E)<\/strong>) is inserted at the back of the queue and added to the spanning .tree. Next edge (B,C) is deleted and edges from C here <strong>(C,D)<\/strong> is marked as done and added to the spanning tree. Now we have covered all the nodes of the graph and the process is complete.<\/p>\n<table style=\"border-collapse: collapse;width: 100%\">\n<tbody>\n<tr>\n<td style=\"width: 100%\">[(dummy,A)]<\/p>\n<p>[(A,B),(A,G),(A,F)]<\/p>\n<p>[(A,G),(A,F),(B,C)]\u2026..<\/p>\n<p>[(A,F), (B,C), (G,I),(G,H)]<\/p>\n<p>[(B,C), (G,I),(G,H), (F,E)]<\/p>\n<p>[(G,I),(G,H),(F,E), (C,D)]\u2026\u2026<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><strong>34.5.2 Example: DFS for Spanning Tree Construction<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">DFS uses the stack data structure and the details are shown below. Here edges are added to stack if edge is not marked or destination node of the edge not marked (Figure 34.7). Initially we start from A and push all edges of A (AB,AF,AG) onto stack and mark A. Now we pop top edge from stack <strong>(AG)<\/strong>, mark edge AG and node G and push all edges of G onto stack if the destination node of the edge is not already marked (GB,GH,GI), note GA is not added since it is marked. Now we pop top edge from stack <strong>(GI)<\/strong>, mark node I and add edges of I (IF, IH, IE) to stack. Now note that IG is not added since it is already marked. Now we pop top edge from stack <strong>(IE)<\/strong>, mark node E and add edges of E (ED, EF) to stack. Now note that EI is not added since it is already marked. Now we pop top edge from stack <strong>(EF)<\/strong>, mark node F and add no edges to stack since destination nodes of edges (FA,FI) are marked and\u00a0<span style=\"text-align: initial;font-size: 1em\">edge FE is marked. Now we pop top edge from stack <\/span><strong style=\"text-align: initial;font-size: 1em\">(ED)<\/strong><span style=\"text-align: initial;font-size: 1em\">, mark node D and add edges of D (DC, DH) to stack. Now note that DE is not added since it is already marked. Now we pop top edge from stack <\/span><strong style=\"text-align: initial;font-size: 1em\">(DH)<\/strong><span style=\"text-align: initial;font-size: 1em\">, mark node H and add edge of H (HC) to stack. Now note that the edge HD is not added to stack since the edge is marked and edges (HG, HI) since their destination nodes are marked. Now we pop top edge from stack <\/span><strong style=\"text-align: initial;font-size: 1em\">(HC)<\/strong><span style=\"text-align: initial;font-size: 1em\">, mark node C and add edge (CB) to stack. Now note that the edges (CH, CB) are not added to stack since the edge are marked and edge CD is not added since its destination node is marked. Now we pop top edge from stack <\/span><strong style=\"text-align: initial;font-size: 1em\">(CB)<\/strong><span style=\"text-align: initial;font-size: 1em\">, mark node B and no more edges to stack since all nodes in the graph have been marked. The process is now complete.<\/span><\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-515 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-333.png\" alt=\"\" width=\"650\" height=\"436\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-333.png 650w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-333-300x201.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-333-65x44.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-333-225x151.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-333-350x235.png 350w\" sizes=\"auto, (max-width: 650px) 100vw, 650px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p><strong>34.6 Weighted Spanning Trees<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Now let us assume that we have an undirected graph G = (V,E) with weights on each edge. The Spanning tree of graph G is a tree T = (V,E<sub>T<\/sub> <span style=\"text-decoration: underline\">c<\/span> E).<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The tree has same set of nodes, all tree edges are graph edges and weight of spanning tree = sum of tree edge weights .<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">A Minimal Spanning Tree (MST) is any spanning tree whose weight is minimal. In general, a graph has several MST\u2019s. There are many applications of circuit-board routing, networking, etc. The MST is acyclic because it is a tree. It is <strong><em>spanning<\/em><\/strong> because it covers every vertex and it is <strong><em>minimum<\/em><\/strong> because it has minimum cost.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>34.6.1 Minimum Spanning Tree<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">If we wish we can have an MST start at a specific node. However, if there are weighted edges and all weighted edges are unique (if all edges have distinct\u00a0<span style=\"text-align: initial;font-size: 1em\">weights), only one MST will exist. In a weighted graph, you can sum the weights for all edges in a spanning tree and attempt to find a spanning tree that minimizes this sum. A generic MST algorithm maintains an acyclic subgraph F of the input graph G. F is a subgraph of the minimum spanning tree of G, and we can use several algorithms for finding a <\/span><strong style=\"text-align: initial;font-size: 1em\">minimum spanning tree<\/strong><span style=\"text-align: initial;font-size: 1em\"> for a component. Repeated application to all the components in a graph yields a <\/span><strong style=\"text-align: initial;font-size: 1em\">minimum spanning forest.<\/strong><\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-516 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-334.png\" alt=\"\" width=\"411\" height=\"281\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-334.png 411w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-334-300x205.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-334-65x44.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-334-225x154.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-334-350x239.png 350w\" sizes=\"auto, (max-width: 411px) 100vw, 411px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>36.2 Real Life Applications of MST<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The standard application is to a problem like phone network design. You have a business with several offices; you want to lease phone lines to connect them up with each other; and the phone company charges different amounts of money to connect different pairs of cities. You want a set of lines that connects all your offices with a minimum total cost. It should be a spanning tree, since if a network isn\u2019t a tree you can always remove some edges and save If it is constrained to bury the cable only along certain paths, then there would be a graph representing which nodes(cities) are connected by those paths. Some of those paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weights. A <em>minimum spanning tree<\/em> would be the network with the lowest total cost as given above (Figure 34.8).<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-517 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-335.png\" alt=\"\" width=\"411\" height=\"281\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-335.png 411w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-335-300x205.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-335-65x44.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-335-225x154.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-335-350x239.png 350w\" sizes=\"auto, (max-width: 411px) 100vw, 411px\" \/><\/p>\n<\/div>\n<p style=\"text-align: justify\">36.2 Real Life Applications of MST The standard application is to a problem like phone network design. You have a business with several offices; you want to lease phone lines to connect them up with each other; and the phone company charges different amounts of money to connect different pairs of cities. You want a set of lines that connects all your offices with a minimum total cost. It should be a spanning tree, since if a network isn\u2019t a tree you can always remove some edges and save If it is constrained to bury the cable only along certain paths, then there would be a graph representing which nodes(cities) are connected by those paths. Some of those paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weights. A minimum spanning tree would be the network with the lowest total cost as given above (Figure 34.8).<\/p>\n<p><strong>\u00a0<\/strong><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-518 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-336.png\" alt=\"\" width=\"563\" height=\"284\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-336.png 563w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-336-300x151.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-336-65x33.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-336-225x113.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-336-350x177.png 350w\" sizes=\"auto, (max-width: 563px) 100vw, 563px\" \/><\/p>\n<div>\n<p style=\"text-align: justify\">Another example could be the determination of how an airline can service all cities, while minimizing the total length of the routes it needs to support . In a weighted, undirected graph, it is a tree formed by connecting all of the vertices with minimal cost (Fig 34.9).<\/p>\n<p>&nbsp;<\/p>\n<p><strong>36.3<\/strong>\u00a0<strong>Single Source Shortest Path (SSSP) tree<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">This tree is constructed the input is a single source vertex in a weighted, directed graph and the job is to compute a shortest path for each possible destination. This is similar to BFS. Thus for a weighted graph <em>G = (V,E,w)<\/em>, the <em>single -source shortest<\/em> <em>paths <\/em>problem is to find the shortest paths from a vertex<em> w <\/em><em>\u2208<\/em><em> V <\/em>to all other vertices in\u00a0<em>V<\/em>. The Single Source Shortest Path (SSSP) has a given fixed start node. However in MST at any point in construction, we have a bunch of nodes that we have reached, and we look at the shortest distance from any one of those nodes to a new node (Figure 34.10).<\/p>\n<\/div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-519 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-337.png\" alt=\"\" width=\"313\" height=\"270\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-337.png 313w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-337-300x259.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-337-65x56.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-337-225x194.png 225w\" sizes=\"auto, (max-width: 313px) 100vw, 313px\" \/><\/p>\n<div>\n<p>&nbsp;<\/p>\n<p><strong>34.6.4 Property 3 of Minimal Spanning Trees<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Given the Graph: G = (V,E) and the Spanning tree: T = (V,E T). For any edge: c in G but not in T, there is a simple cycle Y containing only edge c and edges in spanning tree (already proved). Moreover, weight of c must be greater than or equal to weight of any edge in this cycle as given in Figure 34.11.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-520 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-338.png\" alt=\"\" width=\"555\" height=\"218\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-338.png 555w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-338-300x118.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-338-65x26.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-338-225x88.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-338-350x137.png 350w\" sizes=\"auto, (max-width: 555px) 100vw, 555px\" \/><\/p>\n<\/div>\n<p><strong>\u00a0<\/strong><strong style=\"text-align: initial;font-size: 1em\">\u00a0 \u00a0 34.7 MST algorithms<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong style=\"text-align: initial;font-size: 1em\">34.7.1 Bor\u016fvka\u2019s Algorithm<\/strong><\/p>\n<div>\n<p style=\"text-align: justify\">The first MST Algorithm was created by Otakar Bor\u016fvka in 1926. The algorithm was used to create efficient connections between the electricity network in the Czech Republic. This algorithm is no longer used after Prim\u2019s and Kruskal\u2019s algorithms were discovered.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>34.7.2 Greedy Algorithms for MST<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Let us first understand what is meant by a greedy approach. Greedy algorithms apply to problems with O<em>ptimal substructures<\/em> where optimal solutions contain optimal sub-solutions or has the <em>greedy choice property<\/em> where an optimal solution can be obtained by making the greedy choice at each step. Here we discuss the <strong>greedy-choice property <\/strong>whe<strong>re <\/strong>a globally optimal solution can be arrived at by making a locally optimal (greedy) choice.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">A <strong><em>greedy algorithm<\/em><\/strong> always makes the choice for a locally optimal solution which seems the best at the current moment with the hope of arriving at a globally optimal solution. This approach efficiently computes a solution, works well for a wide range of problems, such as minimum-spanning-tree algorithms, Dijkstra&#8217;s algorithm for shortest paths from a single source, etc. Greedy algorithms construct a solution to an optimization problem piece by piece through a sequence of choices that are feasible, locally optimal and irrevocable. The greedy approach to MST is an optimization problem where we need to find minimum cost for connecting all vertices. Let us understand the greedy approach (Figure 34.12). Let us assume that we have a set of disjoint components (initially nodes). Now we need to add the cheapest edge that joins disjoint components We first start with node 1, and then choose the edge (1,2) since it is the cheapest edge associated with 1 and does not form a cycle. Now from 2, we choose edge (2,6) the cheapest edge from 2 without counting edge (2,1) (which will result in a cycle). Next we choose (6,3) and then (3,5) and finally (6,4) until we exhaust all the vertices.<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-521 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-339.png\" alt=\"\" width=\"542\" height=\"256\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-339.png 542w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-339-300x142.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-339-65x31.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-339-225x106.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-339-350x165.png 350w\" sizes=\"auto, (max-width: 542px) 100vw, 542px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>Both MST algorithms Kruskal, and Prim, determine an edge to be added to form the MST.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>34.7.2.1<\/strong>\u00a0<strong>Greedy Algorithm 1 \u2013 Kruskal\u2019s Algorithm<\/strong><\/p>\n<\/div>\n<p style=\"text-align: justify\">Kruskal\u2019s algorithm grows a tree by repeatedly adding the least cost edge that does not introduce a cycle among the edges included so far. The intermediary solution is a spanning forest. Here we add the cheapest edges that join disjoint components . The Kruskal\u2019s algorithm will be discussed in detail in Module 35.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>34.7.2.2 Greedy Algorithm 2 &#8211; Prim\u2019s Algorithm<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Prim\u2019s algorithm grows a single tree by repeatedly adding the least cost edge that connects a vertex in the existing tree to a vertex not in the existing tree . The intermediary solution is a sub-tree. Here we extend the tree by including the cheapest outgoing edge. The Prim\u2019s algorithm will be discussed in detail in Module 36.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>34.7.3 Why do the Greedy Algorithms work?<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">For simplicity, assume all edge costs are distinct. Let S be a subset of V, and suppose e = (u, v) is the minimum cost edge of E, with u in S and v in V-S and e is in every minimum spanning tree.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Summary<\/strong><\/p>\n<ul>\n<li>Understood the concept of Spanning Trees<\/li>\n<li>Discussed Minimum Spanning Trees and its properties<\/li>\n<li>Explained the Greedy approach to finding Minimum Spanning Trees<\/li>\n<\/ul>\n<table>\n<tbody>\n<tr>\n<td><strong>you can view video on Minimum Spanning Trees-I<\/strong><\/td>\n<td><a href=\"https:\/\/youtu.be\/T_0SjGCONqg\" target=\"_blank\" rel=\"noopener\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-522 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-340.png\" alt=\"\" width=\"662\" height=\"539\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-340.png 662w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-340-300x244.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-340-65x53.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-340-225x183.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-340-350x285.png 350w\" sizes=\"auto, (max-width: 662px) 100vw, 662px\" \/><\/p>\n","protected":false},"author":3,"menu_order":34,"template":"","meta":{"_acf_changed":false,"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-t-v-geetha"],"pb_section_license":""},"chapter-type":[],"contributor":[59],"license":[],"class_list":["post-507","chapter","type-chapter","status-publish","hentry","contributor-dr-t-v-geetha"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/507","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/users\/3"}],"version-history":[{"count":7,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/507\/revisions"}],"predecessor-version":[{"id":980,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/507\/revisions\/980"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/507\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/media?parent=507"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapter-type?post=507"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/contributor?post=507"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/license?post=507"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}