Minimum Spanning Tree- Prim’s algorithm, Kruskal’s algorithm скачать в хорошем качестве

Minimum Spanning Tree- Prim’s algorithm, Kruskal’s algorithm

DAY 8 – UNIT 2 TOPIC: Minimum Spanning Tree (MST), Prim’s Algorithm, Kruskal’s Algorithm -------------------------------------------------- 1. MINIMUM SPANNING TREE (MST) -------------------------------------------------- Spanning Tree: A spanning tree of a connected, undirected graph is a subgraph that: Includes all vertices Is connected Contains no cycles Has exactly (V − 1) edges Minimum Spanning Tree: A Minimum Spanning Tree is a spanning tree with the minimum possible total edge weight. Conditions: Graph must be connected Graph must be weighted Graph must be undirected -------------------------------------------------- 2. PROPERTIES OF MINIMUM SPANNING TREE -------------------------------------------------- 1. An MST has exactly (V − 1) edges 2. Removing any edge disconnects the tree 3. Adding any edge creates a cycle 4. MST may not be unique if weights are equal 5. MST ensures minimum total cost -------------------------------------------------- 3. PRIM’S ALGORITHM -------------------------------------------------- Definition: Prim’s algorithm is a greedy algorithm that builds the Minimum Spanning Tree by starting from a single vertex and repeatedly adding the minimum weight edge that connects the tree to a new vertex. Approach: Start with any vertex Grow the MST one edge at a time Always choose the smallest edge connecting visited and unvisited vertices Data Structures Used: Priority Queue (min-heap) Array for visited vertices -------------------------------------------------- 4. PRIM’S ALGORITHM – STEPS -------------------------------------------------- 1. Select an arbitrary starting vertex 2. Initialize MST as empty 3. Add all edges from the selected vertex to priority queue 4. Pick minimum weight edge 5. If destination vertex is unvisited: Add edge to MST Mark vertex visited Add its edges to priority queue 6. Repeat until MST has (V − 1) edges Time Complexity: Using adjacency matrix: O(V²) Using adjacency list + min heap: O(E log V) -------------------------------------------------- 5. KRUSKAL’S ALGORITHM -------------------------------------------------- Definition: Kruskal’s algorithm is a greedy algorithm that builds the MST by selecting edges in increasing order of weight and adding them if they do not form a cycle. Approach: Sort all edges by weight Add edges one by one Skip edges that form a cycle Data Structures Used: Disjoint Set (Union-Find) -------------------------------------------------- 6. KRUSKAL’S ALGORITHM – STEPS -------------------------------------------------- 1. Sort all edges in ascending order of weight 2. Initialize each vertex as a separate set 3. Pick the smallest edge 4. If adding the edge does not form a cycle: Include it in MST Union the two vertices 5. Repeat until MST has (V − 1) edges Time Complexity: Sorting edges: O(E log E) Union-Find operations: nearly O(1) -------------------------------------------------- 7. COMPARISON: PRIM’S vs KRUSKAL’S -------------------------------------------------- Prim’s Algorithm: Vertex-based Expands from a single node Better for dense graphs Kruskal’s Algorithm: Edge-based Builds forest and merges Better for sparse graphs -------------------------------------------------- 8. APPLICATIONS OF MST -------------------------------------------------- Network design (LAN, electrical grids) Road and railway planning Circuit design Clustering algorithms