Prim’s Algorithm

In this article you will learn about prim’s algorithm which is used to find the minimum spanning tree. We will see the code of the algorithm and how it is implemented with an example. Let’s start with the definition of Minimum Spanning Tree (MST).

Minimum Spanning Tree:

A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted undirected graph that binds all the vertices together with the least feasible total edge weight without any kind of cycles.

What is Prim’s Algorithm:

Prim’s algorithm is a minimum spanning tree algorithm which is used to find the minimum cost of spanning tree and to connect each vertex/node of the tree without forming a cycle. Prim’s algorithm starts with randomly chosen node known as starting node after that all the edges which are directly connected by this node are taken into consideration and the edge which has minimum cost or weight is selected and the other vertex/node which is connected by this edge is also selected. Now we will consider both these nodes and all the edges which are directly connected by them and will again search for the minimum weight edge and again these steps will get repeated until all the vertices are connected. Few things to remember are if you are getting a cycle by selecting an edge then you should not select that edge although it has minimum weight, you should select the next minimum weight edge and second thing is if you get more than one edge whose weights are equal, and they are the minimum ones then you can select any of them unless you are getting a cycle. These were the conditions that you should take into consideration while applying prim’s algorithm. Let’s take an example to be more clear about this algorithm.

Prim's Algorithm in Python:
INF = 9999999
# number of vertices in graph
N = 5
#creating graph by adjacency matrix method
G = [[0, 19, 5, 0, 0],
[19, 0, 5, 9, 2],
[5, 5, 0, 1, 6],
[0, 9, 1, 0, 1],
[0, 2, 6, 1, 0]]
selected_node = [0, 0, 0, 0, 0]
no_edge = 0
selected_node[0] = True
# printing for edge and weight
print("Edge : Weight\n")
while (no_edge < N - 1):
minimum = INF
a = 0
b = 0
for m in range(N):
if selected_node[m]:
for n in range(N):
if ((not selected_node[n]) and G[m][n]):
# not in selected and there is an edge
if minimum > G[m][n]:
minimum = G[m][n]
a = m
b = n
print(str(a) + "-" + str(b) + ":" + str(G[a][b]))
selected_node[b] = True
no_edge += 1

Pseudocode:

Get Vansh Dubey’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

T = ∅;

M = { 1 };

while (M ≠ N)

let (m, n) be the lowest cost edge such that m ∈ M and n ∈ N — M;

T = T ∪ {(m, n)}

M = M ∪ {n}

Example:

Let us apply prim’s algorithm on the weighted graph given below.

First step was to select any random node. So, we will select node A as our starting node and then all the edges which are directly connected by A will be considered.

The edges which are directly connected are edge which connects B and has weight 4, edge which connects D and has weight 3 and last edge E which has weight 5. So we should select the minimum weight edge i.e. the edge connecting A and D which has weight 3.

Now we will consider all the edges that are directly connected with A or D and then select the edge which has minimum weight. So, the next edge would be edge between D and C which has weight 1.

Now after repeating the steps, we will get the next vertex as C with weight 2 and after that we will select the edge between A and E although it has more weight than edge between A and B but if we select AB edge then it will form a cycle which is to be avoided so we will chose AE edge and we will get the minimum spanning tree as all the nodes are connected and no cycles are there.

Cost:

Calculating the cost of the minimum spanning tree given in the above example:

Cost=3+1+2+5

=11

Time Complexity:

Because each insertion of a node into the solution requires logarithmic time, the running time of prim’s method is O(VlogV + ElogV), which is equivalent to O(ElogV). The number of edges is E, while the number of vertices/nodes is V. Using Fibonacci Heaps, we can reduce the running time complexity of prim’s algorithm to O(E + logV).

Conclusion:

As we’ve seen, the least spanning tree has its own significance in the real world, therefore it’s critical to understand the prim’s method, which may help us solve a variety of difficulties. Prim’s approach is the primary choice when it comes to determining the least spanning tree for dense graphs.