证明最小生成树贪心算法必然终止及相关算法流程说明

Alright, let's break down why this greedy minimum spanning tree (MST) algorithm is guaranteed to terminate. First, let's restate the algorithm clearly for context:

算法步骤
初始化：B = ∅ —— 算法将构建的边集合；
当|B| < |V| - 1时执行：
a. 选择图中的某个割(S,V\S)，要求B中不存在跨越该割的边；
b. 找到跨越该割的权重最小的边；
c. 将该边加入集合B，即B = B ∪ {e}；
返回T = (V,B)

核心终止理由分析 #

We're working with a finite connected undirected graph G=(V,E) — this finiteness is the backbone of the termination proof. Here's the step-by-step breakdown:

• 初始状态与目标明确：We start with |B| = 0. A valid spanning tree on |V| vertices requires exactly |V| - 1 edges, so our target for |B| is a fixed, finite number.
• 每次循环的增量固定：Every iteration of the loop adds exactly one edge to B. That means |B| increases by 1 every time we go through the loop — no exceptions.
• 循环次数有明确上限：Starting from 0, we need at most |V| - 1 iterations to reach the target size of B. Since |V| is finite (it's the vertex set of our input graph), this is a finite number of steps.
• 每次循环都能找到有效边：We also need to confirm we never get stuck mid-loop (i.e., we can always find a valid cut and edge):
  • When |B| < |V| - 1, the edges in B form a forest (a group of disconnected trees) with at least two separate components. If we pick S as the vertex set of one of these components, the cut (S, V\S) has no edges from B crossing it — exactly what we need for step a.
  • Since the original graph G is connected, there must be at least one edge in E that crosses this cut. And because the set of crossing edges is finite, we can always find the minimum-weight one to add to B.

结论 #

Putting it all together: we start with an empty set, increment its size by 1 each finite step, stop when we hit our fixed target, and never get stuck unable to find an edge to add. The algorithm cannot run infinitely — it must terminate.

内容的提问来源于stack exchange，提问作者user12400828