Prim's Algorithm

Introduction:

This algorithm is used to find MST in given graph by creating empty set and adding vertices to it such that the edge weight is minimum from all edges going out of vertices in MST set.

Problem Statement:

find MST of graph G.

Algorithm

1. create vertext set V

2. while vertex set is not empty get the minimum distance vertex and add it to MST set

Code :

    #include <bits/stdc++.h>
    using namespace std;
    
    #define adjacency_list map<int, vector<pair<int, int>>>
    #define mp make_pair
    #define INF INT_MAX
    
    typedef struct edge
    {
        int u;
        int v;
        int w;
    } Edge;
    
    typedef struct graph
    {
        adjacency_list adj;
    
        int num_edges;
        int num_vertices;
        Edge *edge;
    } graph;
    
    void prims(graph G, int root)
    {
        set<int> vertex_set;
        for (int i = 0; i < G.num_vertices; i++)
        {
            vertex_set.insert(i);
        }
        vector<int> dist(G.num_vertices, INF);
        vector<int> prev(G.num_vertices, -1);
    
        dist[root] = 0;
        int min_dist = INF;
        int min_vertex;
        while (!vertex_set.empty())
        {
            min_dist = INF;
    
            for (auto i : vertex_set)
            {
                if (min_dist > dist[i])
                {
                    min_dist = dist[i];
                    min_vertex = i;
                }
            }
    
            for (auto i : G.adj[min_vertex])
            {
                if (vertex_set.find(i.first) != vertex_set.end() && i.second < dist[i.first])
                {
                    dist[i.first] = i.second;
                    prev[i.first] = min_vertex;
                }
            }
            vertex_set.erase(min_vertex); // vertex at min distance is in mst
        }
        cout << "vertex prev\n";
    
        for (int i = 0; i < G.num_vertices; i++)
        {
            cout << i << " " << prev[i] << "\n";
        }
        // cout << "\n";
    }
    
    int main()
    {
        // undirected graph
    
        graph G; // u - {{v1,w1}, {v2, w2}, .... {vk,wk}}
        cin >> G.num_vertices;
        cin >> G.num_edges;
    
        int u, v, w;
        for (int i = 0; i < G.num_edges; i++)
        {
            cin >> u >> v >> w;
            G.adj[u].push_back(mp(v, w));
            G.adj[v].push_back(mp(u, w)); // comment this if directed.
        }
        int s;
        cout << "Enter root for prims : ";
        cin >> s;
        prims(G, s);
        // cout << "\n";
    }

Prim's Algorithm

Introduction:

Problem Statement:

Algorithm

Code :

Complexity Analysis :

video resources

web resources

book resources