Prim’s Algorithm

by codecrucks · Published 28/10/2021 · Updated 03/08/2022

Introduction to Prim’s Algorithm

Prim’s algorithm is a greedy approach to find a minimum spanning tree from weighted, connected, undirected graph. It is a variation of Dijkstra’s algorithm. Working principle of Prim’s algorithm is very simple and explained here:

Initialize list of unvisited vertices with U_V = {V₁, V₂, V₃, . . . , V_n}

1. Select any arbitrary vertex from input graph G, call that subgraph as partial MST. Remove selected vertex from U_V

2. Form a set N_E – a set of unvisited neighbour edges of all vertices present in partial MST

3. Select an edge e = (u, v) from N_E with minimum weight, and add it to partial MST if it does not form a cycle and it is not already added.

If the addition of edge e forms a cycle, then skip that edge and select next minimum weight edge from N_E. Continue this procedure until we get an edge e which does not form a cycle. Remove corresponding added vertices u and v from U_V

4. Go to step 2 and repeat the procedure until U_Vis empty.

Prim’s algorithm is preferred when the graph is dense with V << E. Kruskal performs better in the case of the sparse graph with V ≣ E.

Algorithm for Prim’s Algorithm

Algorithm for Prim’s approach is described below :

Algorithm PRIM_MST(G, n)
// Description : Find MST of graph G using Prim’s algorithm
// Input : Weighted connected graph G and number of vertices n
// Output : Minimum spanning tree MST and weight of it i.e. cost
cost ← 0
// Initialize tree nodes

for i ← 0 to n – 1 do
    MST[i] ← 0
end

MST[0] ← 1    // 1 is the initial vertex

for k ← 1 to n do
    min_dist ← ∞
    for i ← 1 to n – 1 do
        for j ← 1 to n – 1 do
            if G[i, j] and ((MST[i] AND ¬MST[j]) or (¬MST[i] AND MST[j])) then
                if G[i, j] < min_dist then
                    min_dist ← G[i, j]
                    u ← i
                    v ← j
                end
            end
        end
    end

    print (u, v, min_dist)
    MST[u] ← MST[v] ← 1
    cost ← cost + min_dist
end
print (“Total cost = ”, cost)

Complexity Analysis of Prim’s Algorithm

In every phase, algorithm search for minimum weight edge. Running time of algorithm heavily depends on how efficiently it performs search operation.
The time taken by the algorithm can be computed as,

Rewriting the equation,

The straight-forward approach to this is to search the entire adjacency matrix for each vertex. It takes O(|V|²) time for |V| vertices and |E| edges, where |V| represents a number of vertices, i.e. n.
However, with the help of some other data structures, we can improve the performance. Using binary heap and adjacency list, time can be reduced to O( |E| log |V| )
Using the Fibonacci heap and adjacency matrix, performance can be improved to O(|E| + |V| log |V|).

Example

Problem: Find the cost of minimum spanning tree of the given graph by using Prim’s algorithm.

Solution:

Initialize U_V – list of unvisited vertices – with all vertices in given graph.
Prim’s algorithm adds some arbitrary vertex V_xfrom U_Vto the partial solution and removes V_x from U_V.
N_E -set of all neighbour edges of vertices in partial solution is explored.
The neighbour edge with minimum cost is added to the partial solution if it does not form a cycle and has not already been added to the partial solution.
Otherwise, select the next minimum cost edge and add it to the partial solution and remove it from the list of unvisited vertices U_V.
This process is repeated until all vertices are visited, i.e. U_V becomes empty.
For given graph, initially the set of unvisited vertices U_V = {a, b, c, d, e, f }.

Partial solution	Set of neighbour edges N_E	Cost of neighbour edges	Updated U_V
Step 1 : U_V = {a, b, c, d, e, f}. Let us start with arbitrary vertex a. Initial partial solution	<a, b> <a, f> <a, e>	3 5 6	{ b, c, d, e, f}
Step 2 : Edge <a, b> has minimum cost, so add it.	<a, f> <a, e> <b, c> <b, f>	5 6 1 4	{ c, d, e, f}
Step 3 : Edge <b, c> has a minimum cost, so add it.	<a, f> <a, e> <b, f> <c, f> <c, d>	5 6 4 4 6	{ d, e, f}
Step 4 : Edge <b, f> and <c, f> have same minimum cost, so we can add any of it. Let us add <c, f>	<a, f> <a, e> <b, f> <c, d> <f, d> <f, e>	5 6 4 6 5 2	{ d, e }
Step 5 : Edge <f, e> has a minimum cost, so add it.	<a, f> <a, e> <b, f> <c, d> <f, d>	5 6 4 6 5	{ d }
Step 6 : Edge <b, f> has minimum cost, but its inclusion in above partial solution creates cycle, so skip edge <b, f> and check for next minimum cost edge i.e. <a, f> Inclusion of <a, f> also creates cycle so skip it and check for next minimum cost edge, i.e. <f, d> The inclusion of <f, d> does not create a cycle, so it is a feasible edge, add it.			U_V is empty so the tree generated in step 6 is the minimum spanning tree of given graph. Let w(u, v) represent the weight of edge (u, v) Cost of solution: w(a, b) + w(b, c) + w(c, f) + w(f, d) + w(f, e) = 3 + 1 + 4 + 5 + 2 = 15

Problem: Find the cost of Minimal Spanning Tree of the given graph by using Prim’s Algorithm.

Solution:

Initialize U_V – list of unvisited vertices – with all vertices in given graph.
Prim’s algorithm adds some arbitrary vertex V_xfrom U_Vto the partial solution and removes V_x from U_V.
N_E – set of all neighbour edges of vertices in partial solution is explored.
The neighbour edge with the minimum cost is added to the partial solution if it does not form a cycle and has not already been added to the partial solution.
Otherwise, select the next minimum cost edge and add it to the partial solution and remove it from the list of unvisited vertices UV.
This process is repeated until all vertices are visited, i.e. UV becomes empty.
For a given graph, initially the set of unvisited vertices U_V = {1, 2, 3, 4, 5}.

Partial solution	Set of neighbor edges N_E	Cost of neighbor edges	Updated U_V
Step 1: U_V = {1, 2, 3, 4, 5}. Let us start with arbitrary vertex 1. Initial partial solution	<1, 2> <1, 3>	1 3	{2, 3, 4, 5}
Step 2: Edge <1, 2> has a minimum cost, so add it.	<1, 3> <2, 3> <2, 4>	3 3 4	{3, 4, 5}
Step 3: Edge <1, 3> has a minimum cost, so add it.	<2, 3> <2, 4> <3, 4> <3, 5>	3 4 4 2	{4, 5}
Step 4: Edge <3, 5> has a minimum cost, so add it.	<2, 4> <3, 4> <5, 4>	6 4 5	{4}
Step 5: Edge <3, 4> has a minimum cost, so add it.			U_V is empty so the tree generated in step 5 is the minimum spanning tree of given graph. Let w(u, v) represent the weight of edge (u, v) Cost of solution: w(1, 2) + w(1, 3) + w(3, 4) + w(3, 5) = 1 + 3 + 4 + 2 = 10

Some Popular Problems Solved by Greddy Algorithm

Greedy algorithms are used to find an optimal or near-optimal solution to many real-life problems. A few of them are listed below :

Additional Reading: Wiki