引言

在2023年计算机课程思政虚拟教研室研讨会与导教研修班上，陈国良院士强调计算教育应催生新认知、科学发现与技术创新的思考。计算学科课程思政教学指南强调科学思维不可或缺，并拆分为三个核心过程^[1]。最小生成树问题是图论中的经典问题，在许多实际应用中都有广泛的应用，例如网络设计、电路设计、通信系统等。Prim算法是求解最小生成树的经典算法之一，具有简单易懂、效率高等特点^[2]。然而，传统的算法类教学往往忽视了对计算模型的构建，导致学生对算法的理解和应用能力不足。本文以最小生成树的求解为例，探讨如何构建其逻辑模型，给出基于模型的算法，并分析算法的正确性和复杂性。通过将算法求解过程拆分为抽象、理论和设计三个学科形态，旨在降低问题求解的复杂性，提高学生解决复杂问题的能力，并推动算法类课程的教学改革。

一．求最小生成树的Prim算法的问题描述

给定一个无向连通带权图G = (V, E, W)，其中V表示图中顶点构成的集合，E ⊆ V×V为图中的所有边构成的集合，权重函数W : E → R+，映射每条边到非负实数值的权重上。图G的一个子图是一棵树，如果它包含图G中的所有顶点，并且恰好有V-1条边，则称这棵树为图G的一棵生成树^[3]。生成树的权重是构成该生成树的所有边上的权重之和。图G的最小生成树是所有生成树中权重最小的一棵树。最小生成树问题就是在给定的带权连通图中，找出其最小生成树。

为了解决最小生成树问题，可以采用一种称为Prim算法的贪心策略。Prim算法的基本思想是从某个顶点开始，逐渐向外扩展生成树，每次选择一条连接生成树和未加入生成树的顶点之间权重最小的边，将其加入到生成树中，直到所有顶点都被加入到生成树中^[4]。

为了展示Prim算法在抽象、理论和设计3个过程中的具体内容，设计了求最小生成树问题的Prim形式模型与算法步骤，并证明了算法的正确性和分析了算法的时间复杂度，最后给出了算法实现，使得该问题的解决过程简单易读，读者可以从问题的形式模型出发，通过一步步推演求解问题^[5]。

二．Prim算法的抽象形态

Prim算法的抽象形态，包括Prim基本逻辑、形式模型。

Prim基本逻辑:

利用Prim算法构造一个连通网的最小生成树的过程可描述如下：

设连通网G=(V，E，W)，其最小生成树T=(V，TE)，V是连通网G中全部n个顶点的集合，TE为最小生成树T中边的集合。

（1）初始时，选择连通网G中的一个顶点s为出发点（根节点），此时，最小生成树T的顶点集S={s},边集TE为空集。

（2）在V-S中选择一个与S中的顶点相邻接的顶点v，使得v与S中的某个顶点所构成的边是一条权值最小的边，并将该边并入集合TE，将顶点v并入S。

（3）重复步骤（2），直到S=V。此时，最小生成树T中已包含连通网G中的全部n个顶点，且TE中仅含有n-1条权值最小的边，则T=(V，TE)为连通网G的最小生成树。

Prim形式模型:

Prim形式模型是一个五元组Prim=(G,T,l,p,s)，其中：

（1）G=(V, E, W)：带权无向连通图，V为顶点集，E为边集，W为权值函数。

（2）T=(V,TE | TE ⊆ E)：G的最小生成树，即包含G中所有顶点的边集，且边的总权重最小。

（3）l:V→R+∪{∞}：最短距离数组，记录每个顶点到最小生成树的最短边的权重。

（4）p:V→V ∪{-1}：前驱数组，记录每个顶点的前驱顶点，用于回溯最小生成树。

（5）s ∈ V：最小生成树的根节点。

模型描述：

（1）初始化

将最小生成树T初始化为空集，T=∅。

将出发点（根节点）s加入S，并设置 S={s}。

将其他顶点i的最短距离l(i)设置为∞，前驱p(i)设置为-1。

（2）迭代

当T中不包含所有顶点时，重复以下步骤：

在V-S中找到与S连接最短的顶点v，即l(v) = min{l(v) | v∈V-S}。

将v加入S，并更新S=S U{v}。

对于V-S中与v相邻的顶点u，如果(v, u)∈E-TE，则更新TE=TE U {(u, v)}，并设置p(u) = v。

（3）终止

当V-S为空时，算法终止，此时T(V,TE)即为G的最小生成树。

三． Prim算法的理论推导证明

Prim算法的理论形态同样包括算法正确性证明和时间复杂度分析。

(1）Prim算法的正确性

引理1：在带权无向连通图中，对于任意两个不相交的顶点集合S和V-S，总存在一条边(u, v)，其中u属于S，v属于V-S，并且这条边的权重是最小的。

证明：我们假设存在另一条边(x, y)，其中x属于S，y属于V-S，并且权重小于(u, v)的权重。这与我们选择(u, v)作为最小权重的边矛盾。因此，引理1成立。

假设不成立。

假设Prim算法不能生成最小生成树，那么存在另一棵生成树T’，其总权重小于由Prim算法生成的生成树T的总权重。

定理：Prim算法能够生成连通加权图G的最小生成树。

证明循环不变式：在Prim算法的每次迭代之前，集合TE包含了最小生成树的一部分，且其所有边的总权重加上集合S和V-S之间所有边的最小权重，不会超过任何最小生成树的总权重。

初始：在算法开始时，TE为空集，S只包含一个顶点s。因此，TE的总权重为0，且没有边连接S和V-S。根据循环不变式，这是成立的。

保持：假设循环不变式在迭代i之前成立，我们需要证明在迭代i之后它仍然成立。

在迭代i中，算法选择了一条连接S和V-S的最小权重边(u, v)。根据引理1，这条边是存在的。将v添加到S中，并将(u, v)添加到TE中，不会形成环，因此TE仍然是生成树的一部分。由于(u, v)是连接S和V-S的最小权重边，根据循环不变式的定义，TE加上(u, v)的权重不会超过任何最小生成树的总权重。因此，循环不变式在迭代i之后仍然成立。

终止：当算法终止时，V-S为空，即S包含了所有的顶点，且TE包含了n-1条边，其中n是顶点的数量。根据循环不变式，TE的总权重加上S和V-S之间所有边的最小权重不会超过任何最小生成树的总权重。由于V-S为空，不存在这样的边，因此TE的总权重就是最小生成树的总权重。这与我们的假设不成立相矛盾，因此，Prim算法确实能够生成最小生成树。

综上所述，定理得证，Prim算法能够生成连通加权图G的最小生成树。

(2）Prim 算法的时间复杂度

假设输入图由邻接表表示，边上的权重存放在邻接表的边结点中。对于集合S，用数组S[1.n]表示。初始时，S[1] = 1，并且对于所有的 i，2 ≤ i ≤ n，S[i] = 0，运算S ← S ∪ { j } 时，将S[j ]的值置1来实现。

对Prim算法进行初始化，花费时间为O(| V |)，找到最小生成树边权重最小的顶点花费时间为O(| V |)，总的执行for循环花费时间O(| V |²)。 由于是输入图由邻接表表示，算法需遍历其他顶点所有邻接的边，因此算法更新操作花费时间为O(| E |)，根据以上得出算法的时间复杂度为O(| V |² + | E |)。

四．Prim算法的设计与实现

Prim的设计形态包括Prim算法举例说明、C++代码实现。

（一）举例

给定一个边上权值非负的带权无向图G和源点s，如图1所示。

图1 带权无向图G

设Prim=(G,T,m,l,p,k)是一个Prim形式模型，由图我们可以得到G = (V, E, W ) ，其中

V = {s, x, y, z, u}，

E = {<s, x>,<s, z>,<x, y>,<x, z>,<x,u>,<y, u>,<y,z>,<z,u>}，

W = {<s, x, 8>,<s, z, 5>,<x, y, 1>,<x, z, 2>, <x,u,9>,<y, u, 4>,<y,z,8>,<z, u, 2>}。

利用Prim算法求连接所有顶点的边权之和最小过程如下。

初始化：

以s为初始点（根节点），将其加入集合S中，初始化集合S：S = {s}；

初始化边集TE=∅；

对于每个顶点i∈V，设置一个前驱顶点p(i)=-1和最小边权值l(i)=∞；

设置起点s的最小边权值l(s)=0。

初始化V上的函数l和p如图 2 所示。

图2 初始化

迭代：

选择、移动、更新操作迭代|V|-1=4次。

（1）第一次迭代

选择：z∈V-S且l(z)=min{l(x),l(z)}=5，故选择顶点z。

移动：将顶点z移动到S中，令S=S∪{z}={s, z}，将边(s,z)移动到TE中，令TE= TE ∪{(s,z)}。

更新：l(z)=5，p(z)=s。

（2）第二次迭代

选择：u∈V-S且l(u) = min{l(x), l(y), l(u)} = 2，故选择顶点u。

移动：将顶点u移动到S中，令S= S∪{u}= {s, z，u}，将边(z,u)移动到TE中，令TE= TE ∪ {(z,u)}。

更新：l(u) = 2，p(u) = z

（3）第三次迭代

选择：x∈V-S且l(x) = min{l(x), l(y)} = 3，故选择顶点x。

移动：将顶点x移动到S中，令S= S∪{x}= {s, z，u，x}，将边(z,x)移动到TE中，令TE= TE ∪ {( z,x)}。

更新：l(x) = 3，p(x) = z。

（4）第四次迭代

选择：y∈V-S且l(y) = min{l(y)} = 1，故选择顶点x。

移动：将顶点x移动到S中，令S= S∪{y}= {s, z，u，x，y}，将边(x,y)移动到TE中，令TE= TE ∪ {(x,y)}。

更新：l(y) = 1，p(y) = x。

求解最小生成树：

每次迭代后S中都会增加一个顶点，这样迭代| V |-1 = 4次后，V-S = ∅即S = V。由形式模型可知，当S=V时，迭代结束，生成的最小生成树为T(V,TE),如图3所示。

图3  确定从源点到每个顶点的最小生成树

（二） C++ 实现

根据Prim算法形式模型，使用C++语言实现该算法，如图4所示。

图 4  C++ 实现代码和运行结果

结束语

概念模型和形式模型在计算学科中具有重要的学科方法论性质，能够将计算学科的各个分支领域有机地联系在一起，为解决计算问题提供强大的抽象工具，同时也降低人们之间沟通的复杂性。构建Prim算法的形式模型，不仅展示其抽象形态的内容，还展示了抽象、理论和设计3个学科形态之间的相互关系^[6]。这种方式有效地将抽象的数学概念与问题求解过程相结合，使学生能够更好地理解和应用形式模型来解决具体的计算问题，不仅培养学生的抽象思维能力，还能提高他们解决实际问题的应用能力和创造能力。

参考文献：

[1] 陈国良. 计算机课程思政虚拟教研室文化建设[J]. 计算机教育, 2023(11): 1-2.

[2] Cormen T H, Leiserson C E, Rivest R L, et al. 算法导论[M]. 殷建平, 徐云, 王刚, 等译. 3版. 北京: 机械工业出版社, 2012.

[3] 董荣胜, 古天龙, 殷建平. 计算学科课程思政教学指南[J]. 计算机教育, 2024(1): 7-15.

[4] 刘荣,徐昕海,刘呈,宋钰 基于虚拟现实技术的算法可视化实验研究 ——以最小生成树Prim算法为例 信息通信 2020(4) 27-28

[5] 王新奇 最小生成树算法及其应用 西安文理学院学报（自然科学版）2009(3) 23-26

[6]钟世平,闫婷,张立飞,等.基于最小生成树算法构造有向无环图在工业控制的应用[J].石油化工自动化, 2023, 59(3):13-16.