实用数学方法：最小生成树

设G是一个边赋权的连通无向图，G的生成树各边的权值和称为该生成树的权，其中权最小的生成树称为最小生成树。

许多网络问题可以归结为最小生成树问题。例如，光纤铺设问题、供水供电系统的设计等。

目前有许多算法可用来求赋权连通简单图的最小生成树，其中最常用的是Prim算法和Kruskal算法。下面介绍这两种算法。

1. Prim算法

Prim算法的基本思想：从任意节点出发（假设从P={u}出发），选取与其关联且权最小的边以及该边的另一个关联节点v，两点及边构成一个图H，同时P=P+{v}，在V（ G)-P中选取与P中的所有节点关联的权最小的边及该边关联的节点，并将其并入H，如此反复，直到H中包含所有节点。

算法过程如下：

输入：图的邻接矩阵。

输出：最小生成树及对应的权。

第一步：令P={v1}，H=∅；

第二步：对于∀e =vi vj ，其中vi ∈P, v j ∈V (G )-P ，若e=min{w( vi vj )}，则H =H ∪{e, vj}；

第三步：若V (H)=V (G)，停止，否则转第二步。

例1 假设某地区要修建一个连接若干城镇的公路系统，如图3.3.1所示。已知i城市与j城市之间造价是ci j，试设计一个造价最低的方案。

图3.3.1

解 应用Prim算法，编写通用的MATLAB函数形式如下：

运行结果为

(www.xing528.com)

2. Kruskal算法（避圈法）

Kruskal算法的基本思想：将图G的边的权值从小到大排列，每次取最小的边归入H中，若某条边与原来的边构成圈，则舍去，直到H中包含n-1条边为止。

算法过程如下：

第一步：将G的m条边按从小到大顺序排序，令H=∅；

第二步：从小到大顺次取e1至em，若ei与前面的边不构成圈，则H=H∪{ei}；

例2 应用Kruskal算法编写例1的程序。

解 应用Kruskal算法，编写通用的MATLAB函数形式如下：

result仍为3×n矩阵，第1、2、3行分别为起点、终点及权值，赋初值为空。

Kruskal算法也叫避圈法，为避免出现圈的情况，应用index存放各边端点信息，如果某条边选中，就将所有边中与此终点标号v2相同的，都修改为v2=v1，后面继续循环时，凡是v2=v1的情况，都排除在最小生成树之外，避免了圈的出现。

输入

a(1, [2, 3, 4]=[6, 10, 12]; a(2, [3, 5, 6]=[2, 14, 6]; %矩阵的另一种输入方式，注意此时与prim算法不同的是其余元素均为0

a(3, [4, 5, 6]=[5, 9, 7]; a(4, 6)=5;

a(5, [6, 7])=[8, 11]; a(6, 7)=16;

[result]=myKrus(a)

输出与例1相同。