最小生成树matlab.doc

. .
- 优选
prim算法
设置两个集合P和Q，其中P 用于存放G的最小生成树中的顶点，集合Q存放G的最小生成树中的边。令集合P的初值为P={V1}〔假设构造最小生成树时，从顶点V1出发〕，集合Q的初值为。Prime算法的思想是，从所有p ∈P，v∈V-P的边中，选取具有最小权值的边pv,将顶点v参加集合P中，将边pv 参加集合Q中，如此不断重复，直到P=V时，最小生成树构造完毕，这时集合Q中包含了最小生成的所有边。〔找最小的权，不连成圈即可〕
clc;clear;
M=1000;
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;zeros(2,7)];
a=a+a';a(find(a==0))=M;
result=[];p=1;tb=2:length(a);
while length(result)~=length(a)-1
temp=a(p,tb);temp=temp(:);
d=min(temp);
[,kb]=find(a(p,tb)==d);
j=p((1));k=tb(kb(1));
result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
end
result
例 、一个乡有7个自然村，其间道路如下图，要以村为中心建有线播送网络，如要求沿道路架设播送线，应如何架设？
. .
- 优选
Kruskal算法
每步从未选的边中选取边e，使它与已选边不构成圈，且e
是未选边中的最小权边，直到选够n-1条边为止。
clc;clear;
M=1000;
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;
[i,j]=find