1. **Problem Statement:** Find the Minimum Spanning Tree (MST) of the given graph using Prim's algorithm. 2. **Graph Details:** Vertices: A, B, C, D, E, F, G Edges with weights: - A-D: 1 - D-G: 5 - E-G: 5 - E-F: 5 - E-D: 4 - C-E: 4 - B-C: 3 - B-A: 2 - C-F: 2 - F-D: 3 - F-A: 3 3. **Prim's Algorithm Overview:** - Start from any vertex (we start from A). - At each step, add the smallest edge connecting a vertex in the MST to a vertex outside the MST. - Repeat until all vertices are included. 4. **Step-by-step Execution:** - Start with vertex A. - Edges from A: A-D(1), B-A(2), F-A(3). Choose A-D(1) (smallest). - MST vertices: {A, D} - Edges from MST to outside: B-A(2), F-A(3), D-G(5), E-D(4), F-D(3) - Choose B-A(2). - MST vertices: {A, D, B} - Edges from MST to outside: F-A(3), D-G(5), E-D(4), F-D(3), B-C(3) - Choose C-F(2) or B-C(3) or F-A(3) or F-D(3). The smallest is C-F(2), but C and F are outside MST, so we need an edge connecting MST to outside. Since C is outside, B-C(3) connects MST to C, but C-F(2) connects two outside vertices. So choose B-C(3). - MST vertices: {A, D, B, C} - Edges from MST to outside: F-A(3), D-G(5), E-D(4), F-D(3), C-E(4), B-C(3) (already included) - Choose F-D(3) or F-A(3) (both connect MST to F). Choose F-D(3) (smallest). - MST vertices: {A, D, B, C, F} - Edges from MST to outside: E-D(4), C-E(4), E-F(5), D-G(5), E-G(5) - Choose E-D(4) or C-E(4). Both have weight 4. Choose E-D(4). - MST vertices: {A, D, B, C, F, E} - Edges from MST to outside: D-G(5), E-G(5), E-F(5) (F already in MST) - Choose D-G(5) or E-G(5). Choose D-G(5). - MST vertices: {A, D, B, C, F, E, G} 5. **Final MST edges and weights:** - A-D: 1 - B-A: 2 - B-C: 3 - F-D: 3 - E-D: 4 - D-G: 5 6. **Total weight of MST:** $$1 + 2 + 3 + 3 + 4 + 5 = 18$$ **Answer:** The minimum spanning tree includes edges A-D, B-A, B-C, F-D, E-D, and D-G with a total weight of 18.