Kruskal’s Algorithm for Minimum Spanning Trees | 最小生成树 Kruskal 算法

📚 Kruskal’s Algorithm for Minimum Spanning Trees | 最小生成树 Kruskal 算法

In A-Level Computer Science, graph optimisation problems often ask for the cheapest way to connect all nodes in a network. Kruskal’s algorithm is a greedy method that builds a minimum spanning tree (MST) by adding the lowest-weight edges that do not form a cycle. This revision guide explains the algorithm step by step, gives a worked trace, compares it with Prim’s algorithm, and highlights common exam mistakes.

在 A-Level 计算机科学中，图优化问题经常要求找到连接网络中所有节点的最便宜方式。Kruskal 算法是一种贪心方法，通过添加不形成环的最低权重边来构建最小生成树 (MST)。本复习指南将逐步解释该算法，给出示例追踪，将其与 Prim 算法进行比较，并强调常见考试错误。

1. What is a Minimum Spanning Tree? | 什么是最小生成树

A spanning tree of a graph with V vertices is a connected subgraph that contains all V vertices and exactly V – 1 edges, with no cycles. If the original graph is weighted, a minimum spanning tree (MST) is a spanning tree whose total edge weight is as small as possible. Kruskal’s algorithm is one of the standard ways to find an MST.

对于含有 V 个顶点的图，生成树是包含所有 V 个顶点且恰好有 V – 1 条边的连通子图，并且没有环。如果原图带权，最小生成树 (MST) 就是总边权尽可能小的生成树。Kruskal 算法是寻找 MST 的标准方法之一。

Edges in an MST = V – 1

2. Core Idea of Kruskal’s Algorithm | Kruskal 算法核心思想

Kruskal’s algorithm builds an MST by considering edges in increasing order of weight. It starts with each vertex as a separate component. For each edge, if the two endpoints lie in different components, adding that edge cannot create a cycle, so it is selected and the components are merged. If the endpoints are already in the same component, the edge is discarded.

Kruskal 算法按照边权递增的顺序考虑边。它开始时将每个顶点视为一个独立的分量。对于每条边，如果两个端点位于不同的分量中，那么加入这条边不会形成环，因此选择它并合并分量。如果两个端点已经在同一分量中，则丢弃该边。

This greedy approach works because the cheapest edge that connects two separate components is always safe to include in some minimum spanning tree. The algorithm does not need to reconsider a rejected edge later.

这种贪心策略之所以有效，是因为连接两个不同分量的最便宜边总是可以安全地加入某个最小生成

Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）