Prim’s Algorithm:

Prim’s Algorithm and How It Works;

Prim’s algorithm employs a greedy algorithm to find the minimum spanning tree. In a greedy algorithm, the next item has always been selected that offers the most local optimal solution to the problem, in which making a choice locally optimum solution also leads to a global solution.

The series of steps for trying to implement Prim’s algorithm:

Get rid of all loops and parallel edges.
Start the minimum spanning tree from every vertex in the graph.
Find all the edges that connect the tree to new unvisited vertices, then find the shortest set of edges and add them to the tree.
The procedure should be repeated until we have a minimum spanning tree.

Prim’s Algorithm Time Complexity Analysis:

Prim’s Algorithm’s Worst Case Time Complexity is: –

Parallel algorithm:

Prim’s algorithm’s main loop is innately sequential and thus cannot be executed in parallel. The inner loop, which determines the next edge of minimum weight that does not form a cycle, on the other hand, can be executed in parallel by dividing the vertices and edges among the available processors.

Conclusion:

This algorithm also works with undirected connected graphs, but no negative edges are allowed. When applied to this type of graph, the algorithm is quite efficient. In the absence of non-negative weight cycles, the shortest path always exists.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store