# Prim 最小生成树算法

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

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.