Objective: In this lesson, we’ll deep-dive into one of the most widely used greedy algorithms – Prim’s algorithm. We’ll focus on:
- Defining the algorithm
- Going through a detailed step-by-step example on how the algorithm works
- The algorithm’s real-life applications
Prim’s algorithm was discovered by Vojtěch Jarník in 1930, and then republished in the 1950’s - first by Robert C. Prim, and then by Edsger W. Dijkstra. It is a greedy algorithm used for finding the minimum spanning tree for an undirected weighted graph. In order to understand this definition, let us first go through the terminology used in it:
Greedy Algorithm – it is a straightforward algorithm that tries to find the best solution by making the best possible decision with the most immediate benefit at each step. In other words, it works by making locally-optimal choices in order to eventually get to a globally-optimal solution.
Minimum Spanning Tree (MST) – a spanning tree of a graph connects all the vertices of a graph with the least number of edges possible. As such, this tree is always connected and never contains cycles. For a single graph, there exist multiple spanning trees. So, a minimum spanning tree is simply the spanning tree in which the sum of the edges (the cost) is the lowest.
Undirected Weighted Graph – an undirected graph is a collection of nodes called vertices (V) and links between them called edges (E). When we say that a graph is weighted, that means that there is a number associated with each edge that represents its weight.
Prim’s algorithm works best on connected, dense graphs. In the case of disconnected graphs, this algorithm might not be the best one to use, because, in order to find the minimum spanning forest, it must iterate over each connected component of the graph individually. A forest is a collection consisting of many separate trees.
The time complexity of the algorithm is O((V+E)*log(V)).
