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

• Puja. Part of the daily practice of life for Buddhists & Hindus. Monks in monasteries & laity in homes. Image of the Buddha; for some ancestral representation. Flowers (beauty & impermanence), fruit (what good conduct brings), water (purity/goal & example),...
• Gnawing Mammals. More of these mammals than any other on earth. Commonly known as . rodents. Ex: squirrel, beavers, chipmunks, rat, mice, porcupines. Common characteristics are four special incisors that are used for gnawing. Rodents spread serious disease
• And New Policy. DFARS PGI 204.270-2 (c) Contract deficiency reports. (1) Contracting officers and all individuals tasked with creating, managing, or viewing contract deficiency reports (CDRs) shall establish and maintain an account in WAWF.
• Nuclear Criticality Safety Division Status Report to Board of Directors American Nuclear Society June 12, 2002 Scope Nuclear Criticality Safety Division Criticality safety considerations of management of fissile material outside reactors acquisition of data related to nuclear criticality development and...
• Fact vs. Inference What is an observation? A. When you observe the world around you, you become aware of something using one of your senses. Your five senses are smell, taste, sight, touch, and sound.
• When the market works as it shouldâ€¦ The invisible hand of the marketplace leads self-interested buyers and sellers to maximize the net benefit that society can derive from a market. Is this always the case?
• Sustainable Skilling Initiative - Offer to Employers. Sourcing talent . Skilling talent. Retaining talent. SSI offer for employers. Provide employers with the required number of employees at the requested location
• Sue Dopson KU05 Melbourne ... Times New Roman Templeton Default Design 'Understanding Organisational Change in Health Care: Reconceptualising the Active Role of Context' Role of Context in Organisational Change Context and Organisational Studies Literature A Misleading Layered View of ...