29 @ :3 3 TE Ims.tu.edu.sa 1) Objectives The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be many spanning trees. Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. There also can be many minimum spanning trees. Minimum spanning tree has direct application in the design of networks. Note that, every connected graph has a spanning tree. There are two famous algorithms for finding the Minimum Spanning Tree: Prim's Algorithm (used in class), and Kruskal's Algorithm. Both are greedy algorithms that produce optimal solutions. Kruskal's Algorithm Step 1 - Arrange all the edges of the given graph G(VE) in ascending order as per their edge weight. Step 2 - Choose the smallest weighted edge from the graph and check if it forms a cycle with the spanning tree formed so far. Step 3 - If there is no cycle, include this edge to the spanning tree else discard it. Step 4 - Repeat Step 2 and Step 3 until (V-1) number of edges are left in the spanning tree. 2) Problem data Suppose we want to find minimum spanning tree for the following graph G 2 20 9 1 5 15 3 10 9 15 10 14 9/ 7 10 4 19 4 17 8 9 4 5 18 16 6 19 4 11 8 21 6 7 7 1 1) Find the minimum-cost spanning tree in the graph given in the figure by using Prim's algorithm, starting from the node 3. Repeat the same question starting from another node? What do you conclude? 2) Find the minimum-cost spanning tree in the graph given in the figure by using Kruskal's algorithm Step 1 - Arrange all the edge Weights Edge Weight Vertex pair (4,5) 171 ZO 3: 3 Ims.tu.edu.sa 2 2 2 2 1) Find the minimum-cost spanning tree in the graph given in the figure by using Prim's algorithm, starting from the node 3. Repeat the same question starting from another node? What do you conclude? 2) Find the minimum-cost spanning tree in the graph given in the figure by using Kruskal's algorithm Step 1 - Arrange all the edge Weights Edge Weight 4 4 4 5 7 7 8 9 9 9 Vertex pair (4, 5) (7.8) (8,9) (2, 3) (3.8) (6, 7) (5,6) (1.4) (2, 10) (9, 10) (3, 4) (3,9) (1,5) (1,3) (2.9) (9,11) (4,8) (4,6) (6,8) (10, 11) () (1,2) (7, 11) 10 10 14 15 15 16 17 18 19 19 20 21 Etc. 8 9 2 29 @ :3 3 TE Ims.tu.edu.sa 1) Objectives The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be many spanning trees. Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. There also can be many minimum spanning trees. Minimum spanning tree has direct application in the design of networks. Note that, every connected graph has a spanning tree. There are two famous algorithms for finding the Minimum Spanning Tree: Prim's Algorithm (used in class), and Kruskal's Algorithm. Both are greedy algorithms that produce optimal solutions. Kruskal's Algorithm Step 1 - Arrange all the edges of the given graph G(VE) in ascending order as per their edge weight. Step 2 - Choose the smallest weighted edge from the graph and check if it forms a cycle with the spanning tree formed so far. Step 3 - If there is no cycle, include this edge to the spanning tree else discard it. Step 4 - Repeat Step 2 and Step 3 until (V-1) number of edges are left in the spanning tree. 2) Problem data Suppose we want to find minimum spanning tree for the following graph G 2 20 9 1 5 15 3 10 9 15 10 14 9/ 7 10 4 19 4 17 8 9 4 5 18 16 6 19 4 11 8 21 6 7 7 1 1) Find the minimum-cost spanning tree in the graph given in the figure by using Prim's algorithm, starting from the node 3. Repeat the same question starting from another node? What do you conclude? 2) Find the minimum-cost spanning tree in the graph given in the figure by using Kruskal's algorithm Step 1 - Arrange all the edge Weights Edge Weight Vertex pair (4,5) 171 ZO 3: 3 Ims.tu.edu.sa 2 2 2 2 1) Find the minimum-cost spanning tree in the graph given in the figure by using Prim's algorithm, starting from the node 3. Repeat the same question starting from another node? What do you conclude? 2) Find the minimum-cost spanning tree in the graph given in the figure by using Kruskal's algorithm Step 1 - Arrange all the edge Weights Edge Weight 4 4 4 5 7 7 8 9 9 9 Vertex pair (4, 5) (7.8) (8,9) (2, 3) (3.8) (6, 7) (5,6) (1.4) (2, 10) (9, 10) (3, 4) (3,9) (1,5) (1,3) (2.9) (9,11) (4,8) (4,6) (6,8) (10, 11) () (1,2) (7, 11) 10 10 14 15 15 16 17 18 19 19 20 21 Etc. 8 9 2