Minimum Spanning Tree - WordPress.com

Minimum Spanning Tree - WordPress.com

Minimum Spanning Tree By: Prof. Uzair Salman Spanning Tree It is a connected graph using all vertices in which there is no cycle Undirected graph G=(V,E) A C A C A C A C A C B D B

D B D B D B D G=(V,E) V={A,B,C,D} E={A-B,B-A,A-C,C-A,B-D,D-B,C-D,D-C} Minimum Spanning Tree We want to find a subset of E with minimum total weight/length that connects all the vertices in to a tree. A 2 3 C A 14

8 B 4 2 D B 4 A C 3 8 D 2 3 9 B 4 A

C D 2 13 B A C 3 8 D C 15 B 4 8 D Applications of MST Network design.

telephone Electrical Hydraulic TV cable Computer network road Cluster analysis Handwriting Recognition Applications Contd.. The phone company task is to provide phone lines to a village with 10 houses, each labeled H1 through H10. A single cable must connects each home. The cable must run through houses H1, H2, and so forth, up through H10. Each node is a house, and the edges are the means by which one house can be wired up to another. The weights of the edges dictate the distance between the homes. Their task is to wire up all ten houses using the least amount of telephone wiring possible. Graphical representation of hooking up a 10-home village with phone lines The two valid spanning trees from the above graph. Problem: Laying Telephone Wire Central office Problem: Laying Telephone Wire

! e v i s n e Exp Central office Problem: Laying Telephone Wire ! e v i ct e f f E Central office Algorithm for Minimum Spanning Tree (MST) Two basic algorithms exists Kruskals Prim May have different complexity (efficiency) depending on the topology of the network. MST Kruskals Algorithm

1. Sort all the edges in non-decreasing order of their weight. 2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. 3. Repeat step#2 until there are (V-1) edges in the spanning tree. Example: A 11 10 4 6 B 13 D 5 C 1 12 F 8 E 20

The graph contains 6 vertices and 10 edges. So, the minimum spanning tree formed will be having (6 1) = 5 edges. Step-1: Sort all the edges in nondecreasing order of their weight After sorting: Weight SrcDest 1 C E 4 C D 5 A E 6 A C 8 D E 10 A D 11 A B 12 D F 13 B C 20 E F A 11 10 4 6 B 13 D

5 C 1 12 F 8 E 20 STEP 2: Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. Weight 1 C 4 C 5 A 6 A 8 D 10 A 11 A 12 D 13 B 20 E Src Dest E

D E C E D B F C F A 11 10 4 6 B 13 D 5 C 1 12 F 8

E 20 STEP 2: Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. Weight 1 C 4 C 5 A 6 A 8 D 10 A 11 A 12 D 13 B 20 E Src Dest E D E C E D B F C F

C 1 E STEP 2: Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. Weight 1 C 4 C 5 A 6 A 8 D 10 A 11 A 12 D 13 B 20 E Src Dest E D E C E D B

F C F D 4 C 1 E STEP 2: Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. Weight 1 C 4 C 5 A 6 A 8 D 10 A 11 A 12 D 13 B 20 E Src Dest E

D E C E D B F C F D A 4 5 C 1 E STEP 2: Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. Weight 1 C 4 C 5 A 6 A 8 D

10 A 11 A 12 D 13 B 20 E Src Dest E D E C E D B F C F E T A CRE ! P LOO D A 4 6

5 C 1 E STEP 2: Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. Weight 1 C 4 C 5 A 6 A 8 D 10 A 11 A 12 D 13 B 20 E Src Dest E D E C E D B

F C F E T A CRE ! P LOO D A 4 5 C 1 8 E STEP 2: Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. Weight 1 C

4 C 5 A 6 A 8 D 10 A 11 A 12 D 13 B 20 E Src Dest E D E C E D B F C F E T A CRE ! P LOO A

10 D 4 5 C 1 E STEP 2: Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. Weight 1 C 4 C 5 A 6 A 8 D 10 A 11 A 12 D 13 B 20 E Src Dest E D

E C E D B F C F 11 D A 4 B 5 C 1 E STEP 2: Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. Weight 1 C

4 C 5 A 6 A 8 D 10 A 11 A 12 D 13 B 20 E Src Dest E D E C E D B F C F 11 D A 4 B F

5 C 1 12 E STEP 2: Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. Weight 1 C 4 C 5 A 6 A 8 D 10 A 11 A 12 D 13 B 20 E Src Dest E D E C E

D B F C F 11 ! P LOO D A 4 EB T A CRE F 5 13 C 1 12

E STEP 2: Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. Weight 1 C 4 C 5 A 6 A 8 D 10 A 11 A 12 D 13 B 20 E Src Dest E D E C E D B F C F 11

! P LOO D A 4 EB T A CRE 12 F 5 C 1 E 20 STEP 3: Repeat step#2 until there are (V-1) edges in the spanning tree Weight

1 C 4 C 5 A 6 A 8 D 10 A 11 A 12 D 13 B 20 E Src Dest E D E C E D B F C F 11 D A 4 B F

5 C 1 12 E ! H P RA G AL N IG R O 11 10 13 D 4 6 B

G N I N N A SP A 5 C F 8 E 1 12 20 ! E E TR 11 D

A 4 B F 5 C 1 12 E MST Prims Algorithm 1. Remove all loops and parallel edges 2. Choose any arbitrary node as root node 3. Check outgoing edges and select the one with less cost 3. Repeat step#3 until there are (V-1) edges in the spanning tree. Example:9 A 7 6 D 4

3 B 8 F 2 C 1 5 3 E 2 Step 1:- Remove all loops and parallel edges 9 A 7 6 D 4

3 B 8 F 2 C 1 5 3 E 2 Step 2:- Choose any arbitrary node as root node A 7 6 4 3 B

8 D 5 F 2 C 3 E 2 In this case, we choose B node as the root node of Prim's spanning tree. Step 3:- Check outgoing edges and select the one with less cost A 7 6 4 3 B 8

D 5 F 2 C 3 E 2 We choose the edge B,A as it is lesser than the other. Step 3:- Check outgoing edges and select the one with less cost A 7 6 4 3 B 8 D

5 F 2 C 3 E 2 the tree B-7-A is treated as one node and we check for all edges going out from it. We select the one which has the lowest cost and include it in the tree. Step 3:- Check outgoing edges and select the one with less cost A 7 6 4 3 B 8 D 5

F 2 C 3 E 2 the tree B-7-A-3-C is treated as one node and we check for all edges going out from it. We select the one which has the lowest cost and include it in the tree. Step 3:- Check outgoing edges and select the one with less cost A 7 6 4 3 B 8 D 5 F

2 C 3 E 2 the tree B-7-A-3-C-3-E is treated as one node and we check for all edges going out from it. We select the one which has the lowest cost and include it in the tree. Step 3:- Check outgoing edges and select the one with less cost A 7 6 4 3 B 8 D 5 F

2 C 3 E 2 the tree B-7-A-3-C-3-E-2-F is treated as one node and we check for all edges going out from it. We select the one which has the lowest cost and include it in the tree. Step 4:- Repeat step#3 until there are (V-1) edges in the spanning tree A 7 6 4 3 B 8 D 5 F 2

C 3 E 2 Hence all nodes are visited, spanning tree is formed Step 4:- Repeat step#3 until there are (V-1) edges in the spanning tree B D A 7 3 F 2 C 3 E 2

Hence all nodes are visited, spanning tree is formed with following edged ANY QUESTION ?

Recently Viewed Presentations

  • Purchasing For Green Hotels Purchasing For Green Hotels

    Purchasing For Green Hotels Purchasing For Green Hotels

    Victor Lebow (retailing analyst) could have been a defining catalyst: He said "… our productive economy demands that we make consumption our way of life, that we convert the buying and use of goods into rituals, that we seek our...
  • The United States in the Cold War Chapter 25

    The United States in the Cold War Chapter 25

    Roots of the Cold War. An Iron Curtain divided Eastern and Western Europe. Eastern side under the influence of Soviet Communism. Western side under the influence of United States and democracy
  • Was Steve Jobs an Ignatian Educator? Tinkering, Thinking

    Was Steve Jobs an Ignatian Educator? Tinkering, Thinking

    1955, to two university students, Joanne Carole Schieble and Syrian born Abdulfattah "John" Jandali (who were both unmarried at the time. He was adopted at birth by Paul Reinhold Jobs (1922-1993) and Clara Jobs (1924-1986) His biological parents subsequently married...
  • Does Australia need a Google Tax? - Ozblogistan

    Does Australia need a Google Tax? - Ozblogistan

    Scott Morrison - second reading speech. ... T.J. Atwood, Michael Drake, James Myers, and Linda Myers 2012, Home Country Tax System Characteristics and Corporate Tax Avoidance: International Evidence, ... Does Australia need a Google Tax?
  • The Digestive System Chapter 16 - San Diego Mesa College

    The Digestive System Chapter 16 - San Diego Mesa College

    Arial Wingdings Calibri Tahoma Arial Black Times New Roman Pixel Textured 1_Pixel Adobe Photoshop Elements Image The Digestive System Chapter 25 Function of the Digestive System Organs of the Digestive System Processes of Digestion Processes of Digestion Processes of Digestion...
  • Common Persuasive Techniques - Bedford Public Schools

    Common Persuasive Techniques - Bedford Public Schools

    Persuasion What is persuasion? A means of convincing people: to buy a certain product to believe something or act in a certain way to agree with a point of view Common persuasive techniques often used in advertising Slogan Bandwagon Card...
  • Vaughan Primary School KS2 SATS 2018 Parents Information

    Vaughan Primary School KS2 SATS 2018 Parents Information

    These revision pages support the work they do at Woodlands Junior School. They have been put together for their students to help them with their revision. Included are some sample questions taken from past Key Stage 2 SATs papers, as...
  • Formal accessibilité et technographie de la poésie extrême ...

    Formal accessibilité et technographie de la poésie extrême ...

    Monica Belluci. Monica Bellucci est une actrice française née le 30 septembre 1964 dans la ville de Città di Castello, en Italie. Elle a été l'épouse de Vincent Cassel, acteur français rencontré lors du tournage de l'Appartement.Elle commence par être...