Prim’s algorithm for computing the minimum
spanning tree of a graph. Now, let’s start off with some basic definitions.
What is a spanning tree? A spanning tree is a subgraph that has the same vertex set as the
original graph and is also a tree which means that it must be connected and must not contain
any cycles. A graph may have large number of spanning trees but not all of them are
minimum. A minimum spanning tree is the one in which the sum of weight of edges is minimum.
For example, consider the graph shown here. The edges highlighted in yellow are the edges
of the spanning tree. Now, both the trees shown here form a spanning tree because each
of these contain all the 4 vertices, are connected and do not contain any cycles. But
tree 2 here a cost lower than tree 1. Infact, tree 2 is a minimum spanning tree, so the
sum of weights of its edges would be lower than any other possible spanning tree of the graph.
Step’s for finding minimum spanning tree using prim’s algorithm. Well it would be
better if we try and understand each step one by one
with the help of an example. So, let’s do that.
Consider the given graph which has 9 vertices, v0 to v8. The numbers on the edges represent the weight of that edge. We need to obtain
a minimum spanning tree of the given graph. The 1 st step says create a set mstSet which
will contain all the vertices in MST. Initially, this set will be empty of course.
Let’s look at step 2. It says that initialize the key of all vertices except the source
vertex to infinity. The source vertex is assigned key
0. Basically, the key of every vertex stores the weight of the minimum weighted edge it is
connected to such that the other end point of the edge is a vertex in mstSet. It’ll be
clearer as we proceed through the example. The next step says that we need to pick a
vertex u not in mstSet with minimum key value. Since, no vertex is in mstSET initially, we
need to look at all the vertices. Here, v0 has a key 0 while all other vertices have key infinite.
So, v0 has the minimum key and hence it’ll be added to our mstSet.
Now, here, the vertices in red represent those that our added to the MstSet while those in orange represent all vertices adjacent to
our current vertex u which are not in mstSET. According to the next step, we need to update
the key values of all vertices adjacent to u which are v1 and v7 in this case. Now, how
to update the key values? It’s simple. If the weight of edge uv is less than the key of
v, update the key value as weight of uv. We see that weight of edge 0,1 is 4 while the key of 1
is still infinite. So, we’ll update the key of v1 to 4. Similarly, the weight of edge 0,7 which is
8 is less than key of 7 which is again infinite. It implies we need to update the key of v7 to
8. Again, pick the vertex with minimum key not
in MSTset which is v1 in this case with key 4. Add it to mstSet.
Here, v2 and v7 are vertices adjacent to u. Now, we again see that weight of edge 1,2
which is 8 is less than the current key of v2. So,
key of v2 will be updated to 8. But on the other hand, weight of edge 1,7 is 11 whereas the
key of v7 is already 8. So, key of v7 won’t be updated.
Again, pick vertex with minimum key not in mstSet. Both v2 and v7 have lowest keys, so
you can add either to mstSet. Let’s add v7.
V8 and v6 are adjacent vertices of v7 not in mstSet. We’ll update their keys following
the same procedure as earlier.
Next vertex to pick is v6 which has the lowest key of 1.
V8 and v5 are vertices adjacent to our u i.e. v6. Weights of both v6v5 and v6v8 are less
than the keys of v5 and v8 respectively. Update
their keys too. Now, v5 will be picked because it has the
lowest key 2 among all the vertices not in mstSet.
Now, v5 has 3 adjacent vertices not in mstSet namely v2, v3 and v4. Keys of all the 3 will
Among the 4 vertices not in mstSet, v2 has the lowest key.
With v2 as u, we find its neighbouring vertices not in mstSet, v3 and v8 and update their keys following the same rule as always!
Now, v8 has the lowest key – 2. Add it to mstSet.
We see that v8 has no vertex adjacent to it not already a part of mstSet. Thus, no keys
will be updated in this case.
V3 will be picked now because it’s key is less than that of v4, which is the only other
vertex left not in mstSet.
To update the keys, consider the only adjacent vertex of v3, which is v4. Its weight is less than the current key of v4 which was 10. So,
set v4’s key to 9. Pick the last remaining vertex v4 and add
it to mstSet. Note that our condition says the procedure
will continue till all vertices are not part of mstSet. Since all the vertices are now added
to mstSet, we have reached the terminating condition.
Thus, we have successfully obtained the minimum spanning tree of the given graph. We can also calculate the weight of this MST by adding
the weight of individual edges in this tree. We see that they add up to 37. The time complexity
of Prim’s algorithm is O(V^2) if implemented using adjacency matrix and O(ElogV)
if done using adjacency list and binary heap.
Now, let’s analyse the code for Prim’s algorithm. This is an adjacency matrix implementation of the algorithm. Let’s start with the main
function. We’ve initialized the graph with the following matrix. The graph contains 5 vertices
0 to 4. Here, 2 represents theres an edge between vertex 0 and 1 with weight 2, 6 represents
an edge between vertex 0 and 3 and so on. Now, we call this function. Parent array
stores our constructed MST. Key stores the key value of v, and mstSET keeps track of vertices
not yet included in the MST. Initially, we set key of all vertices as infinite and none of
them belong to mstSet yet. Then we set the key of source as 0 and it’s parent as -1 because
it doesn’t have any parent. Now, the 1 st line in this for loop picks the vertex u with minimum key
not in MST. Let’s see the function. It says that if the vertex has not yet been added to mstSet
and if it’s key is minimum, pick this vertex as u. Now, mstset[u]=true adds u to mstSet. In
the next for loop, we check for each vertex that if graph[u][v] is not 0 i.e. if u and v are
adjacent vertices and v is not yet added to mstSet, we check if weight(u,v) is less than current
key of v, we update the key of v as weight of u,v. And set v’s parent as u. Finally, this printMST
function will be called which prints the vertex u, vertex v and weight of edge u,v for each edge
in MST. Thank you for watching the video. Please leave
us your comments!