Day-21: Prim's Minimum Spanning Tree Algorithm

Day-21: Prim's Minimum Spanning Tree Algorithm

Prim’s MST algorithm is a good example of how powerful Greedy problem solving paradigm can be.

The algorithm assigns key values to every node and chooses one to start with.

In every iteration, the algorithm adds a new edge to the existing MST(firstly just one vertex).

The edge is of the smallest length.

Finally, we get an MST.

Time complexity: O(ElogV) However, in my implementation, as I did not use a priority queue, complexity becomes O(V^2)

Here is the link of my C++ implementation of Prim’s Algorithm: Prim’s Algorithm

Author face

Abdurrezzak Efe

Bilkent University Bachelor's in CS 2018'

Recent post