n 几种求解最小生成树的算法及其应用
孔祥男
（青海师范大学数学系，青海 810000） 摘要：本文讲述了几种求解最小生成树的算法（Kruskal 算法、Prim 算法、破圈法和 DNA 算法），重点介绍了一种求解最小生成树问题的 DNA 算法，进而比较这几种算法的优 缺点以及介绍最小生成树的几个实际应用。 关键字：最小生成树 Kruskal 算法 Prim 算法 破圈法 DNA 算法
4 key[r] ← 0 5 Q ←VG 6 while Q≠ ∅ 7 8 9 10 11 4.2 Prim 算法的复杂性 下面简单分析一下 Prim 算法的复杂性。第一次执行第 2 步是 n-2 次比较， 第二次为 n-3 次比较，第三次是 n-4 比较，„，因此总的比较为2 n − 2 (n − 1)次。在执行第 3 步时，第一次是 n-2 次比较，第二次 n-3 次比较，„，因此 总的比较为（n-2）（n-1）次。由此算法的总计算量约为 O n2 .
1 引言 最小生成树是网络最优化中一个重要的图论问题，它在交通网、电力网、 电话网、管道网等设计中均有广泛的应用。比如要在 n 个城市间建立通信联络 网，要考虑的是如何保证 n 点连通的前提下最节省经费，就应用到了最小生成 树。 求图的最小生成树有两种常见的算法，一种是 Kruskal（克鲁斯卡尔）算 法，另一种是 Prim（普里姆）算法。这两个算法的基本思想均是基于避圈法， 而从相反的角度，破圈法也可构造最小生成树算法。 本文讲述 Kruskal 算法、Prim 算法和破圈法的同时，也着重介绍了一种求 解最小生成树问题的 DNA 算法。 2 有关最小生成树的理论基础 2.1 有关最小生成树的概念 2.1.1 定义一（图） 一个图 G 定义为一个偶对（V,E）,记作 G=（V,E），其中 （1） （2） V 是一个集合，其中的元素称为顶点； E 是无序积 V������V 中的一个子集合，其元素称为边；
Several algorithm of solving minimum spanning tree and its application
Xiangnan-kong
(Mathematics Department of Qinghai Normal University, Qinghai 810000) Abstract: This paper describes several algorithm of solving minimum spanning tree （Kruskal algorithm、Prim algorithm、Broken circle method and DNA algorithm）, and focuses on discussing the DNA algorithm. Then it compares the advantages and disadvantages of several algorithms and introduces several practical applications of the minimum spanning tree . Keyword: Minimum spanning tree；Kruskal algorithm；Prim algorithm； Broken circle method ；DNA algorithm.
5
图4 6 一种求解最小生成树问题的 DNA 算法 6.1 DNA 算法介绍 基于生化反应的生物智能计算是现阶段计算领域研究的热点，DNA 计算是 通过 DNA 分子之间的生化反应来进行计算的一种计算模式，凭借运算巨大的并 行性和海量存储的优势，DNA 计算在解决复杂运算问题方面的计算能力显而易 见。设计了一种利用 DNA 计算来求解图的最小生成树的计算模型，采用一种特 殊的编码方式来对顶点，边和权值进行编码，从而解决最小生成树问题。 6.1.1 DNA 计算的基本原理 DNA 计算的本质就是利用大量不同的核酸分子杂交，产生类似于某种数学 过程的一种组合的结果，并根据限定条件对其进行筛选的。单链 DNA 可看作由 符号 A、C、G、T 组成的串,同电子计算机中编码 0 和 1 一样,可表示成 4 字母的 集合来译码信息。特定的酶可充当“软件”来完成所需的各种信息处理工作。 DNA 计算的基本思想是：利用 DNA 分子的双螺旋结构和碱基互补配对的性 质,将所要处理的问题编码成特定的 DNA 分子,在生物酶的作用下,生成各种数据
图5 从图 5 中 K-臂 DNA 分子的结构可以看出，通过连接酶，我们可以利用 K-臂（K ≤4）DNA 分子构造出任意顶点的最大度为 4 的图。正是利用这一思想，我们 用 K-臂分子来表示图或树中度为 n（n≤4）的顶点的结构，来实现最小生成树 问题解的节点结构。在求解最小生成树问题计算模型的编码方案中，使用的 DNA 分子是由单链和双链进行混合编码的不完全分子。 6.1.3 最小生成树编码的分子结构 本节介绍最小生成树中顶点、支架分子、权值和边的编码方式，以图 6 的 连1,转向第 2 步；否则，置j： = j + 1，转向第 2 步。 MST-KRUSKAL(G,w)
2
1 A→∅ 2 for each vertex ϑ ∈ V G 3 do Make-Set(v)
4 sort the edge of E into nondecreasing order by weight w 5 for each edge μ, ϑ ∈ E,taken in nondecreasing order by weight 6 7 8 9 retuen A 3.2 Kruskal 算法的复杂性 首先在第 1 步中把边按权的大小由小到大地排列起来，这约需 m﹒log 2 m 次比较；其次第 2 步最多循环 n 次；在第 3 步中判断 G [S⋃ aj ]是否构成回路， 判定加边后是否构成回路总共约需 m 次比较，而加边后点的重新标号最多需 n(n-1)次比较。所以总的计算量为 m﹒log 2 m+n+m+ n(n-1)~O n2 log 2 n 由定理一（1）易见上述算法的正确性。 3.3 例如在图 1 所示的网络中，求一个最小树，计算的迭代过程如图 2 所示 do if Find-Set(u)≠Find-Set(v) then A ← A ∪ u, v
2.1.2 定义二（树）：不含圈的连通图称为树。
1
2.1.3 定义三（生成树）：如果 T 是 G 的一个生成子图而且又是一棵树，则称 T 是图 G 的一棵生成树。 2.1.4 定义四（最小树）：设T ∗ 是赋权图 G 的一颗生成树，若对 G 的任意生成 树 T 都有������ T ∗ < ������ (������),则称T ∗ 为 G 的最小树。 2.2 有关最小生成树的定理 2.2.1 定理一（最小树充要条件） 设 T 是 G 的一棵生成树，则下列条件都是 T 为最小树的充要条件 (1) 对任意连枝 e′∈G\T,有������ (e′)=maxe ∈C T (e ′) {(������(e))} (2) 对图 G 中任意圈 C,存在 e′∈C\T，有������ (e′)=maxe ∈C {������ (e)} (3)对任意树枝 e∈T,有������ (e)=mine ∈S T (e) {(������(e′))} (4)对 G 的任意割集 S，在 T∩S 中存在一条边 e，������ (e)=mine ′∈S T (e) {������(e′)} 2.2.2 定理二（唯一最小树充要条件） 设T ∗ 是 G 的一棵生成树，则下列条件都是T ∗ 是 G 的唯一最小树的充要条件 是下列两个条件中的任一个成立： （1）对任意 e∈G\T ∗ ，e 是CT ∗ (e)的唯一权最大的边。 （2）对任意e∗ ∈ T ∗ ，e∗ 是ST ∗ (e∗ )的唯一权最小的边。 3 Kruskal（克鲁斯卡尔）算法 3.1 Kruskal 算法介绍 Kruskal 算法是 1956 年首次提出的求最小生成树的算法。后来 Edmonds 把这个算法称为贪心算法。其基本思路是从 G 的 m 条边中选取 n-1 条权尽量小 的边，并且使得不构成回路，从而构成一个最小树。下面我们就来叙述这个算 法. 第 1 步 开始把图的边按权的大小由小到大地排列起来，即将图的边排序为 a1 , a2 , … , am ,使W a1 ≤ W a2 ≤ ⋯ ≤ W am 置 S=∅，������ = 0, ������ = 1. 第 2 步 若|S|= ������ = n − 1,则停止。这时 G [S]=T 即为所求；否则，转向第 3 步。 第3步 若 G [S⋃ aj ]不构成回路，则置e ������+1 = aj , S = S⋃{e ������+1 }, ������ ≔ ������ +
4
1
do u ← Extract − Min Q for each v ∈ Adj u do if v ∈ Q and w(u,v)< key[v] then π v ← u key[v] ← w(u, v)
4.3 例如在图 1 所示的网络中，求一个最小树，计算的迭代过程如图 3 所示
图3 5 破圈法 5.1 破圈法介绍 该算法的理论依据是存在性定理：连通图至少有一棵生成树。如果我们给 的连通图 G 中没有回路，那么 G 本身就是一棵生成树，若 G 中只有一个回路， 则删去 G 的回路上的一条边（不删除结点），则产生的图仍是连通的，且没有 回路，则得到的子图就是图 G 的一棵生成树，若 G 的回路不止一个，只要删去 每一个回路上的一条边，直到 G 的子图是连通没有回路且与图 G 有一样的结点 集，那么这个子图就是一棵生成树。由于我们破坏回路的方法可以不一样（即 删去的边不一样）所以可得到不同的生成树，但是在求最小生成树的时候，为 了保证求得的生成树的树权 W（T）最小，那么在删去回路上的边的时候，总是 在保证图仍连通的前提下删去权值较大的边。尽量保留权值较小的边。这就是 所谓的破圈法。破圈法就是在带权图的回路中找出权值最大的边，将该边去掉， 重复这个过程，直到图连通且没有圈为止，保留下来的边组成的图即为最小生 成树。破圈法的复杂程度为 O n3 . 5.2 例如在图 1 所示的网络中，求一个最小树，计算的迭代过程如图 4 所示