# Kruskal 最小生成树算法

Info

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

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

LeetCode | Difficulty |
---|---|

1135. Connecting Cities With Minimum Cost🔒 | 🟠 |

1584. Min Cost to Connect All Points | 🟠 |

261. Graph Valid Tree🔒 | 🟠 |

Prerequisites

Before reading this article, you should first learn:

Among the well-known algorithms in graph theory are Dijkstra's Shortest Path Algorithm, Cycle Detection and Topological Sorting, Bipartite Graph Detection Algorithm, and today's topic: the Minimum Spanning Tree (MST) algorithms.

The two main MST algorithms are Prim's Algorithm and Kruskal's Algorithm. Although both use the greedy approach, they differ significantly in their implementations.

In this article, we will first discuss the simpler and more understandable Kruskal's Algorithm. In the next article, Prim's Algorithm Template, we will cover Prim's Algorithm.

Kruskal's Algorithm is actually quite easy to understand and remember. The key is to be familiar with the Union-Find algorithm. If you're not familiar with it yet, I recommend reading our previous article on the Union-Find Algorithm.

Now, let's start with the definition of a Minimum Spanning Tree.

## What is a Minimum Spanning Tree

**First, the fundamental difference between a "tree" and a "graph": A tree does not contain cycles, while a graph can contain cycles**.

If a graph has no cycles, it can be stretched into the shape of a tree. To put it technically, a tree is an "acyclic connected graph."

So, what is a "spanning tree" of a graph? Literally, it is a tree that includes all the nodes of the graph. Technically speaking, a spanning tree is an "acyclic connected subgraph" that contains all the vertices of the graph.

It's easy to see that a graph can have many different spanning trees. For example, the red edges in the graph below form two different spanning trees:

In a weighted graph, each edge has a weight, so each spanning tree has a total weight. For example, in the graph above, the total weight of the spanning tree on the right is obviously less than that of the spanning tree on the left.

**Therefore, the minimum spanning tree is easy to understand: among all possible spanning trees, the one with the smallest total weight is called the "minimum spanning tree"**.

提示

Generally speaking, we calculate the minimum spanning tree in an **undirected weighted graph**, so in real-world scenarios where minimum spanning tree algorithms are used, the edge weights of the graph usually represent costs or distances.

Before discussing the Kruskal algorithm, we need to review the Union-Find data structure.