# Prim's Algorithm — Build MST using Greedy Selection (C++) ## Overview Prim's algorithm grows an MST from a starting vertex by always selecting the lightest edge that connects the tree to a vertex outside it. Using a min-priority queue yields **O(E log V)**. ## Implementation notes The repo `Prim.cpp` uses an adjacency list and a `priority_queue` (min-heap via `greater<>`) to select the smallest-frontier edge. Parent (`p[]`) and weight (`w[]`) arrays track the MST structure. Full file: `https://github.com/mashrur-rahman-fahim/algorithm/blob/main/Prim.cpp` ### Core idea - Initialize `w[]` with `∞`, pick start node `0` with `w[0]=0`. - Push all (`w[i]`, i) into the queue; pop min, mark visited, examine neighbors and relax. ## Complexity - Time: **O(E log V)** - Space: **O(V + E)** ## Output The program prints chosen edges and the total cost. ## Practical notes - For dense graphs using an adjacency matrix, Prim can be implemented in **O(V^2)**. - Ensure edges are added symmetrically for undirected graphs. ## Source `https://github.com/mashrur-rahman-fahim/algorithm/blob/main/Prim.cpp`.