Word Count : 752

---

Here’s a detailed solution to both (a) and (b) based on your graph: *** ## a) Prim’s and Kruskal’s Algorithm for Minimum Spanning Tree ### **Prim’s Algorithm: Steps and Time Complexity** **Algorithm Steps**: 1. Start from any vertex (say, **A**), add it to the MST. 2. Repeatedly add the minimum weight edge that connects a vertex in the MST to a vertex outside the MST until all vertices are included. **Time Complexity**: - Using a simple array: $$O(V^2)$$ - With Min Heap (priority queue): $$O((V+E)\log V)$$ *** ### **Prim’s Algorithm: Step-by-Step on Given Graph** **Vertices:** A, B, C, D, E, F, G | Step | Candidate Edges from MST | Smallest Edge | Add Vertex | MST Edges | |------|-----------------------------------|---------------|------------|--------------------------| | 1 | A-B(10), A-E(15) | A-B(10) | B | (A,B) | | 2 | A-E(15), B-D(4), B-C(20) | B-D(4) | D | (A,B), (B,D) | | 3 | A-E(15), B-C(20), D-F(7), D-C(8) | D-F(7) | F | (A,B), (B,D), (D,F) | | 4 | A-E(15), B-C(20), D-C(8), F-E(6), F-G(5) | F-G(5) | G | (A,B), (B,D), (D,F), (F,G)| | 5 | A-E(15), B-C(20), D-C(8), F-E(6) | F-E(6) ______ ______ __________ ________ _________ _______ _______.
_____ _________ ______ ____ ___ _________ _________.
__________ ___ _____ __________ _______ _________.
___ ____ _______ ____ ___ _____ ________ _______.
___ __________ __________ _______ ____.
_______ __________ ____ _______ ________.
_______ _____ _____ ___ ______ __________ ______ __________ _____ _______ _____ ______.
_______ _________ _________ _________ ______ ________ _______ ____ ______.
______ __________ __________ ______ ___ _________ ________ ___.
_____ ____ _______ ___ __________ _______ _________ ______ __________ ____ __________ _____.
_____ ______ ________ ________ ______ ___ _____ _________ ____ ____.
_________ _________ ______ ______ _________ ____ _____ ______ _________ _______.
________ ______ ____ _____ _________ _____ ___.
_____ ___ ________ _________ _________ _____ __________ __________.
____ _______ _______ ______ ________.
____ ____ ____ ___ ________ ________ _____ ____ ___ _________ ___ _____.
__________ _______ _______ __________ _______ __________ ___ ___ ______ _______ __________ ______.
____ ________ _______ ____ ____ __________ _______ _____ __________ ____.
_______ _________ __________ ________ ____ ____ _____ _______ ______ ________ _______.
__________ _________ _______ _______ _________ _____.
____ _____ __________ _______ _______ ____ _________ _________ ________.
_________ _________ ______ ________ ________ _____ ________ __________ ______ ______.
_________ ______ _______ _________ ________ ____ ________ _____ _____.
__________ _______ ______ ______ ________ _____ __________ ________ ____.
_______ __________ _______ ___ __________ ___ __________ ______ ____ __________.
__________ _____ _________ _____ _________ _________ _____ _________ _________ ________ ________.
______ _________ _____ _______ ___ __________ _______.
_________ _______ ________ _____ ______ _______ __________.
________ _______ ___ ___ __________ ____ ________.
_______ _____ _________ ________ ________ _____.
_______ _____ __________ _______ ______ _______ __________ ______ ____ _______.
____ _________ __________ ______ ___ _______.
________ ____ _________ _________ ___ ________ ______ ________ __________ ___ ____.
_______ __________ ________ _____ ____ ______ ___ _______ __________ ________.
_________ __________ _________ ________ ___ ______.
________ _________ ______ _____ ___ ___ _______.
_____ _________ __________ ___ ___ _____ _________ _________ ___ _______ _________ _______.
_________ _________ ________ _____ ___ ____ __________ __________.
___ _________ ____ __________ _______.
________ __________ ___ ____ ___ _______ ____ ______.
_____ ______ _______ _______ _____ ________ ___ ______ ______.
_________ __________ ________ ______ ___ ______ _________ ______ ________ ____ ______ ________.
____ ________ ________ ___ ___ _____ ___ ______.
_____ _____ ______ ______ ____ _______ ___ ____.
_____ _____ _________ _________ ___ ___ _____ __________ ___.
__________ ________ _______ ______ _________ _______ ______ _________ ________.
_________ ____ ________ ____ ________ ________ _______ _____ ______.
_________ _______ ___ _______ ____ _______.
_____ ___ _______ ___ _____ __________ _________ _______ _________ _______.
______ ________ ________ _____ __________ _____ ____.
________ _______ _____ ____ __________ ________ _______ ___ ________.
___ ____ ______ _____ ___ _______ _____ _____.
________ ___ __________ _____ _________ _______ _______ ___ _____ _________ _____.
___ _______ _______ _______ _____ ________ ___.
____ ____ _________ _____ _______ __________ ___ ____.
_______ ______ ____ _________ ______ _______ _________ ___ ____ __________.
_________ ______ ____ _______ _____ ________ ____ ________ __________ _______ _________ ________.
___ _________ _______ ___ ____.
________ _______ __________ ____ ________ ___ _________ ______ _________.
_________ _______ _____ ____ _____ _______ ____ ______ _________.
_________ _________ ____ _____ _______ ______ ___.
____ ____ _______ _________ _______ ________ ______ _________ _____ __________.
_______ _________ __________ _______ _____ _______ _______ _____ ______.
___ ________ __________ ______ _________ ________ ____ ________ _______ _____.
______ _______ _____ ___ ___ _____ ______ _________ __________ _______.
_________ ___ __________ _________ ____.
Get Full Answer on WhatsApp