Prim's Minimum Spanning Tree Algorithm

mgcadmin 04-12-2022

Having covered Kruskal's MST algorithm in my last article, it seems only natural to now cover Prim's MST algorithm. Prim's algorithm is another Greedy Best First Search graph algorithm for finding the minimum spanning tree of an undirected weighted graph. Functionally, it is very similar to the priority queue Lazy implementation of Dijkstra's Algorithm.

The Graph

Seeing as we already developed a graph data structure and accompanying graph in my previous article on Kruskal's MST algorithm, we will use that same general data structure and graph, I have removed the sorted edge list from the graph data structure, as it is not required for Prim's algorithm.

struct Edge {
    int from;
    int to;
    int weight;
    Edge* next; //For use in adjacency list and edge list linked lists.
    Edge(int f = 0, int t = 0, int wt = 0, Edge* n = nullptr) {
        from = f; to = t; weight = wt; next = n;
    }
    bool operator<(const Edge& o) const {
        return weight < o.weight;
    }
    bool operator>(const Edge& o) const {
        return weight > o.weight;
    }
    bool operator==(const Edge& o) const {
        return from == o.from && to == o.to;
    }
    bool operator!=(const Edge& o) const {
        return (*this != o);
    }
};

class Graph {
    private:
        Edge** adjlist;
        int _E;
        int _V;
    public:
        Graph(int vertex) {
            _V = vertex; _E = 0;
            adjlist = new Edge*[_V];
            for (int i = 0; i < _V; i++)
                adjlist[i] = nullptr;
        }
        void addEdge(int from, int to, int weight) {
            for (Edge* t = adjlist[from]; t != nullptr; t = t->next)
                if (t->to == to)
                    return;
            adjlist[from] = new Edge(from, to, weight, adjlist[from]);
            adjlist[to] = new Edge(to, from, weight, adjlist[to]);               
            _E++;
        }
        Edge* adj(int vertex) {
            return adjlist[vertex];
        }
        int V() { return _V; }
        int E() { return _E; }
};

We will be using the same graph that we used in the previous article as well:

void initSampleGraph(Graph& G) {
    G.addEdge(1, 2, 1);
    G.addEdge(1, 3, 3);
    G.addEdge(2, 3, 3);
    G.addEdge(2, 4, 6);
    G.addEdge(3, 4, 4);
    G.addEdge(4, 5, 5);
    G.addEdge(3, 5, 2);
}

Prim's Algorithm

Prim's algorithm is a through and through Best First Search. If you are familiar with Dijkstra's Shortest Path algorithm, then Prim's will look VERY familiar.

Prims algorithm works by maintaining several sets as arrays: a parent pointer array (pred), an edge cost array(cost), and a visited array(seen). The main data structure though is a min-heap priority queue, for selecting the minimum edge weight vertex from each nodes adjacency list.

void prims(Graph& G) {
    vector<bool> seen(G.V(), false);
    vector<int> cost(G.V(), INT32_MAX);
    vector<int> pred(G.V(), -1);
    vector<Edge*> mst;
    int mstcost = 0;
    priority_queue<pair<int,int>, vector<pair<int,int> >, std::greater<pair<int,int> > > pq;
    cost[1] = 0;
    pq.push(make_pair(0, 1));
    while (!pq.empty()) {
        int curr = pq.top().second;
        pq.pop();
        if (!seen[curr]) {
            seen[curr] = true;
            for (Edge* t = G.adj(curr); t != nullptr; t = t->next) {
                if (!seen[t->to] && cost[t->to] > t->weight) {
                    cost[t->to] = t->weight;
                    pred[t->to] = curr;
                    pq.push(make_pair(t->weight, t->to));
                }
            }
        }
     
    }
    cout<<"MST: "<<endl;
    for (int i = 0; i < G.V(); i++) {
        if (pred[i] != -1) {
            cout<<pred[i]<<" <-> "<<i<<" - "<<cost[i]<<endl;
            mstcost += cost[i];
        }
    }
    cout<<"MST Cost: "<<mstcost<<endl;
}

Output:
MST: 
 1 <-> 2 - 1
 1 <-> 3 - 3
 3 <-> 4 - 4
 3 <-> 5 - 2
 MST Cost: 10

If you recall the result we attained by using Kruskals algorithm on the same graph, than you know we have gathered the same answer. The version of Prim's Algorithm shown above is the priority first search implementation, which executes in time proportional to E log V where E is the number of edges and V is the number of vertices in the graph.

---