 Vyom World.com Let's Touch the Sky Together!        Home VyomWorld.com Home Free Magazines! VyomLinks.com Home JobsAssist.com Home Vyom Network Contact Us Jobs & Careers Resume Submitter Placement Papers IT Companies Directory Computer Jobs Interview Questions Online Exams Vyom Career eMag. Fun Screensavers New! Send FREE SMS! SMS Jokes Source Codes Library Source Codes Home ASP Source Codes C Source Codes C++ Source Codes COBOL Source Codes Java Source Codes Pascal Source Codes Submit Source Codes GATE GATE an Overview GATE Preparation Study Materal GRE GRE an Overview GRE Questions GRE Preparation GRE Universities TOEFL Preparation TOEFL Resources GMAT Preparation GMAT Resources MBA Preparation MBA Resources Networking Concepts Networking Concepts Testing Preparation Testing Resources Webmasters Free Traffic Builder Webmaster Articles Web Hosting Tutorials Hardware Tutorial 1500 Free eBooks New! FREE Publications Vyom Career eMag. Get 9,000+ Interview Questions & Answers in an eBook. 9,000+ Interview Questions All Questions Answered 5 FREE Bonuses Free Upgrades Get it now!  Get 9,000+ Interview Questions with Answers in an eBook

Analysis and Design of Algorithms

7.2 Minimum-Cost spanning trees

Let G=(V,E) be an undirected connected graph. A sub-graph t = (V,E1) of G is a spanning tree of G if and only if t is a tree. Above figure shows the complete graph on four nodes together with three of its spanning tree.

Spanning trees have many applications. For example, they can be used to obtain an independent set of circuit equations for an electric network. First, a spanning tree for the electric network is obtained. Let B be the set of network edges not in the spanning tree. Adding an edge from B to the spanning tree creates a cycle. Kirchoff�s second law is used on each cycle to obtain a circuit equation.

Another application of spanning trees arises from the property that a spanning tree is a minimal sub-graph G� of G such that V(G�) = V(G) and G� is connected. A minimal sub-graph with n vertices must have at least n-1 edges and all connected graphs with n-1 edges are trees. If the nodes of G represent cities and the edges represent possible communication links connecting two cities, then the minimum number of links needed to connect the n cities is n-1. the spanning trees of G represent all feasible choice.

In practical situations, the edges have weights assigned to them. Thse weights may represent the cost of construction, the length of the link, and so on. Given such a weighted graph, one would then wish to select cities to have minimum total cost or minimum total length. In either case the links selected have to form a tree. If this is not so, then the selection of links contains a cycle. Removal of any one of the links on this cycle results in a link selection of less const connecting all cities. We are therefore interested in finding a spanning tree of G. with minimum cost since the identification of a minimum-cost spanning tree involves the selection of a subset of the edges, this problem fits the subset paradigm.

7.2.1 Prim�s Algorithm

A greedy method to obtain a minimum-cost spanning tree builds this tree edge by edge. The next edge to include is chosen according to some optimization criterion. The simplest such criterion is to choose an edge that results in a minimum increase in the sum of the costs of the edges so far included. There are two possible ways to interpret this criterion. In the first, the set of edges so far selected form a tree. Thus, if A is the set of edges selected so far, then A forms a tree. The next edge(u,v) to be included in A is a minimum-cost edge not in A with the property that A U {(u,v)} is also a tree. The corresponding algorithm is known as prim�s algorithm.

For Prim�s algorithm draw n isolated vertices and label them v1, v2, v3,�vn. Tabulate the given weights of the edges of g in an n by n table. Set the non existent edges as very large. Start from vertex v1 and connect it to its nearest neighbor (i.e., to the vertex, which has the smallest entry in row1 of table) say Vk. Now consider v1 and vk as one subgraph and connect this subgraph to its closest neighbor. Let this new vertex be vi. Next regard the tree with v1 vk and vi as one subgraph and continue the process until all n vertices have been connected by n-1 edges.

Consider the graph shown in fig 7.3. There are 6 vertices and 12 edges. The weights are tabulated in table given below. V1 V2 V3 V4 V5 V6 V1 - 10 16 11 10 17 V2 10 - 9.5 Inf Inf 19.5 V3 16 9.5 - 7 Inf 12 V4 11 Inf 7 - 8 7 V5 10 Inf Inf 8 - 9 V6 17 19.5 12 7 9 - Start with v1 and pick the smallest entry in row1, which is either (v1,v2) or (v1,v5). Let us pick (v1, v5). The closest neighbor of the subgraph (v1,v5) is v4 as it is the smallest in the rows v1 and v5. The three remaining edges selected following the above procedure turn out to be (v4,v6) (v4,v3) and (v3, v2) in that sequence. The resulting shortest spanning tree is shown in fig 7.4. The weight of this tree is 41.5.

7.2.3 Kruskal�s Algorithm:

There is a second possible interpretation of the optimization criteria mentioned earlier in which the edges of the graph are considered in non-decreasing order of cost. This interpretation is that the set t of edges so far selected for the spanning tree be such that it is possible to complete t into a tree. Thus t may not be a tree at all stages in the algorithm. In fact, it will generally only be a forest since the set of edges t can be completed into a tree if and only if there are no cycles in t. this method is due to kruskal.

The Kruskal algorithm can be illustrated as folows, list out all edges of graph G in order of non-decreasing weight. Next select a smallest edge that makes no circuit with previously selected edges. Continue this process until (n-1) edges have been selected and these edges will constitute the desired shortest spanning tree.

For fig 7.3 kruskal solution is as follows,

V1 to v2 =10

V1 to v3 = 16

V1 to v4 = 11

V1 to v5 = 10

V1 to v6 = 17

V2 to v3 = 9.5

V2 to v6 = 19.5

V3 to v4 = 7

V3 to v6 =12

V4 to v5 = 8

V4 to v6 = 7

V5 to v6 = 9

The above path in ascending order is

V3 to v4 = 7

V4 to v6 = 7

V4 to v5 = 8

V5 to v6 = 9

V2 to v3 = 9.5

V1 to v5 = 10

V1 to v2 =10

V1 to v4 = 11

V3 to v6 =12

V1 to v3 = 16

V1 to v6 = 17

V2 to v6 = 19.5

Select the minimum, i.e., v3 to v4 connect them, now select v4 to v6 and then v4 to v5, now if we select v5 to v6 then it forms a circuit so drop it and go for the next. Connect v2 and v3 and finally connect v1 and v5. Thus, we have a minimum spanning tree, which is similar to the figure 7.4. Discussion Center   Recently Updated: New Placement Papers added.
Vyom Network : Web Hosting | Dedicated Server | Free SMS, GRE, GMAT, MBA | Online Exams | Freshers Jobs | Software Downloads | Programming & Source Codes | GRE Preparation | Jobs, Discussions | Software Listing | Free eBooks | Free eBooks | Free Business Info | Interview Questions | Free Tutorials | International Business Information | IAS Preparation | Jokes, Songs, Fun | Free Classifieds | Free Recipes | FAQs | Free Downloads | Bangalore Info | Tech Solutions | Project Outsourcing, Web Hosting | GATE Preparation | MBA Preparation | SAP Info | Excellent Mobiles | Software Testing | Interview Questions | Freshers Jobs | Server Insiders | File Extension Directory