最小生成树（MST）的克鲁斯卡尔算法 | 图论

1. 字幕依据
   观察依据

   黑板上写着：“设 G 是一个阶为 n 的连通赋权图。”

2. 声音
   观察依据

   讲解者说：“设 G 是一个阶为 n 的连通赋权图。”

G

应用克鲁斯卡尔算法的连通赋权图。

连通赋权图

1. 字幕依据
   观察依据

   黑板在前提陈述中使用了“阶为 n”这一表述。

2. 声音
   观察依据

   讲解者解释说，这意味着该图有 n 个顶点。

n

图的阶，即顶点的个数。

正整数顶点个数

1. 字幕依据
   观察依据

   黑板上写着：“克鲁斯卡尔算法以如下方式求出一棵最小生成树 T。”

2. 声音
   观察依据

   讲解者说，该算法求出一棵最小生成树，记为 T。

T

由克鲁斯卡尔算法生成的最小生成树。

G 的子图

1. 声音
   观察依据

   讲解者指出，一个含有 n 个顶点的图的生成树将有 n 减1条边。

2. 字幕依据
   观察依据

   黑板上的第4步写道：“重复执行3，直至已选出 n 减1条边。”

n-1

任意 n 个顶点的图的生成树中的边数，亦即该算法的终止计数值。

整数边数

1. 图示
   观察依据

   所给例题图展示了五个标号顶点 u、v、w、x、y。

2. 声音
   观察依据

   讲解者将“此处这个图”作为运行该算法的示例。

u, v, w, x, y

例题图中用于演示克鲁斯卡尔算法的顶点标号。

例题图的顶点

1. 公式
   观察依据

   书面算法反复提及图 G 的边。

2. 声音
   观察依据

   讲话者指出要选择图 G 中权重最小的一条边。

G

克鲁斯卡尔算法正在其上进行演示的带权图

顶点为 u、v、w、x、y 的带权无向图

1. 图示
   观察依据

   左侧图与右侧复制的顶点集均标有 u、v、w、x、y。

2. 声音
   观察依据

   讲话者依次命名了连接 u 与 v、y 与 x、w 与 v、u 与 w、以及 u 与 x 的边。

u, v, w, x, y

示例图的这五个顶点

图 G 的顶点集

1. 公式
   观察依据

   步骤4写作：重复执行3，直至已选出 $n-1$ 条边。

2. 声音
   观察依据

   讲话者解释说，n 表示该图的顶点个数。

n

图中顶点的个数

正整数；此处 $n=5$

1. 图示
   观察依据

   绿色数字标在左侧图中各条边的旁边。

2. 声音
   观察依据

   说话者称，每条边的权重以绿色数字标在其旁边。

edge weight

为每条边分配的数值代价，用于选取最小权重的边。

可见的数值包括1、2、3、4、5、6、7。

1. 公式
   观察依据

   书面算法文本反复使用符号 G，例如在“选择图 G 的一条边”等短语中，随后又写道：“设 G 是一个 n 阶连通赋权图。”

G

应用克鲁斯卡尔算法的连通赋权图。

连通赋权图

1. 公式
   观察依据

   算法文本写道：“重复执行3，直至已选出 $n-1$ 条边。”

2. 公式
   观察依据

   在步骤67.5处，屏幕显示：“设 G 是一个 n 阶连通赋权图。”

n

图 G 的阶，即图中顶点的个数。

正整数

1. 声音
   观察依据

   讲解员说道：“若将这棵生成树记作 T，则 T 的权 $W(T)$ 等于10。”

2. 公式
   观察依据

   屏幕在第一个例题中显示 $W(T)=10$，在第二个例题中则显示 $W(T)=21$。

T

例题中由克鲁斯卡尔算法所生成的最小生成树。

图 G 的一棵树子图

1. 字幕依据
   观察依据

   顶部文字为：“克鲁斯卡尔算法用于在连通带权图中求最小生成树。”

2. 声音
   观察依据

   讲解者再次强调：克鲁斯卡尔算法用于在连通带权图中求最小生成树。

视频将克鲁斯卡尔算法的适用场景定义为连通带权图，并指出该算法的输出是该图的一棵最小生成树。

1. 输入图是连通的。

2. 输入图是带权的。

3. 期望输出是一棵最小生成树。

1. 声音
   观察依据

   讲解者指出：一个含有 n 个顶点的图的生成树将有 n 减 1 条边。

2. 字幕依据
   观察依据

   后续第 4 步明确使用了“直到已选出 n 减 1 条边”这一条件。

对于阶数为 n 的图，任意生成树恰好包含 n 减 1 条边。视频利用这一事实来说明克鲁斯卡尔算法何时可以终止。

1. T 是一个含有 n 个顶点的图的生成树。

1. 克鲁斯卡尔算法的适用范围

1. 声音
   观察依据

   讲解者说：“请记住，根据定义，生成树必须包含原图的所有顶点。”

在将算法应用于示例之前，视频提醒观众：生成树需包含原图的每一个顶点；该算法仅选择保留哪些边，以使总权重最小。

1. 所选子图是原图的一棵生成树。

1. 克鲁斯卡尔算法的适用范围

1. 字幕依据
   观察依据

   黑板上的第1步写着“选择图G中权值最小的一条边”。

2. 声音
   观察依据

   讲解者说明，若有多条边的权值并列最小，则任选其中一条作为生成树的第一条边。

Kruskal算法的第一步是从图中选出权值最小的一条边；若存在多条边共享该最小权值，则可任选其中一条作为生成树的第一条边。

1. 在连通的带权图G中进行操作。

2. 从图G的所有边中，选出权值达到最小的一条边。

1. 克鲁斯卡尔算法的适用范围

1. 字幕依据
   观察依据

   黑板上的第2步写着“选择图G中尚未选取的、权值最小的一条边”。

2. 声音
   观察依据

   讲解者指出，应再选一条尚未选取的、权值最小的边，作为生成树的第二条边。

在第一条边选定之后，算法从剩余未选的边中再选出一条权值最小的边，这条边成为生成树的第二条边。

1. 已选定一条边。

2. 从未被选中的边中，选出一条权值最小的边。

1. Kruskal算法的第1步：选择一条权值最小的边

1. 字幕依据
   观察依据

   黑板上的第3步写道：“从图G的剩余边中任选一条权重最小的边，且该边与此前已选边不构成环。”

2. 声音
   观察依据

   讲解员解释道：一旦已有两条边，再添加任意一条边都可能形成环，而树不能含有环。

从第三条边开始，算法反复在剩余边中选择一条权重最小的边，前提是将其加入后不会与已选边构成环。这一环限制是合理的，因为树不能包含环。

1. 至少已有两条边被选出。

2. 在剩余边中，选择一条权重最小的边，且该边与当前已选边集合不构成环。

1. Kruskal算法的第2步：选择下一条尚未选取的、权值最小的边
2. 生成树的边数

1. 字幕依据
   观察依据

   黑板上的第4步写道：“重复步骤3，直至已选出n-1条边。”

2. 声音
   观察依据

   讲解员指出：重复执行第3步，直至选出n减去1条边，从而得到一棵最小生成树。

最后的操作指令是：持续执行这种避免成环的最小权重边选择操作，直到算法共选出n-1条边；此时所选边构成一棵最小生成树。

1. 继续执行第3步。

2. 当恰好选出n-1条边时停止。

1. Kruskal算法的第3步：仅当新边不会导致环时，才添加权重最小的边
2. 生成树的边数

1. 公式
   观察依据

   黑板上列出了四个步骤：1．选取图G中权重最小的一条边。2．从图G中剩余边里选取一条权重最小的边。3．从图G中剩余边里任选一条权重最小的边，要求该边与此前已选边不构成环。4．重复步骤3，直至已选出$n-1$条边。

2. 声音
   观察依据

   说话者按顺序朗读并应用这些步骤，同时构建生成树。

该视频片段将Kruskal算法呈现为一种贪心的边选择方法：首先选取全局权重最小的边，然后从剩余边中再选取一条权重最小的边，接着持续从剩余边中选取权重最小的边——但仅当该边不会与已选边构成环时才被接受，如此重复，直至选出$n-1$条边。

1. 图G是带权图。

2. 候选边按其权重非递减顺序被依次考虑。

3. 若某候选边与此前已选边构成环，则该边被拒绝。

4. 该过程在选出$n-1$条边后停止。

1. 公式
   观察依据

   第4步明确指出有 n 减1条边。

2. 声音
   观察依据

   主讲人解释说，边的数量比顶点数量少一条，因为此时我们已经完成了生成树的构建。

3. 公式
   观察依据

   主讲人为本例写出等式：5减1等于4。

视频利用了如下事实：一旦在不形成环的前提下选出了 n 减1条边，生成树即告完成。对于图中展示的含五个顶点的图，这意味着恰好需要四条边。

1. 所选的边构成了一个含 n 个顶点的图的生成树。

2. 本例中 n 等于5，因此目标边数为4。

1. 黑板上展示的Kruskal算法过程。

1. 公式
   观察依据

   屏幕列出步骤4：“重复执行3，直至已选出 n-1 条边。”

2. 声音
   观察依据

   讲解员说道：“当已有 n 减一 条边，或已有四条边时，我们即可停止，此时已得到一棵最小生成树。”

克鲁斯卡尔算法在选出 n-1 条边后停止；此时所选边构成连通加权图 G 的一棵最小生成树。

1. G 是一个连通加权图

2. n 是图 G 的顶点数

1. 用于最小生成树的克鲁斯卡尔算法

1. 声音
   观察依据

   讲述者说：“如果我们称这棵树为 T，那么 T 的权值 $W(T)$ 等于10。这只是各条边权值之和，即2加4加1加3。”

2. 公式
   观察依据

   屏幕在提取出的树旁显示：$W(T)=10$。

生成树 T 的权值，是属于 T 的所有边的权值之和。在第一个例子中，所展示的树的各条边权值分别为2、4、1和3，因此其总权值为10。

1. T 是一个带权图的生成树

2. $w(e)$ 表示边 e 的权值

1. 用于最小生成树的克鲁斯卡尔算法

1. 公式
   观察依据

   屏幕显示完整算法文字：“克鲁斯卡尔算法用于在连通带权图中寻找最小生成树。设 G 是一个阶数为 n 的连通带权图。克鲁斯卡尔算法按如下方式构造 G 的最小生成树 T：1。选取 G 中权值最小的一条边2。选取 G 中剩余边中权值最小的一条边3。选取 G 中剩余边中权值最小的一条边，且该边与此前已选边不构成环4。重复步骤3，直至已选出 $n-1$ 条边。”

2. 声音
   观察依据

   讲述者总结道：“这就是用于寻找最小生成树的克鲁斯卡尔算法。”

克鲁斯卡尔算法通过反复选取一条尚未被选、且与已选边不构成环的最小权值边，来构造最小生成树，并持续进行，直至已选出 $n-1$ 条边。

1. G 是一个连通带权图

2. n 是 G 的阶数

1. 声音
   观察依据

   讲述者指出，一个含有 n 个顶点的图的生成树将有 n 减去1条边，因此该算法在选出 n 减去1条边后即可停止。

2. 字幕依据
   观察依据

   后续写出的步骤4使用了相同的停止条件。

对于一个阶数为 n 的图，Kruskal 算法在选出 n 减去1条边后即可停止，因为一个含 n 个顶点的生成树恰好有 n 减去1条边。

1. 该图有 n 个顶点。

2. 所选的边旨在构成一棵生成树。

针对一个阶数为 n 的连通赋权图。

1. 声音
   观察依据

   主讲人指出，此时可任选一条权重最小的边，因为仅凭两条边绝不可能构成环。

在选出第一条边后，第二小权重的边可直接选取，无需检查是否成环，因为在本演示的构造中，仅靠两条边本身不可能形成环。

1. 截至目前，仅选出了两条边。

2. 演示中将该图视为一个简单无向图。

在本例的当前阶段，即步骤1之后、步骤3之前

1. 公式
   观察依据

   黑板上的步骤4写道：重复执行步骤3，直至已选出 $n-1$ 条边。

2. 声音
   观察依据

   主讲人解释，此时生成树已完成。

该算法不断重复避开环路的选择步骤，直至已选出 $n-1$ 条边；此时生成树即告完成。

1. n 表示图的顶点个数。

2. 所选边均依据前述最小权重且不形成环路的规则选出。

针对本例中的图 G，以及黑板上所写的通用过程

1. 声音
   观察依据

   讲解者称该树的权值为10，并将其解释为2加4加1加3。

2. 公式
   观察依据

   屏幕上显示 $W(T)=10$。

对于第一个展示的含5个顶点的带权图，Kruskal算法所提取出的树总权值为 $W(T)=10$，且该图的任何生成树都不具有更小的权值。

1. 左侧所示的图是输入图

2. 右侧的树是Kruskal算法的输出结果

3. 各边的权值即图中标注的数值

针对第一个示例中展示的具体图。

1. 声音
   观察依据

   讲述者问道：“你的树的权重是多少？我的树的权重是21，当然你的树的权重也应如此，因为最小权重是唯一的。”

2. 公式
   观察依据

   屏幕上显示 $W(T)=21$。

对于第二个展示的6个顶点的带权图，克鲁斯卡尔算法所找到的最小生成树总权值为 $W(T)=21$。

1. 所示图即为第二个已解示例。

2. 算法按屏幕上所述方式执行。

针对第二个示例中展示的具体图。

1. 声音
   观察依据

   讲解者说：“请记住，该算法可能对同一张图生成不同的最小生成树，因为在某些步骤中，需在权值相同的候选边之间任意选择。但本图不会出现这种情况，因此你的最小生成树应与下图一致。”

当存在权值相同的候选边时，克鲁斯卡尔算法可能对同一张图生成不同的最小生成树；但第二个示例图不存在此类平局情况，因此所得生成树在所示结构意义上是唯一确定的。

1. 该图是带权图。

2. 选择过程中，边的最小权重可能相等

存在某些带权图，使得不同的合法并列选择会导致不同的最小生成树；对于视频中展示的第二个示例图，视频指出这种情况不会出现。

1. 声音
   观察依据

   讲解者说：“在后续视频中，我们将实际证明该算法的正确性，因此我们可以100%确信它能完成预期功能。”

本视频并未证明克鲁斯卡尔算法；而是说明将在后续视频中证明该算法的有效性。

1. 本片段属于一个系列

针对本片段中介绍的算法。

1. 声音
   观察依据

   讲述者指出，在选出两条边之后，再添加任意一条边都可能形成环，而树不能含有环。

2. 字幕依据
   观察依据

   步骤3被表述为：选择一条剩余的最小权重边，且该边与之前已选边不构成环。

1. 公式

   $$$$
   解释

   该算法首先选出一条最小权重边，然后选出一条剩余边中权重最小的边。

   步骤依据

   这些是黑板上写出并口头念出的步骤1和2。

   视频直接表达
2. 公式

   $$$$
   解释

   一旦已选定两条边，第三条边就可能与它们构成一个环。

   步骤依据

   这是叙述者在前两次选择之后引入新限制的明确理由。

   视频直接表达
3. 公式

   $$$$
   解释

   由于树不能包含环，算法必须拒绝任何会导致成环的候选边。

   步骤依据

   这源于树的定义，并在叙述中被明确引用。

   视频直接表达

因此，步骤3添加了如下规则：每条后续的最小权重边仅当它不与先前已选边构成环时才被接受。

1. 声音
   观察依据

   主讲人口述每一次选择：权重为1的边 uv，权重为2的边 yx，权重为3的边 wv；因会形成环路而拒绝权重为4的边 uw；并选择权重为4的边 ux。

2. 图示
   观察依据

   右侧重复出现的顶点按相同顺序累积已选边。

3. 公式
   观察依据

   黑板上显示停止计数：$5-1=4$。

1. 公式

   $$$$
   解释

   执行步骤1：遍历所有边，选择权值最小的边。

   步骤依据

   黑板上写着：选择图G中权值最小的一条边。

   视频直接表达
2. 公式

   $$uv,\quad w(uv)=1$$
   解释

   所选的第一条边是连接顶点u和v、权值为1的边，它被添加到右侧的生成树中。

   步骤依据

   这是图中可见的最小边权值。

   视频直接表达
3. 公式

   $$$$
   解释

   执行步骤2：选择一条剩余边中权值最小的边。

   步骤依据

   黑板上写着：选择图G中一条剩余边，且该边权值最小。

   视频直接表达
4. 公式

   $$yx,\quad w(yx)=2$$
   解释

   所选的第二条边是连接顶点y和x、权值为2的边，它被添加到右侧的树中。

   步骤依据

   它是当前剩余可见边中的最小权值；说话者指出，仅凭两条边尚无法构成环。

   视频直接表达
5. 公式

   $$$$
   解释

   执行步骤3：选择一条剩余边中权值最小、且与已选边不构成环的边。

   步骤依据

   黑板上写着：选择图G中任意一条剩余边，要求其权值最小，且与之前已选边不构成环。

   视频直接表达
6. 公式

   $$wv,\quad w(wv)=3$$
   解释

   所选的第三条边是连接顶点w和v、权值为3的边，它被添加到右侧的树中。

   步骤依据

   说话者明确指出，该边不会与之前已选的边构成环。

   视频直接表达
7. 公式

   $$5-1=4$$
   解释

   计算生成树所需的总边数。

   步骤依据

   该图有 $n=5$ 个顶点，算法在添加 n-1 条边后停止。

   视频直接表达
8. 公式

   $$$$
   解释

   检查剩余的最小权重候选边，以确定第四条边。

   步骤依据

   步骤3必须重复执行，直至已选出四条边。

   视频直接表达
9. 公式

   $$uw,\quad w(uw)=4$$
   解释

   连接 u 和 w 的边权重为4，但被拒绝。

   步骤依据

   主讲人指出，选择该边将在已选边中形成环。

   视频直接表达
10. 公式

    $$ux,\quad w(ux)=4$$
    解释

    连接 u 和 x 的边权重为4，并被选为第四条边。

    步骤依据

    它是唯一剩余的、不构成环的最小权重边。

    视频直接表达

对于本例中的图，该算法恰好选出四条边：uv、yx、wv 和 ux，从而生成右侧所画的生成树。

1. 声音
   观察依据

   讲解者口头计算权重为2加4加1加3。

2. 公式
   观察依据

   屏幕上在提取出的树旁显示 $W(T)=10$。

3. 图示
   观察依据

   右侧的树上标出各边权重为2、4、1和3。

1. 公式

   $$W(T)=2+4+1+3$$
   解释

   将提取出的树中四条边的权重相加。

   步骤依据

   根据定义，生成树的权重是其所有边权重的总和。

   视频直接表达
2. 公式

   $$W(T)=10$$
   解释

   该求和结果为10。

   步骤依据

   对屏幕上显示的各边权重进行算术运算。

   视频直接表达

第一个例子中的最小生成树总权重为10。

1. 声音
   观察依据

   讲解者说道：“我的生成树权重是21。”

2. 公式
   观察依据

   屏幕上显示 $W(T)=21$。

3. 图示
   观察依据

   右侧最终呈现的生成树包含对应权重为1、2、3、4和11的边。

1. 中间加法过程以最终数值形式口述，而非在屏幕上完整写出。

1. 公式

   $$W(T)=1+2+3+4+11$$
   解释

   将屏幕上所示生成树中五条边的权重相加。

   步骤依据

   依据生成树权重的定义，即所有边权重之和。

   依据视频推导
2. 公式

   $$W(T)=21$$
   解释

   总和为21，与屏幕上所写及讲解者口述的数值一致。

   步骤依据

   算术求值。

   视频直接表达

第二个例子的最小生成树总权重为21。

1. 声音
   观察依据

   叙述者说：“为了让这个算法更具体，我们来在这个图上运行它。”

2. 图示
   观察依据

   左侧显示一个含五个顶点的带权图，右侧则显示同一五个顶点的孤立副本。

3. 字幕依据
   观察依据

   算法步骤仍粘贴在示例上方以供参考。

1. 该片段在任何边实际被选定或拒绝之前即结束，因此本段未完成完整演算过程。

2. 部分边的权重在采样帧中视觉上难以辨认，但清晰可读的数值包括：uv=1、vx=2、wy=3、uw=4、xy=5、yv=5、xw=6；其余显示的权重分别为边ux、vw和yx上的4、7和7。

对所示的五个顶点u、v、w、x、y的带权图应用Kruskal算法。

1. 该图的顶点为 u、v、w、x、y。

2. 可见的边权值为 uv=1、vx=2、wy=3、uw=4、ux=4、xy=5、yv=5、xw=6、vw=7、yx=7。

3. 算法步骤显示在图的上方。

4. 右侧展示了相同的五个孤立顶点，准备用于构建生成树。

开始演示克鲁斯卡尔算法如何从该图中选取边，以构成一棵最小生成树。

1. 公式

   $$$$
   解释

   视频将纯文本的初始设定替换为一个具体的图示例，同时保持算法步骤始终显示在图的上方。

   步骤依据

   讲解员明确指出，该示例旨在使算法更具体、更直观。

   视频直接表达
2. 公式

   $$$$
   解释

   左侧图是原始带权图；右侧则将相同顶点彼此分离地展示，作为生成树的构建场所。

   步骤依据

   这一点可直接从图示布局中看出。

   视频直接表达
3. 公式

   $$$$
   解释

   在开始选择边之前，讲解员提醒观众：生成树必须包含原图的所有顶点。

   步骤依据

   这句话出现在该片段结尾处的音频中。

   视频直接表达

本片段未生成最终的生成树；该段仅完成示例设定，并在执行算法前再次陈述其步骤。

视频片段在讲解者尚未完成示例介绍时就已结束，因此对最终最小生成树（MST）的验证超出了所提供的时段范围。

1. 图示
   观察依据

   左侧展示了一个含顶点 u、v、w、x、y 的带权图，右侧则使用一组相同的顶点来构建生成树。

2. 声音
   观察依据

   主讲人针对此图逐步演示该算法。

3. 公式
   观察依据

   图中可见的边权重包括1、2、3、4、5、6、7，且写有终止计算式$5-1=4$。

1. 图中部分边的标签在视觉上存在歧义，但口述讲解明确指出了所选的边 uv、yx、wv 和 ux。

2. 尽管第四条边已被选出，但在本片段结束前，完整的最终生成树并未通过口头方式总结。

对所展示的带权图 G（其顶点为 u、v、w、x、y）运行克鲁斯卡尔算法，并在右侧的顶点副本集合上构建生成树。

1. 图 G 有5个顶点：u、v、w、x、y。

2. 边的权重以绿色数字标在对应边旁。

3. 算法步骤写在黑板上。

4. 右侧包含一组顶点的副本，用于记录已选中的边。

按权重递增顺序选取边，同时避免形成环，直至选出 $n-1$ 条边。

1. 公式

   $$$$
   解释

   从步骤1开始，在整个图中找出权重最小的边。

   步骤依据

   黑板上的第一条指令是：选取图 G 中一条权重最小的边。

   视频直接表达
2. 公式

   $$uv\text{ with weight }1$$
   解释

   选择顶点 u 与 v 之间的边，并将其画在右侧的生成树中。

   步骤依据

   主讲人指出这是权重最小的边。

   视频直接表达
3. 公式

   $$$$
   解释

   转到步骤2，并选择一条剩余的最小权重边。

   步骤依据

   黑板上的第二条指令是：从图G中选出一条剩余的最小权重边。

   视频直接表达
4. 公式

   $$yx\text{ with weight }2$$
   解释

   选择y与x之间的边，并将其加入右侧的树中。

   步骤依据

   主讲人称这是当前剩余边中权重最小的一条，并指出此时两条边尚不足以构成环。

   视频直接表达
5. 公式

   $$$$
   解释

   转到步骤3，且仅考虑那些不会形成环的剩余最小权重边。

   步骤依据

   黑板上的第三条指令增加了“不得成环”的条件。

   视频直接表达
6. 公式

   $$wv\text{ with weight }3$$
   解释

   选择w与v之间的边，并将其加入右侧的树中。

   步骤依据

   主讲人明确检查了该边是否与之前已选的边构成环。

   视频直接表达
7. 公式

   $$5-1=4$$
   解释

   计算完成所需的边数。

   步骤依据

   共有$n=5$个顶点，算法在选出n-1条边后停止。

   视频直接表达
8. 公式

   $$$$
   解释

   在剩余的最小权重边中搜索第四条入选边。

   步骤依据

   步骤3必须重复执行，直到选出四条边。

   视频直接表达
9. 公式

   $$uw\text{ rejected}$$
   解释

   不要选择顶点 u 与 w 之间的边。

   步骤依据

   讲解者指出，这条边会与已选的边构成一个环。

   视频直接表达
10. 公式

    $$ux\text{ with weight }4$$
    解释

    在此片段中，选择顶点 u 与 x 之间的边作为所需的最后一条边。

    步骤依据

    它是唯一剩余的、权重最小且不会构成环的边。

    视频直接表达

本片段中构建的生成树包含边 uv、yx、wv 和 ux。

边的数量符合所写的停止规则$5-1=4$，右侧图示恰好展示了按顺序添加的这四条边。

1. 图示
   观察依据

   左侧展示了一个含5个顶点的带权图，其顶点为 u、v、w、x、y；右侧展示了从中提取出的树。

2. 公式
   观察依据

   屏幕上显示 $5-1=4$，且 $W(T)=10$。

3. 声音
   观察依据

   讲解者说明在选出四条边后停止，并将树的权重计算为 $2+4+1+3$。

对所展示的5个顶点的带权图应用克鲁斯卡尔算法，并确定所得最小生成树的权重。

1. 该图有5个顶点，因此 $n=5$。

2. 该算法需要选取 $n-1=4$ 条边。

3. 所示最终树的各边权重分别为2、4、1和3。

求出最小生成树并计算 $W(T)$。

1. 公式

   $$5-1=4$$
   解释

   计算需选取的边数。

   步骤依据

   克鲁斯卡尔算法在选出 $n-1$ 条边后停止。

   视频直接表达
2. 公式

   $$W(T)=2+4+1+3$$
   解释

   将所选树中各条边的权重相加。

   步骤依据

   生成树的权重是其所有边权重的总和。

   视频直接表达
3. 公式

   $$W(T)=10$$
   解释

   所得的最小生成树总权重为10。

   步骤依据

   直接根据图中显示的边权重进行算术计算。

   视频直接表达

该最小生成树的权重为10。

讲解者指出，其他生成树虽然存在，但没有任何一棵的权重小于10。

1. 图示
   观察依据

   一个含6个顶点的新加权图出现，其顶点为 u、v、w、x、y、z，边权重包括1、2、3、4、5、6、7、8、9和11。

2. 公式
   观察依据

   屏幕上显示 $W(T) = 21$。

3. 声音
   观察依据

   讲解者邀请观众运行该算法，随后指出其权重为21。

1. 本片段并未逐步完整口述边选择的确切顺序；仅清晰呈现了最终生成树及其总权重。

对第二个展示的带权图运行克鲁斯卡尔算法，并求出最小生成树的权重。

1. 该图有6个顶点

2. 最终展示的树的总权重为21

3. 讲解者指出，该图不会迫使人们任意选择平局边

求第二个图的最小生成树权重。

1. 公式

   $$\text{Apply Kruskal's algorithm to the 6-vertex graph}$$
   解释

   在避免形成环路的前提下，依次选取权重最小的边，直至选出5条边。

   步骤依据

   这是屏幕上所陈述的克鲁斯卡尔算法步骤。

   视频直接表达
2. 公式

   $$W(T)=21$$
   解释

   所得树的权重为21。

   步骤依据

   讲解者给出了该数值，屏幕也明确写出了该值。

   视频直接表达

最小生成树的权重为21。

讲解者指出，观众所构造的树应具有相同权重，因为该图只有一个最小权重值。

1. 图示
   观察依据

   屏幕仅显示黑底上的印刷体与手写文字，一个红色指针在“最小生成树”、“连通带权图”、“G”、“n”和“T”等词语上移动。

2. 字幕依据
   观察依据

   可见文字包括标题句以及设定语句：“设 G 是一个阶为 n 的连通带权图。Kruskal 算法以下述方式求出 G 的一棵最小生成树 T。”

1. 关于 Kruskal 算法的标题句

2. 手写设定行，定义了 G、n 和 T

3. 红色指针圆点

1. 红色指针在标题句和设定句中的关键词上移动。

2. 约在30秒处，表达式 n-1被写出并框出，位置靠近设定行。

1. 背景始终保持黑色。

2. 目前尚未出现任何图的绘制。

3. 数学内容始终聚焦于定义与符号表示。

这一可视化阶段在写出算法步骤之前，先确立问题背景与符号记号。

1. 图示
   观察依据

   在背景文字下方，出现四个带编号的手写步骤。

2. 字幕依据
   观察依据

   这些步骤的内容为：1. 选取图 G 中权值最小的一条边；2. 选取图 G 中剩余边中权值最小的一条边；3. 选取图 G 中剩余边中权值最小的一条边，且该边不与此前已选边构成环；4. 重复执行3，直至已选出 $n-1$ 条边。

3. 动画
   观察依据

   红色指针随着讲解者对每一步的解说，沿各行文字移动。

1. 从1到4的编号步骤

2. 红色指针圆点

3. 步骤上方的背景文字

1. 完整的算法以四个书面步骤的形式逐步呈现。

2. 指针着重强调不同短语，尤其是步骤3中的“不构成环”条件与步骤4中的“停止条件”。

1. 先前的背景文字在整个步骤区域上方持续可见。

2. 在此时间段的大部分时间内，未展示任何示例图。

视觉布局将文字描述转化为明确的有序步骤，突出强调贪心最小权重规则和无环性约束。

1. 图示
   观察依据

   左侧显示一个带权图，包含五个标有 u、v、w、x、y 的黄色顶点；右侧显示五个孤立的黄色顶点，标签相同。

2. 字幕依据
   观察依据

   算法步骤粘贴在示例图上方。

3. 动画
   观察依据

   一个蓝色圆圈在约95秒时短暂地围绕左侧图出现。

1. 视频片段在任何边被选入右侧生成树之前即结束。

2. 蓝色圆圈之后的确切视觉强调顺序受限于剩余时间较短。

1. 左侧为顶点 u、v、w、x、y 构成的带权图

2. 右侧为相同五个顶点的孤立副本

3. 粘贴在上方的算法步骤

4. 围绕左侧图的蓝色圆形高亮

1. 屏幕从纯文字讲解切换为具体的图示例题。

2. 左侧的图像暂时用蓝色圆圈标出，以引起注意。

3. 右侧的孤立顶点已准备好作为生成树构造的目标位置。

1. 算法步骤在示例上方始终保持可见。

2. 左右两侧的顶点标签一一对应。

3. 到本片段结束时，尚无边被转移到右侧。

这种视觉布局将源图与正在生长的生成树分离开来，使算法的选边过程更易于理解。

1. 图示
   观察依据

   屏幕分为左侧带权图、右侧重复的顶点集，以及顶部的算法文字。

1. 左侧带权图 G

2. 右侧重复的顶点 u、v、w、x、y

3. 顶部算法文字

1. 左侧图形始终作为候选边的来源。

2. 右侧始终作为已选边的记录位置。

3. 算法文字全程保持可见。

布局将输入图与输出的生成树分开，以便直观追踪每一次贪心选择。

1. 动画
   观察依据

   一个红色指针先移至步骤1，再移至左侧图形的底边，该边以紫色高亮显示。

2. 图示
   观察依据

   随后在右侧的u与v之间绘制一条白色边。

1. 步骤1的文字

2. 左侧图形中的边uv

3. 右侧的顶点u和v

1. 边uv在左侧被高亮显示。

2. 在右侧绘制一条对应的边。

1. 此时，其余边均未被选中。

该可视化序列通过选择权重为1的边 uv，来实现规则“选取图 G 中权重最小的一条边”。

1. 动画
   观察依据

   指针移至步骤2，然后移至 y 与 x 之间的边，该边以紫色高亮显示。

2. 图示
   观察依据

   在右侧，y 与 x 之间绘制了一条白色边。

1. 步骤2的文字

2. 左侧图中的边 yx

3. 右侧的顶点 y 和 x

1. 边 yx 在左侧图中被高亮显示。

2. 在右侧绘制了对应的边。

1. 此阶段未在视觉上执行环路检查。

这展示了第二个贪心选择，讲解者说明：仅含两条边时，尚不可能形成环路。

1. 动画
   观察依据

   指针移动到步骤3，然后移动到顶点 w 和 v 之间的边，该边以紫色高亮显示。

2. 图示
   观察依据

   在右侧绘制一条连接顶点 w 和 v 的白色边。

1. 步骤3的文字

2. 左侧图中的边 wv

3. 右侧的顶点 w 和 v

1. 边 wv 在左侧图中被高亮显示。

2. 在右侧绘制一条对应的边。

1. 之前已选中的边 uv 和 yx 保留在生成树中。

此可视化步骤展示了步骤3中新增的限制条件：仅当剩余边不会形成环路时，才选择其中权重最小的一条。

1. 动画
   观察依据

   步骤 3 被框出，然后第 1 步中的 4 被圈出。

2. 公式
   观察依据

   表达式$5-1=4$写在算法文字下方。

1. 方框标注步骤3

2. 圆圈标注$n-1$

3. 写出等式$5-1$＝4

1. 算法文字说明已加注，以强调重复性与终止性。

2. 数值目标4被明确写出。

1. 该图仍包含五个顶点。

2. 当前生成树在本次标注开始时仍含有三条边。

这些标注将一般规则$n-1$与具体实例联系起来，表明还需再添加一条边。

1. 动画
   观察依据

   指针指示尚存两条权重为4的边，随后边uw被标记为不可用，最后边ux被高亮并在右侧画出。

1. 用于拒绝uw的精确视觉标记较为简略，但口述解释清楚地将其识别为成环边。

1. 边 uw

2. 边 ux

3. 右侧树

1. 边 uw 被考虑但被拒绝。

2. 边 ux 在左侧被高亮显示，并在右侧被加入。

1. 此前已选的边 uv、yx 和 wv 保持不变。

这是关键的避环演示：在权重相等的最小权重候选边中，会导致成环的那条边被跳过，而另一条则被选中。

1. 图示
   观察依据

   左侧显示原始的5顶点图，其中若干条边以紫色高亮；右侧显示提取出的树，包含四条边，其权重分别为2、4、1和3。

2. 动画
   观察依据

   右侧的树被画上白色轮廓，红色圆点在讲解过程中短暂标记所选的边。

1. 原始的5个顶点的带权图

2. 提取出的4条边的树

3. 顶部显示算法文字

4. 方程$5-1=4$

5. 记号 $W(T)=10$

1. 右侧的树通过轮廓线在视觉上被单独凸显

2. 红色标记短暂高亮正在讨论的边

3. 树旁添加了权重记号 $W(T)=10$

1. 左侧的图始终保持为源图

2. 右侧的树始终保持为所选的生成树

3. 算法文字始终显示在上方

动画将所选的最小生成树与完整图区分开来，并直观地支持该树的总权重为10这一结论。

1. 图示
   观察依据

   屏幕切换为左侧一个含6个顶点的带权图，右侧为分散排列的带标签顶点，随后变为右侧完成的生成树。

2. 动画
   观察依据

   紫色高亮在左侧图的部分区域上扫过，右侧最终生成树则被白色轮廓线框出。

1. 仅凭采样画面，无法完全辨识边添加的确切顺序。

1. 第二个含6个顶点的带权图

2. 右侧分离的顶点标签

3. 右侧的最终生成树

4. 方程 $W(T) = 21$

1. 第一个例题被替换为一张新图

2. 右侧从彼此孤立的顶点逐步演变为一棵连通的树

3. 最终的树被勾勒出来，其权重写作21

1. 算法文字仍保留在屏幕上

2. 任务仍是寻找一棵最小生成树

视觉变化标志着一道练习题：对一个更大的图应用相同的算法，并验证其最小总权重为21。

1. 公式
   观察依据

   屏幕变为一张简洁的总结幻灯片，内容为：“克鲁斯卡尔算法可在连通的带权图中找到一棵最小生成树。设G是一个阶数为n的连通带权图。克鲁斯卡尔算法按如下方式在G中找出一棵最小生成树T：1。选取G中权重最小的一条边2。选取G中剩余边中权重最小的一条边3。选取G中剩余边中权重最小的一条边，且该边与此前已选边不构成回路4。重复步骤3，直至选出$n-1$条边。"

1. 仅含文字的克鲁斯卡尔算法总结

2. G、n和T的定义

1. 逐步演算的图示消失

2. 仅保留形式化的算法陈述

1. 算法步骤与此前屏幕上的文字完全一致

本片段以紧凑的形式化语言重述该方法作为结尾，并提及后续将给出证明及相关算法。

1. 声音
   观察依据

   讲解者指出：一旦选定了两条边，再添加任意额外的边都可能形成环，而树不能含有环。

人们可能会认为，在构建生成树的过程中，任何额外的低权重边都可以自由添加。

视频明确否定了这种想法：在前两条边选定之后，每新增一条边都必须检查其是否会导致成环，因为树不能含有环。

1. 声音
   观察依据

   讲解者提醒观众：按定义，生成树必须包含原图的所有顶点。

人们可能会将最小权重子图与生成树混淆，误以为可以遗漏某些顶点。

视频指出，生成树必须包含原图的所有顶点；而克鲁斯卡尔算法仅选择边以使总权重最小。

1. 声音
   观察依据

   讲解者指出，此时我们可以任选一条最小权重的边，因为仅凭两条边绝不可能构成环。

有人可能认为，每一条被选中的边——包括第二条边——都必须检验是否会导致成环。

视频明确指出，当仅选出两条边时，尚不可能形成环，因此第二小权重的边可直接选取。

1. 声音
   观察依据

   讲解者指出，最小权重的边有这两条，它们的权重均为4，但其中一条不能选取，因为它会导致成环。

当若干剩余边具有相同的最小权重时，人们可能认为其中任意一条都可自由选择。

该示例表明，即便在权重相等的候选边中，无环条件仍起决定作用：uw 被拒绝，而 ux 被选中。

1. 声音
   观察依据

   讲述者说：“只有一个最小权重”，随后澄清道：“该算法可能从同一张图中生成不同的最小生成树，因为在某些情况下，需要在权重并列最小的边之间任意选择。”

由于最小生成树的总权重是唯一的，人们可能会误以为该树本身也必定唯一。

视频区分了这两个概念：最小总权重是唯一的，但当存在多条权重并列最小的边时，为做出选择而不得不进行任意决定，就可能产生不同的最小生成树。

1. 声音
   观察依据

   讲述者说：“在后续视频中，我们将实际证明该算法是正确的。”

人们可能误以为视频已阐明克鲁斯卡尔算法为何总能返回一棵最小生成树。

本片段明确将正确性证明推迟至后续视频；此处仅介绍该算法，并通过示例加以说明。

1. 声音
   观察依据

   讲解者将边数 n-1与该算法的终止规则联系起来。

2. 字幕依据
   观察依据

   步骤4以 n-1作为终止条件。

克鲁斯卡尔算法第4步中的终止规则，依赖于这样一个事实：含 n 个顶点的生成树恰好有 n-1条边。

1. 声音
   观察依据

   讲解者通过指出树不能含有环，来为第3步提供依据。

第3步被明确定义，正是为了防止产生“可随意添加额外边而不顾是否成环”的错误想法。

1. 声音
   观察依据

   讲解者表示，引入该示例是为了让算法更具体、更直观。

2. 图示
   观察依据

   算法步骤被置于示例图的上方。

这个完整演算示例被呈现为对前述克鲁斯卡尔算法步骤的直接应用。

1. 声音
   观察依据

   讲解者指出，生成树包含原图的所有顶点。

2. 图示
   观察依据

   右侧显示了在开始选择边之前，全部五个顶点彼此孤立的状态。

理解为何全部五个顶点都被复制到右侧，取决于生成树的定义：它必须包含原图中的每一个顶点。

1. 公式
   观察依据

   步骤4指出：重复执行，直至已选出 $n-1$ 条边。

2. 声音
   观察依据

   主讲人将这一计数与生成树的完成联系起来。

该算法的停止规则直接利用了如下事实：含 n 个顶点的生成树包含 $n-1$ 条边。

1. 公式
   观察依据

   步骤3中包含短语“不与先前已选边构成环”。

2. 动画
   观察依据

   后续对 uw 的拒绝体现了该条件的实际应用。

该过程对比了早期阶段（仅选取两条边后尚无需检查是否成环）与后期阶段（此时避免成环变得至关重要）。

1. 公式
   观察依据

   总结文字指出，克鲁斯卡尔算法找到一棵最小生成树 T。

2. 声音
   观察依据

   讲述者总结道：“这就是用于寻找最小生成树的克鲁斯卡尔算法。”

克鲁斯卡尔算法被呈现为构造最小生成树所采用的方法。

1. 声音
   观察依据

   讲述者将 $W(T)$ 定义为各边权重之和，并在两个示例中均应用了该定义。

2. 公式
   观察依据

   屏幕上显示 $W(T)=10$，随后显示 $W(T)=21$。

生成树权重的定义被用于计算例题中的总和。

1. 公式
   观察依据

   该算法的第4步指出：重复执行，直至已选出 n-1 条边。

停止规则是克鲁斯卡尔算法完整描述中的一个组成部分。

1. 声音
   观察依据

   讲解者提到：“我在关于普里姆算法的课程中讲过，那是一种不同的、略微更复杂的求最小生成树的算法。”

本视频将克鲁斯卡尔算法与普里姆算法进行对比，后者是求最小生成树的另一种方法。

1. 字幕依据
   观察依据

   首句点明了克鲁斯卡尔算法和最小生成树。

2. 声音
   观察依据

   讲述者重复了同一句话。

1. 克鲁斯卡尔算法的适用范围

1. 声音
   观察依据

   讲述者解释了边数为 n-1 以及停止条件。

2. 字幕依据
   观察依据

   后续手写的步骤 4 将 n-1 条边作为终止判据。

1. 生成树的边数
2. Kruskal 算法的停止条件
3. Kruskal算法的第4步：重复执行，直至选出n-1条边

1. 字幕依据
   观察依据

   四个手写算法步骤完全可见。

2. 声音
   观察依据

   讲述者按顺序逐条朗读并解释每个步骤。

1. Kruskal算法的第1步：选择一条权值最小的边
2. Kruskal算法的第2步：选择下一条尚未选取的、权值最小的边
3. Kruskal算法的第3步：仅当新边不会导致环时，才添加权重最小的边
4. Kruskal算法的第4步：重复执行，直至选出n-1条边

1. 声音
   观察依据

   讲述者指出：在加入两条边之后，再添加任意一条边都可能形成环。

2. 字幕依据
   观察依据

   步骤 3 包含了无环条件。

1. Kruskal算法的第3步：仅当新边不会导致环时，才添加权重最小的边
2. 为何环检测从步骤3开始

1. 图示
   观察依据

   展示了一个包含五个顶点 u、v、w、x、y 的带权图。

2. 声音
   观察依据

   讲解者将其介绍为运行该算法所用的图。

1. 本片段中未完成完整演算过程。

1. 为讲解Kruskal算法而引入的示例图
2. 从抽象算法过渡到具体例题演示

1. 声音
   观察依据

   讲解者指出：根据定义，生成树必须包含原图的所有顶点。

1. 生成树必须包含所有顶点

1. 公式
   观察依据

   步骤3被明确写在黑板上。

2. 声音
   观察依据

   主讲人解释道：现在我们只需考虑那些不会产生环的边。

1. 黑板上展示的Kruskal算法过程。

1. 公式
   观察依据

   黑板上显示：重复执行3，直到已选出 $n-1$ 条边。

2. 声音
   观察依据

   主讲人解释说，所选边数比顶点数少一条，因为此时我们已构造出一棵生成树。

1. 一个含 n 个顶点的生成树具有 n 减1条边。
2. 该算法的停止条件

1. 声音
   观察依据

   主讲人指出，不能选择连接 u 和 w 的边，因为那样会形成环。

2. 动画
   观察依据

   边 uw 被标出，随后改选边 ux。

1. 黑板上展示的Kruskal算法过程。
2. 假设所有边的最小权重相等，意味着任一边始终有效

1. 声音
   观察依据

   主讲人指出，仅用两条边不可能构成环。

1. 在本次演示中，两条已选边无法构成环。

1. 公式
   观察依据

   完整的算法文字显示在屏幕上。

1. 用于最小生成树的克鲁斯卡尔算法
2. 克鲁斯卡尔算法的终止规则

1. 公式
   观察依据

   屏幕上显示“重复3，直至已选出 n-1 条边”，示例中写出 $5-1=4$。

1. 克鲁斯卡尔算法的终止规则