Page 217 - 数学建模算法与应用

第八章 图与网络模型及方法应用

prim 算法如下：
1. P={v1}，Q =F；
2.while P ~=V

找最小边 pv ，其中 pÎP，vÎV － P
P=P ＋ {v}
Q=Q ＋ {pv}
end

图 8-4 最小生成树问题

例 用 prim 算法求图 5 的最小生成树。
我们用 result3×n 的第一、二、三行分别表示生成树边的起点、终点、权集合。
Matlab 程序如下：

clc；clear；
a=zeros(7)；
a(1，2)=50； a(1，3)=60；

a(2，4)=65； a(2，5)=40；
a(3，4)=52；a(3，7)=45；
a(4，5)=50； a(4，6)=30；a(4，7)=42；
a(5，6)=70；

a=a+a’；a(find(a==0))=inf；
result=[]；p=1；tb=2：length(a)；
while length(result)~=length(a)-1

temp=a(p，tb)；temp=temp(：)；
d=min(temp)；
[jb，kb]=find(a(p，tb)==d)；

207