Prim Minimum Spanning Tree Algorithm
Note
Now all the plugins has supported English. I'm still improving the website...
This article will resolve
| LeetCode | Difficulty |
|---|---|
| 1135. Connecting Cities With Minimum Cost🔒 | 🟠 |
| 1584. Min Cost to Connect All Points | 🟠 |
Prerequisites
Before reading this article, you need to study:
This article introduces Prim's algorithm, which, like the previously covered Kruskal's algorithm, is a classic minimum spanning tree algorithm. Before diving into this article, it is recommended that you read the earlier piece on Kruskal's Minimum Spanning Tree Algorithm to understand the basic definition of a minimum spanning tree and the principles of Kruskal's algorithm. This prior knowledge will make it easier to grasp the logic of Prim's algorithm.
Comparing Kruskal's Algorithm
The Minimum Spanning Tree (MST) problem in graph theory requires you to find a set of edges mst from a graph that has the following properties:
- The edges form a tree (the difference between a tree and a graph is that a tree cannot contain cycles).
- The tree must include all the nodes.
- The sum of the edge weights must be as small as possible.
So how does Kruskal's algorithm meet these conditions to compute the MST?
First, Kruskal's algorithm uses a greedy approach to ensure that the sum of the weights is as small as possible:
It sorts all the edges by weight in ascending order and starts by selecting the edge with the smallest weight, adding suitable edges to the mst set. The tree formed by these selected edges will have the minimum possible weight.
There is a specific criterion for selecting edges: if the two nodes of an edge are already connected, adding this edge would create a cycle in the mst set. If the final number of connected components is greater than one, it means that multiple trees (a forest) have been formed instead of a single MST.
Therefore, Kruskal's algorithm uses the Union-Find data structure to ensure that the selected edges form a tree without cycles or creating a forest.
Now, how does Prim's algorithm compute the MST?
First, Prim's algorithm also uses a greedy approach to minimize the total weight of the tree, which is based on the "cut property," explained in detail later.
Second, Prim's algorithm uses the BFS algorithm and a visited boolean array to avoid cycles, ensuring that the final selection of edges forms a tree.
Prim's algorithm does not require pre-sorting of all edges but uses a priority queue to dynamically sort them. Therefore, I think Prim's algorithm is similar to a dynamic version of Kruskal's algorithm.
Next, let's introduce the core principle of Prim's algorithm: the cut property.