视频字幕
最小生成树是图论中的重要概念。对于一个连通的加权无向图，最小生成树是连接所有顶点的树形子图，具有最小的总权重。它必须连通所有顶点，不能有环，边数等于顶点数减一。最小生成树在网络布线、道路建设等实际问题中有广泛应用。现在我们看到一个示例图的最小生成树转换过程。
Kruskal算法是求最小生成树的经典算法之一。它的核心思想是贪心策略：按边的权重从小到大排序，然后依次考虑每条边，如果这条边连接的两个顶点不在同一个连通分量中，就将这条边加入最小生成树。算法使用并查集数据结构来高效地检测是否会形成环。让我们看这个示例图，所有边按权重排序后的顺序是：BE权重1最小，然后是AD和EF都是2，接着是BC和DE都是3，AB是4，CF最大是5。
现在开始演示Kruskal算法的完整执行过程。首先选择权重最小的边BE，权重为1，不会形成环，加入最小生成树。接下来选择AD，权重为2，同样不形成环，加入结果。然后选择EF，权重为2，仍然安全。继续选择BC，权重为3，可以加入。最后选择AB，权重为4，完成最小生成树的构建，总共选择了5条边连接6个顶点。
Prim算法是另一种经典的最小生成树算法。与Kruskal算法不同，Prim算法采用顶点扩展的策略：从任意一个顶点开始，逐步向外扩展生成树。每次选择连接已访问顶点和未访问顶点的最小权重边。这种方法更关注顶点之间的连接关系，而不是全局的边排序。Prim算法特别适合稠密图，因为它只需要维护候选边集合，而不需要对所有边进行排序。
现在演示Prim算法的完整执行过程。从顶点A开始，将其标记为已访问。然后寻找连接A和未访问顶点的最小权重边，选择AD权重2。接下来从已访问的A和D中寻找候选边，选择BE权重1。继续这个过程，依次选择EF权重2、BC权重3，最后选择CF权重5，完成最小生成树的构建。Prim算法通过逐步扩展已访问顶点集合来构建最小生成树。