Prim算法2分钟讲解

1. 字幕依据
   观察依据

   手写标题“Prim算法”显示在白板上。

2. 声音
   观察依据

   讲解者说：“本视频将向您展示在图上正确运行Prim算法的方法。”

Prim's Algorithm

本片段所演示的贪心最小生成树算法的名称。

图论／离散数学

1. 字幕依据
   观察依据

   标题下方，白板显示“最小生成树（MST）”，并有一条从“Prim算法”指向它的向下箭头。

2. 声音
   观察依据

   讲解者说：“Prim算法的结果是一棵最小生成树，即一个无环且连通的、总权重最小的图。”

MST

最小生成树的缩写，即Prim算法所生成的输出对象。

图论

1. 字幕依据
   观察依据

   在图示页面底部，白板最初显示“已访问 = { }”，随后随着节点被加入而不断更新该集合。

2. 声音
   观察依据

   讲解者说：“首先，创建一个名为‘已访问’的空列表。我们将用它来记录已被处理过的节点。”

Visited

已包含在不断生长的最小生成树中的顶点的跟踪集合／列表。

图遍历过程中算法所处的状态

1. 图示
   观察依据

   手绘图中包含七个标有字母 A、B、C、D、E、F 和 G 的圆形节点。

2. 声音
   观察依据

   讲解者在运行算法时，提到了特定的顶点，例如 A、B、C、F 和 G。

A, B, C, D, E, F, G

用于演示普里姆（Prim）算法的示例加权图的顶点标签。

示例图的顶点

1. 图示
   观察依据

   示例图中的边标有数字权重，包括1、2、3、4、5、6、7、8和9。

2. 声音
   观察依据

   讲解者通过比较边的权重反复选择边，例如“选择权重最小的边”以及“权重为3的边 BE”。

Edge weights

分配给边的数值代价；普里姆算法从已访问顶点集向未访问顶点集跨越的所有边中，选取权重最小的那条边。

带权无向图

1. 字幕依据
   观察依据

   黑板上写着“总边权 = $2 + 3 + 3 + 1 + 6 + 9 = 24$”。

2. 声音
   观察依据

   讲解者说：“你可以将所选边的权重相加，得到最小生成树的总边权。”

Total Edge Weight

所有被选入最小生成树（MST）的边的权重之和。

最小生成树的目标函数值

1. 字幕依据
   观察依据

   在时间复杂度页面上，黑板上写着 $O(V^2)$ 和 $O(V \log V + E \log V)$。

2. 声音
   观察依据

   讲述者开头说道：“时间复杂度取决于所用的数据结构”，表明这些公式描述的是与具体实现相关的运行时间。

1. 视频片段在讲述者口头解释 V 和 E 的含义之前就结束了。

V

图中顶点的数量，出现在所展示的时间复杂度表达式中。

图的规模参数

1. 字幕依据
   观察依据

   黑板上第二个复杂度公式写作 $O(V \log V + E \log V)$。

2. 声音
   观察依据

   讲述者在视频片段结束前刚刚引入时间复杂度这一主题。

1. 视频片段在讲述者口头明确给出 E 的定义之前就结束了。

E

图中边的数量，出现在所展示的时间复杂度表达式中。

图的规模参数

1. 公式
   观察依据

   在手写幻灯片中，V 出现在 $O(V^2)$ 和 $O(V \log V + E \log V)$ 中。

V

图中顶点的数量。

正整数。

1. 公式
   观察依据

   在手写幻灯片中，E 出现在 $O(V \log V + E \log V)$ 中。

E

图中边的数量。

非负整数。

1. 公式
   观察依据

   打印版伪代码的函数头写作 procedure prim(G,w)。

G

Prim 算法的输入图。

连通无向图 $G=(V,E)$。

1. 公式
   观察依据

   打印版伪代码的函数头写作 procedure prim(G,w)，且输入说明中提到了边权 $w_e$。

w

边权函数。

为每条边 e 分配一个权重 $w_e$。

1. 字幕依据
   观察依据

   标题卡片显示“Prim算法”，并带有一支箭头指向“最小生成树（MST）”。

2. 声音
   观察依据

   讲述者指出，本视频将演示如何执行Prim算法，并说明该算法最终得到一棵最小生成树。

普里姆算法被介绍为一种从带权图中构造最小生成树的方法。板书将该算法直接与最小生成树（MST）概念关联起来，而旁白将最小生成树定义为：一个无环的、连通的、总权重最小的图。

1. 适用于带权图。

2. 期望输出是一棵总权重最小的生成树。

1. 最小生成树的定义

1. 字幕依据
   观察依据

   板书在标题下方写出“最小生成树（MST）”。

2. 声音
   观察依据

   旁白说道：“最小生成树，即一个无环的、连通的、总权重最小的图。”

该片段将最小生成树定义为：一个连通、无环的子图，它包含原图的所有顶点，且所含边的总权重最小。这正是普里姆算法所生成的目标结构。

1. 图必须是连通的，生成树才可能存在。

2. 最小生成树使所选边的权重之和最小。

3. 最小生成树中不含任何环。

1. 字幕依据
   观察依据

   图示页面底部显示“已访问 = { }”。

2. 声音
   观察依据

   旁白提示：创建一个名为 visited 的空列表，用于记录已被访问过的节点。

Prim 算法维护一个已纳入生成树的顶点集合。在示例中，该集合以类似集合的对象“Visited”表示，并在每次选定新顶点并将其加入不断生长的树后更新。

1. 在 Prim 算法执行过程中使用。

2. 在首个顶点被选定前，该列表初始为空。

1. 普里姆算法的目的

1. 字幕依据
   观察依据

   另一块板书页面写着：“Prim = 任选一个节点”。

2. 声音
   观察依据

   旁白说：“下一步是任选一个节点。我们将从该节点启动算法。在本图中，我们从 A 开始。首先，将 A 加入 visited 列表。”

算法首先任选一个起始顶点。在本例演算中，顶点 A 被选定，并立即插入 Visited 集合，从而构成初始的树片段。

1. 起始顶点可任意选取。

2. 选定之后，起始顶点即被标记为已访问。

1. visited 列表/集合的作用

1. 声音
   观察依据

   旁白说：“接下来，检查所有从 A 可达的顶点……Prim 是一种贪心算法，因此我们将选择连接至未访问节点的最小权值边，本例中即为 A 到 B 的边。”

2. 图示
   观察依据

   从顶点A出发的边被高亮显示，其中权重为2的边A-B被圈出，随后作为最小生成树（MST）的一部分被涂成红色。

在每一轮迭代中，算法检查当前已访问顶点集合所关联的所有边，并从中选出一条权重最小、且通向尚未访问顶点的边；随后将该边及其新到达的顶点加入最小生成树。

1. 仅考虑从已访问顶点指向未访问顶点的横跨边。

2. 在这些候选边中，选择权重最小的一条。

3. 将该边以及新到达的顶点一并加入生成树。

1. Prim 算法的起始步骤
2. visited 列表/集合的作用

1. 声音
   观察依据

   旁白说道：“三条边的权重均为三。任选其中一条。我选择了添加边AC。”

2. 图示
   观察依据

   从已访问顶点集{A,B}出发，存在多条权重为3的候选边，接下来选择边A-C。

当多个候选边同时达到相同的最小权重时，算法可任选其一。在本例中，顶点集{A,B}已被访问，此时存在多条权重为3的边，演示者选择了边A-C。

1. 当多条横跨边共享最小权重时发生。

2. 任选一条权值并列的边，均不违背贪心规则。

1. 普里姆算法中的贪心选择规则

1. 声音
   观察依据

   旁白说：“注意此时，权值为3的边BE是最小权值边。但它的两个顶点都已在最小生成树中，因此我们不选择它。相反，我们将选择把F加入最小生成树。”

2. 图示
   观察依据

   边B-E保持蓝色/未选中状态，而算法转而选择了权值为6的边C-F。

普里姆算法仅接受那些连接已访问树部分与未访问顶点的边。即使某条边权值很小，只要它的两个端点都已在最小生成树中，该边就会被忽略，因为加入它将导致环路。

1. 候选边必须跨越已访问顶点与未访问顶点之间。

2. 位于已访问顶点集合内部的边将被舍弃。

1. 普里姆算法中的贪心选择规则
2. 最小生成树的定义

1. 声音
   观察依据

   旁白说：“唯一剩余的未访问节点是G，因此我们将它加入最小生成树。此时所有节点已通过一棵树彼此连通。”

2. 图示
   观察依据

   最终的红色最小生成树包含全部七个顶点A至G以及六条被选中的边。

该过程在每个顶点都被访问并纳入树中时停止。在本例中，最后一个未访问顶点G通过边F-G被接入，从而得到一棵覆盖所有顶点的连通无环生成树。

1. 持续进行，直至所有顶点都进入已访问集合。

2. 对于一个含n个顶点的连通图，其最小生成树包含n-1条边。

1. 普里姆算法中的贪心选择规则
2. 最小生成树的定义

1. 字幕依据
   观察依据

   黑板上写着“总边权 = $2 + 3 + 3 + 1 + 6 + 9 = 24$”。

2. 声音
   观察依据

   旁白说：“你可以将各条边的权重相加，得到最小生成树的总边权。”

在选定最小生成树的边之后，通过对这些边的权重求和即可得到总代价。示例中对所选的六条边求和，得到结果24。

1. 在最小生成树的边集确定之后应用。

2. 仅对包含在最小生成树中的边的权重求和。

1. 终止条件与完成的最小生成树

1. 字幕依据
   观察依据

   黑板标题为“时间复杂度”，列出两项：“邻接矩阵配合搜索 → $O(V^2)$”以及“二叉堆配合邻接表 → $O(V \log V + E \log V)$”。

2. 声音
   观察依据

   旁白说：“时间复杂度取决于所采用的数据结构。”随后片段结束。

1. 口头解释在旁白进一步阐述每种实现为何得出对应界之前被截断。

该片段指出，普里姆算法的运行时间取决于所选用的数据结构。展示了两种标准实现：使用邻接矩阵配合搜索时为 $O(V^2)$，而使用二叉堆配合邻接表时为 $O(V \log V + E \log V)$。

1. 第一个界对应邻接矩阵配合搜索的实现。

2. 第二个界对应于二叉堆加邻接表的实现。

3. V 表示顶点数，E 表示边数。

1. 普里姆算法的目的

1. 公式
   观察依据

   手写幻灯片标题：时间复杂度（邻接矩阵法），搜索 → $O(V^2)$。

幻灯片指出，当 Prim 算法采用邻接矩阵搜索实现时，运行时间为 $O(V^2)$，其中 V 表示顶点数量。

1. 实现采用邻接矩阵搜索。

2. V 表示顶点的数量。

1. V

1. 公式
   观察依据

   手写幻灯片行：二叉堆与邻接表 → $O(V \log V + E \log V)$。

幻灯片指出，当采用二叉堆与邻接表表示时，运行时间为 $O(V \log V + E \log V)$。其中 V 是顶点的数量，E 是边的数量。

1. 实现采用二叉堆。

2. 图以邻接表形式存储。

3. V 表示顶点的数量，E 表示边的数量。

1. V
2. E

1. 声音
   观察依据

   讲解者将最小生成树（MST）定义为“一个无环且总权重最小的连通图”。

2. 字幕依据
   观察依据

   黑板上将输出标注为“最小生成树（MST）”。

最小生成树是原图的一个连通、无环的生成子图，且其所有边的总权重最小。

1. 基础图是带权图。

2. 生成树存在，这要求图本身是连通的。

对于给定的带权连通图，最小生成树是所有生成树中总权重最小的那个生成子图。

1. 声音
   观察依据

   讲解者说：“注意，若所有边的权重互不相同，则该最小生成树是唯一的。”

1. 该片段陈述了结论，但未给出证明。

如果图中所有边的权重互不相同，那么最小生成树是唯一的。

1. 该图是带权图。

2. 所有边的权重两两不同。

对于任意边权重互不相同的带权图，其最小生成树恰好有一棵。

1. 声音
   观察依据

   旁白说道：“普里姆算法是一种贪心算法，因此我们将选择连接到未访问节点的最小边。”

普里姆算法通过贪心地选取连接当前已访问顶点集与某一未访问顶点的最小权重边来逐步推进。

1. 已选定一个起始顶点。

2. 维护一个已访问顶点集合。

3. 边的权重可比较。

在算法完成前的每一轮迭代中，都会选择一条局部最小的横跨边。

1. 声音
   观察依据

   旁白在引入复杂度页面时说道：“时间复杂度取决于所采用的数据结构。”

2. 字幕依据
   观察依据

   针对两种不同的实现方式，给出了两个不同的界。

1. 口述讲解在给出更多细节之前被截断。

Prim 算法的时间复杂度取决于用于表示图和搜索图的数据结构。

1. 该图以某种具体的数据结构来表示。

2. 该算法通过相应的搜索/更新机制来实现。

在 Prim 算法的不同实现中，渐近运行时间随所选的图表示方式及优先级结构支持而变化。

1. 声音
   观察依据

   说话者说：“此处展示的算法实现起来相当简单。”

1. 这是一个评价性陈述，而非形式化定理。

屏幕上展示的算法实现起来相当简单。

1. 说话者所指为屏幕上显示的 Prim 算法伪代码。

未明确陈述任何形式化的量词。

1. 声音
   观察依据

   讲解者在示例图上逐步演示该算法。

2. 图示
   观察依据

   随着算法推进，黑板实时更新 Visited 集合，并将所选的最小生成树边涂为红色。

1. 公式

   $$$$
   解释

   从空的 Visited 集合开始，记为 Visited = { }。

   步骤依据

   讲解者陈述的初始化步骤。

   视频直接表达
2. 公式

   $$$$
   解释

   任选一个起始顶点；示例中选择了 A，并更新已访问集合为 Visited = {A}。

   步骤依据

   讲解者说任选一个节点，然后从 A 开始。

   视频直接表达
3. 公式

   $$$$
   解释

   检查与 A 关联的所有边，并选择通往未访问顶点的最小权值边，即边 A-B，其权值为2；更新已访问集合为 Visited = {A,B}。

   步骤依据

   这是讲解中所述的贪心规则，图中通过圈出 A-B 来示意。

   视频直接表达
4. 公式

   $$$$
   解释

   在已访问集合 {A,B} 的基础上，比较所有跨越边；其中多条边的权值为3，演示者选择了 A-C，更新已访问集合为 Visited = {A,B,C}。

   步骤依据

   讲解者明确指出权值为3的边之间存在并列情况，并说：“我选择加入 AC。”

   视频直接表达
5. 公式

   $$$$
   解释

   继续应用相同规则，选择权值为1的边 C-E，更新已访问集合为 Visited = {A,B,C,E}。

   步骤依据

   板书上圈出了 C-E，随后将其涂成红色，作为下一条最小跨越边。

   视频直接表达
6. 公式

   $$$$
   解释

   选择权值为3的边 A-D，更新已访问集合为 Visited = {A,B,C,E,D}。

   步骤依据

   图中高亮显示了 A-D，讲解说明应继续选取通往未访问节点的最小权值边。

   视频直接表达
7. 公式

   $$$$
   解释

   尽管 B-E 的权值为3，但因其两个端点均已访问，故不被选取；转而选择权值为6的边 C-F，更新已访问集合为 Visited = {A,B,C,D,E,F}。

   步骤依据

   讲解者明确拒绝将 B-E 加入最小生成树（因其两端点均已在树中），随后加入 F。

   视频直接表达
8. 公式

   $$$$
   解释

   唯一剩余的未访问顶点是 G，因此添加边 F-G，其权重为9，从而得到覆盖全部七个顶点的完整最小生成树（MST）。

   步骤依据

   讲述者指出 G 是唯一剩余的未访问节点，随后声明所有节点已通过一棵树彼此连通。

   视频直接表达
9. 公式

   $$2 + 3 + 3 + 1 + 6 + 9 = 24$$
   解释

   将所选六条 MST 边的权重相加，以计算总边权。

   步骤依据

   黑板上写出算式，讲述者解释：MST 的总权重通过累加各边权重得出。

   视频直接表达

该示例得到 MST 边集 {A-B, A-C, C-E, A-D, C-F, F-G}，总权重为24。

1. 声音
   观察依据

   讲述者指出：边 B-E 的权重最小，但其两个端点均已位于 MST 中，因此不选取该边。

2. 图示
   观察依据

   边 B-E 保持未被选取，而另一条横跨边被选中。

1. 公式

   $$$$
   解释

   在候选边中找出可见的最小边，此处为边 B-E，其权重为3。

   步骤依据

   讲述者指出：此时 B-E 是权重最小的边。

   视频直接表达
2. 公式

   $$$$
   解释

   检查该边是否连接一个已访问顶点与一个未访问顶点。

   步骤依据

   Prim 算法的规则仅接受从当前树指向外部顶点的横跨边。

   依据视频推导
3. 公式

   $$$$
   解释

   由于顶点B和E都已在最小生成树（MST）中，因此舍弃边B-E。

   步骤依据

   讲解者明确指出，这两个顶点都已在最小生成树中，因此该边未被选中。

   视频直接表达
4. 公式

   $$$$
   解释

   选择下一条有效的最小横跨边C-F，其权重为6。

   步骤依据

   算法继续选取通往未访问节点的最小可接受边。

   视频直接表达

位于已访问顶点集合内部的边会被忽略，因为接纳它们将违反最小生成树所要求的树结构（即无环）性质。

1. 公式
   观察依据

   procedure prim(G,w) 的完整带类型伪代码可见，涵盖从初始化到 while 循环及 decreasekey 更新的全部步骤。

1. 该片段并未证明算法的正确性；它仅展示了算法的执行步骤。

1. 公式

   $$for all u \in V: cost(u)=\infty, prev(u)=nil$$
   解释

   将每个顶点的代价初始化为无穷大，并将其前驱初始化为空。

   步骤依据

   显示的伪代码初始化步骤。

   视频直接表达
2. 公式

   $$Pick any initial node u_0; cost(u_0)=0$$
   解释

   选择一个起始顶点，并将其代价设为零，以确保它被首先选中。

   步骤依据

   显示的伪代码初始化步骤。

   视频直接表达
3. 公式

   $$H = makequeue(V)$$
   解释

   将所有顶点放入一个以代价值为键的优先队列中。

   步骤依据

   显示的伪代码行，括号内注明‘优先队列’，并以代价值作为键。

   视频直接表达
4. 公式

   $$while H is not empty: v = deletemin(H)$$
   解释

   重复地从队列中移除当前代价最小且尚未到达的顶点。

   步骤依据

   显示的主循环头部。

   视频直接表达
5. 公式

   $$for each {v,z} \in E: if cost(z) > w(v,z): cost(z)=w(v,z); prev(z)=v; decreasekey(H,z)$$
   解释

   对顶点 v 的每个邻接顶点 z，若边 {v,z} 的代价小于 z 当前的代价，则改进 z 与树的连接，并更新队列中的键。

   步骤依据

   显示的松弛操作块。

   视频直接表达

该过程通过不断提取代价最小的前沿顶点并松弛其关联边来逐步生长一棵生成树，最终的树结构由 prev 数组编码。

1. 图示
   观察依据

   绘制并逐步处理一张带权图，其顶点为A至G，各边标有数值权重。

2. 声音
   观察依据

   讲解者在此图上运行Prim算法，并计算出最终的总权重。

在所示的带权图上运行Prim算法，该图顶点为A、B、C、D、E、F、G，请找出其最小生成树及所有边的总权重。

1. 顶点：A、B、C、D、E、F、G。

2. 可见的边权重包括：$A-B=2$，$A-C=3$，$A-D=3$，$B-C=4$，$B-E=3$，$C-D=5$，$C-E=1$，$C-F=6$，$D-F=7$，$E-F=8$，$F-G=9$。

3. 从任选一个起始节点开始；本例选择节点A。

使用普里姆（Prim）贪心规则构造最小生成树，并计算所有边的总权重。

1. 公式

   $$$$
   解释

   初始化已访问集合 Visited = { }。

   步骤依据

   这是算法的初始化步骤说明。

   视频直接表达
2. 公式

   $$$$
   解释

   选择 A 作为起始顶点，并令 Visited = {A}。

   步骤依据

   讲解者指出可任选一个节点，此处从 A 开始。

   视频直接表达
3. 公式

   $$$$
   解释

   从 A 出发，选取到未访问顶点的最小边 A-B（权重为2）；令 Visited = {A,B}。

   步骤依据

   直接应用贪心的横跨边规则。

   视频直接表达
4. 公式

   $$$$
   解释

   在权重均为3的若干最小横跨边中，选择 A-C；令 Visited = {A,B,C}。

   步骤依据

   讲解者指出存在并列情况，并明确选择了 AC。

   视频直接表达
5. 公式

   $$$$
   解释

   选取 C-E（权重为1）；令 Visited = {A,B,C,E}。

   步骤依据

   该边是当时已访问顶点集到未访问顶点的最小边。

   视频直接表达
6. 公式

   $$$$
   解释

   选取 A-D（权重为3）；令 Visited = {A,B,C,E,D}。

   步骤依据

   继续使用黑板上所示的同一贪心规则。

   视频直接表达
7. 公式

   $$$$
   解释

   跳过 B-E，因为两个端点都已被访问；选择 C-F（权重6）；设 Visited = {A,B,C,D,E,F}。

   步骤依据

   讲解者明确拒绝了 B-E，然后通过 C-F 将 F 加入。

   视频直接表达
8. 公式

   $$$$
   解释

   选择 F-G（权重9），因为最后一个未访问的顶点是 G。

   步骤依据

   讲解者指出 G 是唯一剩余的未访问节点。

   视频直接表达
9. 公式

   $$2 + 3 + 3 + 1 + 6 + 9 = 24$$
   解释

   将最小生成树（MST）的六条边的权重相加，得到总代价。

   步骤依据

   黑板展示了算术运算过程，讲解者解释了求和过程。

   视频直接表达

该最小生成树由边 A-B、A-C、C-E、A-D、C-F 和 F-G 构成，所有边的权重之和为24。

所得子图连接全部七个顶点，恰好包含六条边，且不含环；所显示的已选边权重之和为24。

1. 字幕依据
   观察依据

   开场黑板显示“Prim 算法”，随后添加向下的箭头指向“最小生成树（MST）”。

1. 文字“Prim 算法”

2. 向下箭头

3. 文字“最小生成树（MST）”

1. 黑板首先呈现该算法的名称。

2. 添加一个箭头，表示该算法可生成一棵最小生成树。

1. 所展示的关系是概念性的，而非计算性的。

2. 在此时间段内，尚未对任何图进行处理。

该视觉呈现确立了普里姆算法被作为获取最小生成树的一种方法来引入。

1. 图示
   观察依据

   出现一幅手绘的带权图，顶点标记为 A 至 G，图下方写着“已访问 = { }”。

1. 七个标号顶点 A–G

2. 带权边

3. 文字“已访问 = { }”

1. 引入示例图。

2. 算法状态以一个空的已访问集合进行初始化。

1. 基础图结构及边权重在整个演算示例中保持不变。

2. 尚未选择任何最小生成树（MST）边。

本帧在做出任何贪心选择之前，先设定输入实例。

1. 字幕依据
   观察依据

   另一页板书上写着“Prim算法 = 选一个节点”。

1. 文字：“Prim算法 = 选一个节点”

1. 视频暂时离开图示，以强调初始化规则。

1. 本页幻灯片上尚未永久添加任何顶点。

2. 该提示总结了下一步操作步骤。

画面将Prim算法的起始阶段浓缩为“选择一个初始顶点”的概念。

1. 图示
   观察依据

   与顶点 A 关联的边被突出显示，且边 A-B 被圈出，随后涂为红色。

2. 声音
   观察依据

   旁白提示：检查所有从 A 可达的顶点，并从中选择一条通往未访问节点的权重最小的边。

1. 顶点 A

2. 从 A 出发的边

3. 边 A-B

4. 已访问集合文字

1. 已访问集合由 { } 变为 {A}，再变为 {A,B}。

2. 边 A-B 被标记为最小生成树（MST）的一部分。

1. 图的其余拓扑结构保持不变。

2. 仅连接已访问顶点与未访问顶点的边才相关。

动画/示意图演示了 Prim 算法的核心步骤：检查前沿边，并选取其中向外延伸的最廉价的一条。

1. 图示
   观察依据

   从已访问集合可见多条权重为3的候选边，其中边A-C被圈出并选中。

2. 声音
   观察依据

   解说员指出三条边的权重均为3，并选择了边AC。

1. 已访问集合{A,B}

2. 权重为3的候选边

3. 边A-C

1. 已访问集合从{A,B}扩展为{A,B,C}。

2. 任意选择一条平局的最小边。

1. 所有平局的边具有相同权重。

2. 无论选择哪条平局的边，该算法依然有效。

该图示说明：Prim算法的贪心规则在遇到平局时，仍可通过任选一条最小横跨边继续执行。

1. 图示
   观察依据

   边B-E以权重3可见，但未被选中；随后选中了边C-F。

2. 声音
   观察依据

   讲解员明确指出：边 B-E 未被选中，因为它的两个顶点都已位于最小生成树（MST）中。

1. 边 B-E

2. 边 C-F

3. 添加顶点 F 前后已访问顶点集合的状态

1. 该算法尽管边 B-E 的权重很小，仍将其忽略。

2. 通过边 C-F 添加顶点 F，使得已访问顶点集合得以扩展。

1. 被接受的边必须始终连接一个已访问顶点与一个未访问顶点。

2. 已访问顶点集合只增不减，绝不会缩小。

这一事件在视觉上澄清了一个常见误解：全局最小的邻接边，若其两端均落在当前树内部，则并不总是可选的。

1. 图示
   观察依据

   全部七个顶点均以红色圆圈标出，所选出的最小生成树边也以红色显示。

2. 字幕依据
   观察依据

   黑板上写着：“总边权 = $2 + 3 + 3 + 1 + 6 + 9 = 24$”。

1. 以红色高亮显示的MST边

2. 所有顶点A–G

3. 用于计算总权重的算术行

1. 算法在访问全部顶点后终止。

2. 总权重由所选边计算得出。

1. 最终结构是一棵覆盖所有顶点的树。

2. 未被选中的边从最小生成树中省略。

收尾的图示视图确认了Prim算法的输出，并将边集转化为其数值代价。

1. 字幕依据
   观察依据

   一个标题为“时间复杂度”的新页面列出了两个依赖于实现方式的上界。

1. 讲解员的说明在展开前被截断。

1. 标题：“时间复杂度”

2. 文字：“邻接矩阵，搜索 → $O(V^2)$”

3. 文字：“二叉堆与邻接表 → $O(V \log V + E \log V)$”

1. 视频从具体的图执行转向一般性的算法分析。

1. 这些界被呈现为实现方式的性质，而非某个具体图实例的性质。

黑板总结指出：Prim 算法的效率取决于图的表示方式以及优先级操作的实现方式。

1. 图示
   观察依据

   静态手写页面，标题为‘时间复杂度’，包含两种实现方式的两行说明及指向渐近界的时间复杂度箭头。

1. 标题：时间复杂度

2. 行：邻接矩阵，搜索

3. 箭头

4. 表达式：$O(V^2)$

5. 行：二叉堆与邻接表

6. 箭头

7. 表达式：$O(V \log V + E \log V)$

1. 大约在3.5秒时，手写页面切换为打字排版的伪代码页面。

1. 在最初的3.5秒内，幻灯片内容保持静止。

2. 两条复杂度陈述始终与其对应的实现标签配对显示。

该视觉呈现先引入依赖于实现的运行时间，再展示算法本身。

1. 图示
   观察依据

   静态打字页面，标题为过程 prim(G,w)，包含输入/输出行、初始化、优先队列创建及嵌套循环。

1. 头函数：prim(G, w)

2. 输入行

3. 输出行

4. 初始化块

5. H = 创建一个以 V 为初始元素的队列

6. while 循环

7. 对每条边 {v, z} ∈ E

8. 若 cost(z) > $w(v, z)$

9. 降低键值（H，z）

10. 右下角为源网址

1. 约在3.5秒时，上一张手写幻灯片被此页打印内容替换。

2. 过渡完成后，页面保持静止直至片段结束。

1. 伪代码文本不会对单行进行动画或高亮显示。

2. 资料来源标注始终显示在右下角。

第二个画面以伪代码形式完整呈现该算法，同时旁白评述其易于实现，并以此结束本课。

1. 声音
   观察依据

   讲解员指出，权值为3的边 BE 是当前最小的边，但其两个端点均已位于最小生成树中，因此不选取该边。

2. 图示
   观察依据

   边 B-E 未被选中，而另一条横跨边被选中。

有人可能认为 Prim 算法应始终选取当前最小的邻近边，即使该边的两个端点都已在生成树中。

Prim 算法的规则仅接受连接已访问顶点集合与未访问顶点的最小边；位于已访问集合内部的边会被拒绝，因为它们将导致环的产生。

1. 声音
   观察依据

   讲解员说：“注意，若所有边权互不相同，则该最小生成树是唯一的。”

1. 该片段未讨论边权不互异时的情形，仅暗示此时最小生成树可能不唯一。

学习者可能从示例中推断出：每张图都恰好有一棵最小生成树。

视频仅在附加条件“所有边权互异”下说明了最小生成树的唯一性；若不满足该条件，则可能存在多棵最小生成树。

1. 字幕依据
   观察依据

   从“普里姆算法”指向“最小生成树（MST）”的箭头。

2. 声音
   观察依据

   讲解员指出，普里姆算法的结果是一棵最小生成树。

普里姆算法被呈现为一种过程，其输出是一棵最小生成树。

1. 声音
   观察依据

   引入已访问列表，并随后用它来判断哪些边连接至未访问节点。

2. 图示
   观察依据

   每当一个顶点被接纳，已访问集合即被更新。

维护已访问集合是必要的，以便识别那些从当前生成树跨越至未访问顶点的边。

1. 声音
   观察依据

   讲解员反复应用贪心规则，直至所有节点均被连接成一棵树。

2. 图示
   观察依据

   每条被接纳的跨越边都会扩大当前的部分最小生成树，直至所有顶点都被包含。

终止性论证依赖于反复应用贪心穿越边规则，直到每个顶点都被吸收进生成树中。

1. 声音
   观察依据

   讲解者拒绝边 B-E，因为它的两个端点都已在最小生成树（MST）中。

2. 图示
   观察依据

   所选边持续构成一个无环且连通的子图。

舍弃内部边，正是为了使构造过程始终满足生成树的无环要求。

1. 字幕依据
   观察依据

   总权重的算术运算写在最终红色最小生成树显示之后。

2. 声音
   观察依据

   讲解者说，将各条边的权重相加，即可得到最小生成树的总边权。

只有当最小生成树的边集被完全确定后，才能计算总边权。

1. 字幕依据
   观察依据

   列出了两种不同实现方式所对应的两个不同上界。

2. 声音
   观察依据

   讲解者指出，时间复杂度取决于所采用的数据结构。

1. 该片段在给出任一上界的详细推导之前就结束了。

抽象算法——普里姆方法——可有多种实现方式，而所选用的数据结构决定了其渐近运行时间。

1. 公式
   观察依据

   邻接矩阵，搜索操作通过箭头直接与 $O(V^2)$ 配对。

$O(V^2)$ 界适用于采用邻接矩阵搜索方式实现的所展示 Prim 过程。

1. 公式
   观察依据

   二叉堆与邻接表通过箭头直接与 $O(V \log V + E \log V)$ 配对。

$O(V \log V + E \log V)$ 界适用于采用二叉堆与邻接表实现的所展示 Prim 过程。

1. 公式
   观察依据

   初始化语句位于伪代码块中 H = makequeue(V) 和 while 循环之前。

主循环依赖于 cost、prev、起始顶点 $u_0$以及优先队列 H 的前期初始化。

1. 公式
   观察依据

   过程头与输入/输出语句将后续算法框定为求解最小生成树问题。

所展示的方法是一种 Prim 算法实现，用于从连通无向带权图中生成最小生成树。

1. 声音
   观察依据

   讲解者将最小生成树（MST）定义为：一个无环且连通、且总权重最小的图。

1. 最小生成树的定义
2. 普里姆算法的目的

1. 字幕依据
   观察依据

   黑板上写着“普里姆算法 = 选一个节点”。

2. 声音
   观察依据

   旁白提示我们任选一个节点，从节点 A 开始。

1. Prim 算法的起始步骤
2. visited 列表/集合的作用

1. 声音
   观察依据

   旁白选择从 A 到未访问节点的最小权值边，即 A 到 B 的边。

2. 图示
   观察依据

   边 A-B 被圈出并涂成红色。

1. 普里姆算法中的贪心选择规则

1. 声音
   观察依据

   旁白指出三条边的权值均为3，并从中任选一条。

1. 当多个最小权重边的权值相等时的处理方式

1. 声音
   观察依据

   旁白说明边 B-E 未被选中，因为其两个端点都已在最小生成树中。

1. 拒绝两个端点都已被访问过的边。
2. 常见误解：不考虑端点状态，直接选择最小边

1. 声音
   观察依据

   旁白指出：若所有边的权值互不相同，则最小生成树唯一。

1. 边权重互异时最小生成树的唯一性
2. 常见误解：最小生成树总是唯一的

1. 字幕依据
   观察依据

   黑板上显示求和式：$2 + 3 + 3 + 1 + 6 + 9 = 24$。

1. 计算最小生成树的目标函数值

1. 字幕依据
   观察依据

   黑板上列出了不同实现方式的时间复杂度：$O(V^2)$ 和 $O(V \log V + E \log V)$。

1. 口述讲解被截断。

1. 普里姆算法的时间复杂度依赖于具体实现方式

1. 公式
   观察依据

   手写行：邻接矩阵，搜索 → $O(V^2)$。

1. 使用邻接矩阵进行搜索的时间复杂度。

1. 公式
   观察依据

   手写行：二叉堆与邻接表 → $O(V \log V + E \log V)$。

1. 使用二叉堆与邻接表的时间复杂度

1. 公式
   观察依据

   伪代码对所有顶点初始化 cost 和 prev，然后设 cost($u_0$)=0，并构建堆 H。

1. Prim 算法的初始化步骤

1. 公式
   观察依据

   在 if 语句块内，伪代码更新 cost(z)、prev(z)，并调用 decreasekey(H,z)。

1. Prim 算法的主松弛循环