Prim算法直观讲解 | 最小生成树

1. 声音
   观察依据

   讲述者指出，在任意一棵最小生成树中，边的数量总是恰好等于顶点数减一，其中顶点数用 V 表示。

2. 图示
   观察依据

   屏幕文字在最终的红色生成树旁显示“Edges”，其上方为“V - 1”。

V

图中顶点的个数。

正整数；在本例演算中，$V = 6$。

1. 声音
   观察依据

   讲解员指出，任意最小生成树恰好有 V - 1 条边。

2. 图示
   观察依据

   屏幕上显示的公式为“V - 1 Edges”。

V - 1

含 V 个顶点的生成树中边的条数。

1. 图示
   观察依据

   Python 代码显示 `def prims_algorithm(graph, start):`，随后使用了 `graph[start]`。

2. 声音
   观察依据

   讲解员说明该函数以图和起始节点作为输入参数。

1. 可见部分未完整指定邻接表数据结构的具体形式。

graph

Prim 算法实现所采用的输入图表示方式。

1. 图示
   观察依据

   Python 代码显示 `def prims_algorithm(graph, start):`，接着是 `visited.add(start)` 和 `for neighbor, weight in graph[start]:`。

2. 声音
   观察依据

   讲解者指出，该函数将起始节点作为输入参数。

start

普里姆算法构建生成树时所选取的初始顶点。

1. 图示
   观察依据

   Python 代码初始化 `priority_queue = []`，并使用 `heapq.heappush(priority_queue, (weight, start, neighbor))` 和 `heapq.heappop(priority_queue)`。

2. 声音
   观察依据

   此前的讲解提到，优先队列可存储边，以便快速获取权重最小的边。

priority_queue

以权重为主要排序依据、存储候选边元组的最小堆。

1. 图示
   观察依据

   Python 代码初始化 `visited = set()`，随后调用 `visited.add(start)` 并检查 `if v not in visited:`。

visited

已加入不断生长的生成树中的顶点集合。

1. 图示
   观察依据

   Python 代码初始化 `mst_edges = []`。

1. 本片段中未见向 `mst_edges` 追加元素的操作。

mst_edges

用于收集所选最小生成树边的列表。

1. 图示
   观察依据

   Python 代码初始化 `total_cost = 0`。

1. 本片段中未见对 `total_cost` 的更新操作。

total_cost

用于累加所选生成树边总权重的累加器。

1. 图示
   观察依据

   Python 代码包含 `for neighbor, weight in graph[start]:`，并压入元组 `(weight, start, neighbor)`。

neighbor, weight

从起始顶点的邻接表中读取的相邻顶点及其对应边的权重。

1. 图示
   观察依据

   Python 代码包含 `weight, u, v = heapq.heappop(priority_queue)`。

weight, u, v

弹出的候选边元组：边的权重、源顶点、目标顶点。

1. 公式
   观察依据

   所显示的代码将 `graph` 用作 `prims_algorithm(graph, start)` 的第一个参数，并以 `graph[start]` 和 `graph[v]` 的方式对其索引。

2. 声音
   观察依据

   在00:24-00:27处，讲解者说：“这假设图以邻接表形式存储。”

graph

以邻接表形式表示的带权图；每个条目将一个节点映射到其带权邻边的集合。

Prim 算法所使用的带权图数据结构。

1. 公式
   观察依据

   代码中定义了 `def prims_algorithm(graph, start):`，随后出现 `visited.add(start)` 以及 `for neighbor, weight in graph[start]:`。

2. 声音
   观察依据

   在00:17-00:23处，讲解者说：“接着，我们将起始节点加入已访问集合，并将其邻边及其权重一并推入优先队列。”

start

Prim 算法开始构建最小生成树时所选取的初始顶点。

输入图中的一个顶点。

1. 声音
   观察依据

   讲解员将最小生成树定义为图的一个子集，该子集以尽可能小的总边权重连接所有顶点，保持连通性，且不含环。

2. 图示
   观察依据

   在讲解定义的同时，展示一个带权无向图，其顶点为 A、B、C、D、F，并含多条边。

最小生成树是带权图的一个生成子图，它包含图中所有顶点，保持连通，不含环，且使其所有边的权重之和最小。

1. 适用于带权图。

2. 所选子图必须连接所有顶点。

3. 所选子图必须是无环的。

4. 目标是使所有边的总权重最小。

1. 声音
   观察依据

   讲解者表示将使用普里姆（Prim）算法求最小生成树：首先选定一个顶点，然后逐步添加权重最小的边，在保持图连通且无环的前提下扩展生成树。

普里姆算法从一个选定的起始顶点出发，通过反复添加能扩展当前树、且不会形成环的最廉价边，来构建一棵生成树。

1. 要求输入图为连通的带权图，以保证能覆盖所有顶点生成一棵生成树。

2. 从一个选定的顶点开始。

3. 每条被采纳的边都必须将当前树连接至一个新顶点。

1. 最小生成树定义

1. 声音
   观察依据

   讲解者指出，可用优先队列来存储边，从而快速检索出权重最小的边。

在普里姆算法中，优先队列用于存储候选边，以便高效地提取下一条最小权重的边。

1. 候选边按权重排序。

2. 该队列支持对最小权重项的快速提取。

1. 普里姆算法的高层方法

1. 声音
   观察依据

   讲解员指出，任意最小生成树恰好有1条边，其中V表示顶点数量。

2. 图示
   观察依据

   文字“V - 1 条边”出现在最终生成树旁。

对于含有V个顶点的图，任意生成树（包括最小生成树）都恰好包含V - 1条边。

1. 该图含有V个顶点。

2. 该子图是一棵生成树，即连通且无环。

1. 最小生成树定义

1. 图示
   观察依据

   可见的Python代码导入`heapq`，定义函数`prims_algorithm(graph, start)`，初始化`priority_queue`、`visited`、`mst_edges`和`total_cost`，将起始节点标记为已访问，将起始节点的邻接边压入堆，并开始从堆中弹出元素，同时进行`v not in visited`检查。

2. 声音
   观察依据

   讲解员介绍Python代码，提到导入`heapq`以实现优先队列，并定义接收图和起始节点作为输入的函数。

1. 视频片段在完整循环体和返回语句显示之前结束。

可见代码用候选边的最小堆、记录生成树顶点的已访问集合，以及用于收集最小生成树边和总代价的占位符，实现了Prim算法。

1. 使用`heapq`作为最小堆优先队列。

2. 图用邻接表表示，因此 `graph[start]` 返回形如 `(邻居节点, 边权)` 的二元组。

3. 已加入生成树的顶点记录在 `visited` 中。

1. 普里姆算法的高层方法
2. 优先队列作为选边结构

1. 公式
   观察依据

   屏幕上显示 `priority_queue = []`、`visited = set()`、`mst_edges = []` 以及 `total_cost = 0`，位于 `def prims_algorithm(graph, start):` 函数内部。

2. 声音
   观察依据

   讲解者按从00:02到00:17的顺序，依次说明每个变量的作用。

该实现首先创建四个状态容器：一个用于候选边的优先队列、一个用于已加入生成树的顶点的 visited 集合、一个用于存储最小生成树边的列表，以及一个用于累计总代价的数值累加器。这些对象分别对应算法的前沿、成员判定、输出结果和目标值。

1. 该图是带权图。

2. 该实现使用最小堆优先队列。

3. 假设图以邻接表形式存储。

1. 公式
   观察依据

   高亮显示的代码为 `visited.add(start)`，随后是 `for neighbor, weight in graph[start]: heapq.heappush(priority_queue, (weight, start, neighbor))`。

2. 声音
   观察依据

   在00:17-00:23处，讲解者指出起始节点被加入 `visited`，且其所有邻接边被压入优先队列。

3. 声音
   观察依据

   在00:24-00:27处，讲解者说明图以邻接表形式存储。

普里姆算法首先将一个顶点标记为已在生成树中，并将其所有关联边插入优先队列。这就在已访问顶点与未访问顶点之间形成了初始割集，使得后续步骤可反复选择最廉价的横跨边。

1. 选定一个起始顶点 `start`。

2. `graph[start]` 枚举所有邻接的 `(neighbor, weight)` 对。

3. 边以 `(weight, start, neighbor)` 形式压入，使堆按权重优先排序。

1. Prim 算法实现的初始化变量。

1. 公式
   观察依据

   代码显示 `while priority_queue:` 和 `weight, u, v = heapq.heappop(priority_queue)`，随后是 `if v not in visited:`。

2. 声音
   观察依据

   在00:28-00:35处，讲解者说：“只要优先队列非空，我们就弹出权重最小的元素，并检查该节点是否已在已访问集合中。”

核心贪心步骤反复从优先队列中移除权重最小的边，并检验其目标顶点是否仍在生成树之外。若目标顶点已被访问，则丢弃该边；否则，该边成为下一条被接受的最小生成树边。

1. 堆按权重顺序存储候选边。

2. 在此实现中，仅检查目标顶点 `v` 是否在 `visited` 中。

1. 从起始顶点启动普里姆算法。

1. 公式
   观察依据

   高亮代码块为：`visited.add(v)`、`mst_edges.append((u, v))`、`total_cost += weight`，然后执行 `for neighbor, weight in graph[v]: if neighbor not in visited: heapq.heappush(priority_queue, (weight, v, neighbor))`。

2. 声音
   观察依据

   在00:36-00:47处，讲解者说：将节点加入 `visited`，将该边加入最小生成树，更新总代价，并将所有相连的边压入优先队列。

1. 讲解词说“当前节点连接的所有边”，而屏幕上可见的代码仅压入那些邻居尚未被访问的边。

当弹出的边到达一个未访问顶点时，算法将该顶点正式纳入生成树，记录该边，将其权重加至总代价，并将该顶点新可到达的所有出边插入优先队列。此举维持了堆中始终包含从已访问集合指向图其余部分的候选边这一不变性。

1. 弹出的边 `(u, v)` 满足 `v not in visited`。

2. `graph[v]` 提供相邻的 `(neighbor, weight)` 对。

3. 实现过程会在将邻居节点加入优先队列前，先过滤掉已在 `visited` 中的邻居。

1. 主循环：提取权重最小的候选边

1. 公式
   观察依据

   屏幕上显示的最后一行是 `return mst_edges, total_cost`。

2. 声音
   观察依据

   在00:47-00:52处，讲解者说：“最后，我们返回最小生成树的边集及其总代价。”

当优先队列耗尽后，函数同时输出所选边的列表与累积权重。该边列表描述了树的结构，而标量值则给出了优化目标的取值。

1. 主循环已终止，原因是 `priority_queue` 为空。

2. 图的连通性足以保证遍历生成一棵生成树；但这一条件在视频片段中并未明确说明。

1. 接纳一个新顶点，记录对应边，并扩展搜索边界

1. 公式
   观察依据

   幻灯片首先显示 `TIME COMPLEXITY` 及 `$O(E)$`，接着显示 `$O(E) + O(E \log V)$`，最后简化为 `$O(E \log V)$`。

2. 声音
   观察依据

   在00:57-01:10处，讲解者指出：遍历所有边的时间复杂度为 `$O(E)$`，每条边至多被压入队列一次，每次压入耗时对数级，因此总时间复杂度为 `$O(E \log V)$`。

算法在线性时间内扫描邻接信息（以边数为基准），每次堆插入或删除操作耗时对数级。由于每条边大约仅进入优先队列一次，主导项为堆操作开销，故总体时间复杂度为 `$O(E \log V)$`。

1. 优先队列以二叉堆方式实现。

2. 每条边最多被插入约一次。

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

1. 主循环：提取权重最小的候选边
2. 接纳一个新顶点，记录对应边，并扩展搜索边界

1. 公式
   观察依据

   幻灯片显示 `SPACE COMPLEXITY`（空间复杂度），并先构建出 `$O(V + E) + O(V) + O(E) + O(V)$`，再化简为 `$O(V + E)$`。

2. 声音
   观察依据

   从 01:11 到 01:33，讲解者将邻接表表示的图的空间复杂度记为 `$O(V + E)$`，已访问顶点集合记为 `$O(V)$`，优先队列记为 `$O(E)$`，最小生成树边列表记为 `$O(V)$`，进而得出总空间复杂度为 `$O(V + E)$`。

内存使用主要由图本身的存储决定，此外还需额外结构来记录已访问顶点、前沿堆以及输出边列表。将这些项相加并化简后，得到总空间复杂度为 `$O(V + E)$`。

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

2. 已访问集合最多可包含全部顶点。

3. 优先队列最多可包含全部边。

4. 最小生成树边列表最多存储 `V - 1` 条边，其上界为 `$O(V)$`。

1. Prim 算法实现的初始化变量。
2. 基于堆实现的 Prim 算法的时间复杂度

1. 声音
   观察依据

   讲解者明确陈述了最小生成树的定义性质。

最小生成树是图的一个子集，它连接所有顶点，总边权最小，保持连通性，且不含环。

1. 基础图是带权图。

2. 所选子图覆盖所有顶点。

对于给定的带权图，在所有生成树中，最小生成树取得最小的总边权。

1. 声音
   观察依据

   讲解者描述了从一个顶点出发，逐步添加权重最小的边，同时确保连通性与无环性。

普里姆算法通过反复添加能将当前连通无环子树扩展至新顶点的最小权重边，来构造最小生成树。

1. 该图是连通的且带权。

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

3. 当前选中的边构成一棵树。

在每次迭代中，选择一条权重最小的可行边。

1. 声音
   观察依据

   讲解员指出：任意一棵最小生成树恰好有 V - 1 条边。

2. 图示
   观察依据

   屏幕文字显示“V - 1 条边”。

对于一个含有 V 个顶点的图，其任意一棵最小生成树都恰好包含 V - 1 条边。

1. 该子图是 V 个顶点上的一棵生成树。

对于任意一棵 V 个顶点上的生成树，其边数都等于 V - 1。

1. 声音
   观察依据

   讲解员解释：如果边数更少，该图将不连通。

若一个 V 个顶点上的生成子图所含边数少于 V - 1，则它不连通。

1. 该子图旨在包含全部 V 个顶点。

对于所有含 V 个顶点且边数少于 V - 1 的子图。

1. 声音
   观察依据

   讲解员说明：若边数更多，便会形成环，而树中不允许出现环。

若一个含 V 个顶点的连通子图具有多于 V - 1 条边，则它包含一个环，因此不是一棵树。

1. 该子图包含全部 V 个顶点且是连通的。

对于所有含 V 个顶点且边数多于 V - 1 的连通子图。

1. 声音
   观察依据

   在 00:24-00:27 处，讲解者说：“这假设图以邻接表形式存储。”

2. 公式
   观察依据

   代码将 `graph[start]` 和 `graph[v]` 视为可迭代的邻居列表并进行索引。

所展示的普里姆算法实现假设输入图以邻接表形式存储。

1. 该函数接收一个名为 `graph` 的参数。

2. `graph[node]` 可被遍历，从而生成 `(neighbor, weight)` 对。

针对本片段中展示的实现。

1. 公式
   观察依据

   在‘时间复杂度’标题下，幻灯片简化为 `$O(E \log V)$`。

2. 声音
   观察依据

   在01:00-01:10处，讲解者得出总时间复杂度为‘E log V 的大 O 表示法’。

对于本片段中展示的基于堆的实现，总时间复杂度为 `$O(E \log V)$`。

1. 该图具有 `V` 个顶点和 `E` 条边。

2. 优先队列是一个二叉堆。

3. 每条边大约被压入一次，且堆操作耗时为对数级。

所呈现算法的渐近最坏情况界。

1. 公式
   观察依据

   在“空间复杂度”标题下，该幻灯片简化为 `$O(V + E)$`。

2. 声音
   观察依据

   在01:30-01:33处，讲解者说：“因此，总空间复杂度为 V 加 E 的大 O 记号。”

对于所展示的实现，总空间复杂度为 `$O(V + E)$`。

1. 图以邻接表形式存储，需占用 `$O(V + E)$` 空间。

2. 已访问集合占用 `$O(V)$` 空间。

3. 优先队列占用 `$O(E)$` 空间。

4. 最小生成树边列表占用 `$O(V)$` 空间。

所呈现算法的渐近内存界。

1. 声音
   观察依据

   讲解员依次演示选择 A、AB、BD、DC、AF，并指出所有节点均已连通，因此算法终止。

2. 动画
   观察依据

   图中以绿色高亮候选边，以红色标示已采纳的边，同时顶点按顺序变为黄色。

1. 公式

   $$$$
   解释

   选择顶点 A 作为起始顶点。

   步骤依据

   讲解员说：“我们从节点 A 开始。”

   视频直接表达
2. 公式

   $$$$
   解释

   在与顶点 A 关联的所有边中，选择权重为2的边 AB，并将其加入生成树。

   步骤依据

   AB 是当前生成树 {A} 中通往外部顶点的最小权重边；动画将 AB 变为红色，B 变为黄色。

   视频直接表达
3. 公式

   $$$$
   解释

   从当前生成树 {A, B} 出发，考察所有跨越到外部顶点的边，并选择权重为2的边 BD。

   步骤依据

   讲解员指出，高亮显示的最小代价边是权重为2的 BD；动画将 BD 以红色加入，并将 D 标记为黄色。

   视频直接表达
4. 公式

   $$$$
   解释

   从当前生成树 {A, B, D} 出发，选择权重为1的边 DC 并将其加入。

   步骤依据

   DC 是当前可选的最小权重跨割边；动画将 DC 染为红色，并将 C 标记为黄色。

   视频直接表达
5. 公式

   $$$$
   解释

   从当前生成树 {A, B, D, C} 出发，选择权重为3的边 AF 并将其加入。

   步骤依据

   AF 是到达顶点 F 所需的剩余最小权重边；动画将 AF 染为红色，并将 F 标记为黄色。

   视频直接表达
6. 公式

   $$$$
   解释

   停止，因为所有顶点均已包含在内。

   步骤依据

   讲解员指出：通过此次添加，所有节点均已连通，算法终止。

   视频直接表达

所得的最小生成树由边 AB、BD、DC 和 AF 构成，总权重为$2 + 2 + 1 + 3 = 8$。

1. 声音
   观察依据

   讲解员给出直观解释：边数过少会使图不连通，边数过多则会产生环。

1. 这是一种直观解释，而非严格证明。

1. 公式

   $$E = V - 1$$
   解释

   一个包含 V 个顶点的生成树恰好有 V - 1 条边。

   步骤依据

   由讲述者直接陈述，并在屏幕上展示。

   视频直接表达
2. 公式

   $$$$
   解释

   如果边数少于 V - 1 条，该图将不连通。

   步骤依据

   讲述者所陈述的关于边数不足、无法连接所有顶点的直观理解。

   视频直接表达
3. 公式

   $$$$
   解释

   如果边数多于 V - 1 条，则会形成环。

   步骤依据

   讲述者所陈述的关于多余边违反树结构条件的直观理解。

   视频直接表达

精确的边数 V - 1 是由“覆盖所有顶点”与“保持无环”这两个要求共同决定的。

1. 公式
   观察依据

   图示演算过程为 `$O(E)$` → `$O(E) + O(E \log V)$` → `$O(E \log V)$`。

2. 声音
   观察依据

   讲解者解释了边的遍历、近似每条边仅入队一次、每次入队代价为对数级，以及最终的简化过程。

1. 公式

   $$O(E)$$
   解释

   遍历所有边带来与边数成线性关系的时间开销。

   步骤依据

   叙述者在00:57-01:00处直接陈述，并在幻灯片中展示。

   视频直接表达
2. 公式

   $$O(E \log V)$$
   解释

   每条边最多被压入优先队列一次，每次压入操作耗时对数级。

   步骤依据

   叙述者在01:00-01:07处直接陈述，并体现在第二张幻灯片的对应项中。

   视频直接表达
3. 公式

   $$O(E) + O(E \log V) = O(E \log V)$$
   解释

   该求和式通过保留主导的渐近项得以简化。

   步骤依据

   在幻灯片中以可视化方式呈现，并在01:07-01:10处由叙述者口头得出结论。

   视频直接表达

所介绍的基于堆的Prim算法的总运行时间为`$O(E \log V)$`。

1. 公式
   观察依据

   可视化序列是`$O(V + E)$` → `$O(V + E) + O(V)$` → `$O(V + E) + O(V) + O(E)$` → `$O(V + E) + O(V) + O(E) + O(V)$` → `$O(V + E)$`。

2. 声音
   观察依据

   叙述者将各项分别对应到图、已访问集合、优先队列和最小生成树边列表，然后求和。

1. 公式

   $$O(V + E)$$
   解释

   图本身占用`$O(V + E)$`空间，因其以邻接表形式存储。

   步骤依据

   由讲解员在01:11-01:15处陈述，并作为幻灯片上首项显示。

   视频直接表达
2. 公式

   $$O(V)$$
   解释

   访问集合占用 $O(V)$ 空间，因为它最多存储全部顶点。

   步骤依据

   由讲解员在01:16-01:20处陈述，并作为第二项追加。

   视频直接表达
3. 公式

   $$O(E)$$
   解释

   优先队列占用 $O(E)$ 空间，因为在执行过程中它可能容纳全部边。

   步骤依据

   由讲解员在01:21-01:26处陈述，并作为第三项追加。

   视频直接表达
4. 公式

   $$O(V)$$
   解释

   最小生成树边列表占用 $O(V)$ 空间。

   步骤依据

   由讲解员在01:26-01:30处陈述，并作为第四项追加。

   视频直接表达
5. 公式

   $$O(V + E) + O(V) + O(E) + O(V) = O(V + E)$$
   解释

   将辅助空间界相加并化简，得到总内存需求。

   步骤依据

   在幻灯片上以可视化方式呈现，并于01:30-01:33处通过口头总结得出。

   视频直接表达

所展示实现的总空间使用量为 $O(V + E)$。

1. 图示
   观察依据

   带权图，顶点为 A、B、C、D、F，可见的边权为：AB=2，AF=3，AD=5，BD=2，BC=7，BF=4，CD=1。

2. 声音
   观察依据

   讲述者说：“现在，我们用普里姆算法来求解这个示例图的最小生成树。”

3. 动画
   观察依据

   被选中的边按 AB、BD、DC、AF 的顺序变为红色。

1. 图中未显示顶点E，尽管标签集为五个字母：A、B、C、D、F。

使用普里姆算法，从顶点A出发，求出所展示的带权图的最小生成树。

1. 已显示的顶点：A、B、C、D、F。

2. 已显示的边权：AB=2，AF=3，AD=5，BD=2，BC=7，BF=4，CD=1。

3. 起始顶点：A。

选取一个连通、无环且覆盖所有顶点的边子集，使其总权重最小。

1. 公式

   $$T_0 = \{A\}$$
   解释

   从仅含顶点A的单顶点树开始。

   步骤依据

   叙述中明确指出了起始选择。

   视频直接表达
2. 公式

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

   添加边AB，因为它是从A出发的最便宜的边。

   步骤依据

   当前树上关联边中的最小权重边。

   视频直接表达
3. 公式

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

   从当前树{A,B}出发，添加边BD。

   步骤依据

   这是旁白提到的当前树中成本最低的容许横跨边。

   视频直接表达
4. 公式

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

   将边 DC 加入当前树 {A,B,D}。

   步骤依据

   这是逐步演示中接下来选出的最小权重边。

   视频直接表达
5. 公式

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

   添加边 AF 以包含最后一个顶点 F。

   步骤依据

   旁白选择 AF 作为下一条最小权重边，随后停止。

   视频直接表达
6. 公式

   $$2+2+1+3=8$$
   解释

   将所选边的权重相加，得到整棵树的总权重。

   步骤依据

   由所选边的可见权重推导得出。

   依据视频推导

最小生成树为 {AB, BD, DC, AF}，总权重为8。

所选边连接了所有显示的顶点 A、B、C、D、F，包含$4 = 5 - 1$条边（对应显示的顶点集），且不构成环。

1. 图示
   观察依据

   展示了一个静态的带权无向图：顶点为青绿色圆形，标有字母 A、B、C、D、F；边为深蓝色，标有数字权重。

1. 顶点 A、B、C、D、F

2. 边的权重分别为1、2、2、3、4、5、7

1. 图在定义与算法概述讲解过程中被引入并保持不变。

1. 顶点标签保持固定。

2. 边的权重保持固定。

该图示确立了将用于演示普里姆算法的具体实例。

1. 动画
   观察依据

   顶点A最先变为黄色；当前生成树出发的候选边亮起绿色；已被采纳的边变为红色；新加入的顶点依次变为黄色：B、D、C、F。

1. 每次颜色变化的精确逐帧时间仅为近似值。

1. 当前生成树中的顶点以黄色高亮显示

2. 候选的横跨边以绿色高亮显示

3. 已被采纳的生成树边以红色高亮显示

1. 从顶点A开始。

2. 高亮从顶点 A 出发的边。

3. 选择边 AB。

4. 从集合 {A,B} 扩展候选集。

5. 选择边 BD。

6. 从集合 {A,B,D} 扩展。

7. 选择边 DC。

8. 从集合 {A,B,D,C} 扩展。

9. 选择边 AF。

10. 所有顶点均成为生成树的一部分。

1. 原始图的拓扑结构与边权值均不发生变化。

2. 仅通过颜色编码的变化来标识顶点是否属于生成树以及是否为候选顶点。

该动画展示了普里姆算法的贪心规则：始终维持一棵连通的树，并反复添加代价最小的边界边。

1. 图示
   观察依据

   非树边消失或淡出，仅保留红色树边 AB、BD、DC、AF；右侧显示文字“V - 1 条边”。

1. 红色生成树边 AB、BD、DC、AF

2. 黄色顶点 A、B、C、D、F

3. 文字“V - 1 条边”

1. 画面从完整图切换为孤立的生成树。

2. 公式文字出现在生成树旁。

1. 所选生成树保持连通且无环。

2. 顶点集合保持不变。

视觉效果强调输出结果是一棵生成树，且其边数满足 V - 1 条边这一规则。

1. 图示
   观察依据

   屏幕切换为带语法高亮的 Python 代码；方框短暂突出显示 `import heapq` 和 `def prims_algorithm(graph, start):`。

1. 代码视图仅被部分遍历，片段即结束。

1. Python 源代码

2. 高亮显示的导入语句

3. 高亮显示的函数定义

1. 图可视化被代码取代。

2. 注意力提示框从导入语句移动到函数签名处。

1. 主题仍为普里姆算法。

2. 该代码对应此前讲解过的贪心过程。

视频从概念演示转向使用基于堆的优先队列进行算法实现。

1. 动画
   观察依据

   一个绿色矩形轮廓高亮标出 Python 函数内部的四行初始化代码。

2. 图示
   观察依据

   代码块保持静止，仅高亮框的位置发生变化。

1. Python 代码编辑器视图

2. 绿色高亮矩形

3. 变量 `priority_queue`、`visited`、`mst_edges`、`total_cost`

1. 该高亮覆盖从 00:00 到约 00:17 的初始化语句。

2. 讲解者按高亮行出现的相同顺序逐一介绍每个变量。

1. 在此时间段内，底层代码文本不发生变化。

2. 函数签名 `def prims_algorithm(graph, start):` 始终显示在高亮区域上方。

视觉强调将口头讲解直接对应到定义算法状态的数据结构上。

1. 动画
   观察依据

   绿色方框依次下移至 `visited.add(start)`，再移至 `for neighbor, weight in graph[start]:` / `heapq.heappush(...)` 行。

2. 公式
   观察依据

   高亮代码展示了从起始顶点进行种子化，并将其关联边压入堆中。

1. 执行 `visited.add(start)` 这一行

2. 执行 `for neighbor, weight in graph[start]:` 循环

3. 执行 `heapq.heappush(priority_queue, (weight, start, neighbor))` 这一行

4. 绿色高亮矩形

1. 高亮区域从初始化代码块移至播种语句。

2. 代码视图在 00:26 附近略微向下滚动，以显示更多循环体内容。

1. 同一段 Python 实现始终保留在屏幕上。

2. 优先队列中元组的格式保持为 `(weight, source, destination)`。

动画标记了从设置阶段到首次贪心前沿构建的过渡。

1. 动画
   观察依据

   绿色方框依次高亮显示 `while priority_queue:`、`weight, u, v = heapq.heappop(priority_queue)`、`if v not in visited:`、三条更新语句，以及内部的邻居入队代码块。

2. 公式
   观察依据

   当前可见的代码展示了完整的贪心循环及扩展步骤。

1. 当优先队列非空时：

2. 从优先队列中弹出堆顶元素

3. 如果顶点 v 尚未被访问过：

4. 将顶点 v 加入已访问集合

5. 将边 (u, v) 加入最小生成树的边集

6. 总代价增加 weight

7. 内层 `for neighbor, weight in graph[v]:` 循环块

8. 绿色高亮矩形

1. 高亮区域按执行顺序逐组推进，每次覆盖一组语句行。

2. 代码视图自动滚动，使函数的下半部分显现出来。

1. 堆始终优先提供权重最小的候选边。

2. 接受判定依据是顶点 `v` 是否已在 `visited` 集合中。

移动的方框将静态代码转化为算法贪心循环的时间演进过程。

1. 图示
   观察依据

   一张米色幻灯片，标题为“时间复杂度”，上面依次显示并逐步化简若干公式。

2. 动画
   观察依据

   表达式从 `$O(E)$` 变为 `$O(E) + O(E \log V)$`，再变为 `$O(E \log V)$`。

1. 标题“时间复杂度”

2. 公式 `$O(E)$`

3. 公式 `$O(E) + O(E \log V)$`

4. 公式 `$O(E \log V)$`

1. 最初仅显示 `$O(E)$`。

2. 随后追加 `+ $O(E \log V)$`。

3. 最后整个表达式简化为 `$O(E \log V)$`。

1. 幻灯片背景与标题保持不变。

2. 变量 `E` 和 `V` 在整个序列中保持相同的含义。

视觉上的简化过程，对应于口头论述中‘堆操作主导边扫描’这一观点。

1. 图示
   观察依据

   同一张幻灯片在时间复杂度结果下方添加了绿色标题 `SPACE COMPLEXITY`。

2. 动画
   观察依据

   空间复杂度公式逐项增长，随后化简为 `$O(V + E)$`。

1. 标题 `SPACE COMPLEXITY`

2. 公式 `$O(V + E)$`

3. 公式 `$O(V + E) + O(V)$`

4. 公式 `$O(V + E) + O(V) + O(E)$`

5. 公式 `$O(V + E) + O(V) + O(E) + O(V)$`

6. 最终公式 `$O(V + E)$`

1. 一个新的标题出现在时间复杂度结果的下方。

2. 各项依次加入图存储、已访问集合、优先队列和最小生成树边列表。

3. 求和表达式被简化为总时间复杂度 `$O(V + E)$`。

1. 先前得到的时间复杂度结果 `$O(E \log V)$` 仍显示在上方。

2. `V` 和 `E` 继续分别表示顶点数与边数。

分阶段累加的方式明确展示了在渐近简化之前，各数据结构对内存占用的贡献。

1. 声音
   观察依据

   讲述者明确对比了边数过少导致不连通、边数过多导致出现环的情形。

有人可能认为生成树的边数可以少于或大于 V - 1 条，但仍为有效生成树。

少于 V - 1 条边无法连接全部 V 个顶点，而多于 V - 1 条边则必然引入环；因此，一棵生成树必须恰好含有 V - 1 条边。

1. 声音
   观察依据

   讲解反复将选择范围限定在与当前树相连的边上，再从中选出权重最小的一条。

2. 动画
   观察依据

   仅黄色树顶点的边界边在红色选择前被高亮为绿色。

人们可能误以为普里姆算法只是在每一步从整个图中任意挑选权重最小的边。

视频指出，普里姆算法选取的是从当前树跨越到外部顶点的、权重最小的边，而非任意的全局未使用最小权重边。

1. 声音
   观察依据

   在 00:36-00:47 处，讲解者说：“将当前节点所连接的所有边压入优先队列。”

2. 公式
   观察依据

   屏幕上显示的代码中，在 `heapq.heappush(priority_queue, (weight, v, neighbor))` 前实际包含 `if neighbor not in visited:` 判断。

可从讲解推断：当前节点的每一条关联边都被无条件地压入优先队列。

屏幕上展示的实现仅压入邻居节点尚未进入 `visited` 集合的边；而讲解所述范围比屏幕上显示的代码更宽泛。

1. 声音
   观察依据

   该片段描述了返回最小生成树的边集及其总代价，但未说明连通性这一前提条件。

2. 公式
   观察依据

   代码本身并未显式检查是否所有顶点均已被访问到。

仅看这段代码片段，可能让人误以为它对任意输入图都总能生成一棵生成树。

分析说明：对于连通的带权图，最小生成树存在；若图不连通，则所示过程生成的是最小生成森林而非单棵生成树。这一条件在视频片段中未被提及。

1. 声音
   观察依据

   讲解员将普里姆算法介绍为求解该示例图最小生成树的方法。

普里姆算法被呈现为一种构造最小生成树的方法。

1. 声音
   观察依据

   讲解员指出，优先队列用于存储边，以便快速获取权重最小的边。

优先队列是实现普里姆算法中贪心选边步骤所采用的数据结构。

1. 声音
   观察依据

   讲解员特别指出，V - 1 条边这一性质适用于任意最小生成树。

边数公式是生成树定义中所包含的结构性质，因而也适用于最小生成树。

1. 图示
   观察依据

   该代码定义了 `prims_algorithm` 函数，并使用 `heapq` 模块，配合一个已访问节点集合和一个候选边堆。

这段 Python 代码实现了前文所讲解的普里姆算法步骤。

1. 动画
   观察依据

   对示例图的手动执行过程严格遵循前文所述的贪心规则。

该示例在一幅具体的带权图上展示了这一抽象方法。

1. 公式
   观察依据

   初始化代码块定义了紧随其后立即使用的容器，包括 `visited.add(start)` 和首个 `heapq.heappush` 循环中用到的容器。

播种步骤必须等待优先队列、已访问集合、边列表以及代价累加器全部创建完毕后才能执行。

1. 公式
   观察依据

   首批入队的边填充了 `priority_queue`，随后该队列被 `while priority_queue:` 和 `heapq.heappop(priority_queue)` 消耗。

主贪心循环作用于初始播种步骤所构建的前沿（frontier）。

1. 公式
   观察依据

   只有当 `v not in visited` 为真时，才执行 `visited.add(v)`、`mst_edges.append((u, v))`、`total_cost += weight` 以及邻居扩展循环。

仅当最小候选边被弹出且其终点通过已访问测试后，该边才被接受，前沿才得以扩展。

1. 公式
   观察依据

   被接受的边与累积的代价分别存入 `mst_edges` 和 `total_cost`，而这二者正是 `return mst_edges, total_cost` 所返回的值。

最终输出依赖于每次接受步骤中所构建的记录。

1. 声音
   观察依据

   时间复杂度解释中提到的遍历边并将其压入优先队列的操作，正是循环体内的操作。

2. 公式
   观察依据

   该幻灯片从相同的基于堆的操作中推导出 `$O(E \log V)$`。

时间界通过对主循环中反复执行的弹出与压入操作行为进行分析而得到。

1. 声音
   观察依据

   空间说明中提到了图、已访问集合、优先队列以及最小生成树边列表。

2. 公式
   观察依据

   这些结构恰好是在代码中初始化、并在幻灯片上求和的那些结构。

空间界是通过将初始化阶段引入的数据结构所需的内存开销相加而得出的。

1. 图示
   观察依据

   同一张幻灯片在 `SPACE COMPLEXITY` 上方展示了 `TIME COMPLEXITY`，但二者最终表达式不同。

该视频片段区分了运行时开销（主要由堆操作主导）与内存开销（主要由存储图及辅助结构主导）。

1. 声音
   观察依据

   开篇解说直接定义了这一概念。

1. 最小生成树定义

1. 声音
   观察依据

   讲解员先说明贪心构造思路，再通过一个示例加以演示。

1. 普里姆算法的高层方法
2. 示例：在含六个顶点的带权图上运行普里姆算法
3. 在示例图上逐步执行普里姆（Prim）算法的过程

1. 声音
   观察依据

   讲解员借助图的不连通性与环路特性来解释其原理。

1. 生成树的边数公式
2. 任意最小生成树中的边数
3. 为什么生成树具有 V - 1 条边

1. 声音
   观察依据

   讲解员指出，优先队列能够快速检索出权重最小的边。

1. 优先队列作为选边结构
2. Prim算法的Python实现框架

1. 图示
   观察依据

   可见的 Python 代码介绍了实现结构。

1. 本片段未展示完整的函数体。

1. Prim算法的Python实现框架

1. 动画
   观察依据

   所选的红色边为 AB、BD、DC、AF，其可见权重分别为2、2、1、3。

1. 示例：在含六个顶点的带权图上运行普里姆算法
2. 在示例图上逐步执行普里姆（Prim）算法的过程

1. 公式
   观察依据

   初始化语句在屏幕上可见，并配有语音讲解。

1. Prim 算法实现的初始化变量。

1. 声音
   观察依据

   讲解员解释了如何添加起始节点并将其邻接边压入堆中。

2. 公式
   观察依据

   对应的代码在屏幕上被高亮显示。

1. 从起始顶点启动普里姆算法。

1. 公式
   观察依据

   代码在从堆中弹出元素后立即显示 `if v not in visited:`。

2. 声音
   观察依据

   讲解者指出，该算法会检查当前节点是否已在已访问集合中。

1. 主循环：提取权重最小的候选边

1. 公式
   观察依据

   高亮代码块更新 `visited`、`mst_edges`、`total_cost`，并压入新的边。

1. 接纳一个新顶点，记录对应边，并扩展搜索边界

1. 声音
   观察依据

   讲解者明确指出了邻接表表示法这一前提假设。

1. 从起始顶点启动普里姆算法。

1. 公式
   观察依据

   幻灯片将时间复杂度简化为 `$O(E \log V)$`。

2. 声音
   观察依据

   讲解者解释了对边的遍历以及对堆进行对数级次数的插入操作。

1. 基于堆实现的 Prim 算法的时间复杂度