Spanning Tree: Subset of edges of graph that forms a tree(acyclic), where every node is a part of tree.

1. (Edges = Vertices-1)
2. Shouldn't be disconnected
3. Acyclic
4. Multiple STs possible

Minimum Spanning Tree (MST): Spanning Tree that has minimum weight among all possible spanning Trees.

Aim is to craete a weighted, connected and undirected graph.

Prim's Algorithm#

Greedy Algorithm

• Suitable for Dense Graph
• Use Priority Queue -> minHeap

Intiution#

Prim's algorithm grows the MST one vertex at a time, always expanding towards the cheapest reachable edge from the current tree. Unlike Kruskal's (which sorts all edges globally), Prim's maintains a min-heap of edges that cross the boundary between the current MST and the remaining vertices — only locally relevant edges are tracked at each step. This makes Prim's more efficient on dense graphs where the edge count is high relative to vertices.

• Pick the smallest weight edge that connects the growing MST to an unvisited vertex.
• Use a min-heap (priority queue) to efficiently retrieve the smallest weight edge at each step.
• Mark vertices as visited when they are extracted from the heap to avoid re-processing.

Algorithm#

• Start with empty tree
• Maintain set of all vertices not yet picked.
• Pick the smallest weight edge (minHeap)
• For every vertex u, check all adjacent and pick smallest weight edge.
• Continue, until all vertices picked.
• Use visited array

Implementation#

int spanningTree(int V, vector<vector<int>> adj[]) {
        
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    vector<bool> visited(V, false);
    
    // wt -> v;
    pq.push({0,0});
    
    int mstWeight = 0;
    while(!pq.empty())
    {
        int wt = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        
        if(visited[u])
            continue;
            
        mstWeight += wt;
        visited[u] = true;
        
        for(auto it: adj[u])
        {
            int v = it[0];
            int w = it[1];
            if(!visited[v])
                pq.push({w,v});
        }
        
    }
    return mstWeight;
    
}

Time Complexity: O(VlogE) , Sort: O(ElogE), pick and check cycle: E x log(V)

Space Complexity: O(V^2)