Prim's Algorithm is an algorithm that takes a weighted undirected graph as an input and outputs its Minimum Spanning Tree (MST). At every step, it selects an open edge that has the minimum weight.
Note: The nodes in the graph must have no self-loops, and there should be no parallel edges.
Consider the graph above. Let’s run Prim’s algorithm on it.
Any node can be the root node. Let's go with node A as our root node and mark it as visited.
The edges associated with node A are opened. These include A-B, A-D, and A-C.
From the opened edges, the edge with the minimum weight A-D is added to the MST and D is marked as visited.
The edges D-B, D-E, and D-G are opened because of their association with node D.
The opened edge with the least weight, such as nodes, D-B is added to the MST and node B is marked as visited.
The only closed edge of node B, B-E is opened.
Two open edges have the minimum weight. Both B-E and D-E can be added to the MST. In this case, B-E was added to the MST and node E was marked as visited.
The edge E-G is opened.
E-G has the minimum weight among the opened edges so it is added to the MST. Node G is marked as visited.
The minimum weight edge is now D-E, but both D and E have been marked visited. Hence, the edge will be closed.
G-F, A-B and D-G all have the minimum weight. G-F is added to the MST and F is marked as visited.
F-C is opened because it is the last edge of E that is not opened.
The nodes in the minimum weight edge A-B are already visited. Therefore, it is closed.
Again, the nodes in the minimum weight edge D-G are already visited, thats why it is closed.
The minimum cost edge F-G is added to the MST and node C is marked visited. As all of the nodes have been visited, the algorithm stops.
The time complexity of Prim's algorithm is O(E log V) if a min-heap is used. Here, V is the number of vertices and E is the number of edges.
The space complexity of Prim's Algorithm is O(E+V). Here, V is the number of vertices and E is the number of edges.
View all Courses