Trusted answers to developer questions

Muhammad Hasaan

**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.

- Randomly select a node as the root node and mark it as visited. Open all edges associated with the root node.
- From the opened edges, select the edge with the minimum weight. In case there are multiple edges with the same minimum weight, select any one.
- If both nodes in the selected edge are already marked visited, close that edge and go to step 2 again. Otherwise, continue to the next step.
- Add the selected edge to the MST and mark the edge nodes as visited. Open all closed edges associated with the visited nodes.
- If all edges are marked visited, terminate the algorithm. Otherwise, repeat step 2.

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.

RELATED TAGS

graph

spanning tree

CONTRIBUTOR

Muhammad Hasaan

RELATED COURSES

View all Courses

Keep Exploring

Related Courses