第3讲最小生成树.ppt

第3讲最小生成树
第1页，共21页，编辑于2022年，星期一
一、树及其性质
树：
图论中把不包含圈的连通图称为树，记为T;不包含圈的图称为无权圈图；图G的连通无圈子图称为G的树；包含图G的所有顶点的G的树为图G的一棵圈法求出下图的另一棵生成树.
不难发现，图的生成树不是唯一的 .
第12页，共21页，编辑于2022年，星期一
3) 最小生成树与算法
介绍最小树的两种算法：
Kruskal算法和Prim破圈法.
第13页，共21页，编辑于2022年，星期一
A Kruskal算法（或避圈法）
步骤如下：
1) 选择边e1，使得w(e1)尽可能小；
2) 若已选定边 ，则从
中选取 ，使得:
i) 为无圈图，
ii) 是满足i)的尽可能小的权，
3) 当第2)步不能继续执行时，则停止.
定理 由Kruskal算法构作的任何生成树
都是最小树.
第14页，共21页，编辑于2022年，星期一
例: 用Kruskal算法求下图的最小树.
在左图中 权值
最小的边有 任取一条
在 中选取权值
最小的边
中权值最小边有 , 从中选
任取一条边
会与已选边构成圈,故停止.
中选取在中选取
中选取 . 但 与 都
第15页，共21页，编辑于2022年，星期一
【Kruskal算法的MATLAB实现】
function [T c]=krusf(d,flag)
if nargin==1
n=size(d,2);
m=sum(sum(d~=0))/2;
b=zeros(3,m);
k=1;
for i=1:n
for j=(i+1):n
if d(i,j)~=0
b(1,k)=i;b(2,k)=j;
b(3,k)=d(i,j);
k=k+1;
end
end
end
else
b=d;
end
第16页，共21页，编辑于2022年，星期一
n=max(max(b(1:2,:)));
m=size(b,2);
[B,i]=sortrows(b',3);
B=B';
c=0;T=[];
k=1;t=1:n;
for i=1:m
if t(B(1,i))~=t(B(2,i))
T(1:2,k)=B(1:2,i);
c=c+B(3,i);
k=k+1;
tmin=min(t(B(1,i)),t(B(2,i)));
tmax=max(t(B(1,i)),t(B(2,i)));
for j=1:n
if t(j)==tmax
t(j)=tmin;
end
end
end
if k==n
break;
end
end
T;
c;
第17页，共21页，编辑于2022年，星期一
B：Prim算法
步骤如下：
从图G中某一顶点出发，任选一最小权边。
2）将其顶点加入到生成树的顶点集合U中。
3）从一个顶点在U中，一个顶点不在U中的各条边中任取最小权边，加入到生成树中。
例 用Prim算法求下图的最小树.
第18页，共21页，编辑于2022年，星期一
【Prim算法的MATLAB实现】
function [T c]=Primf(a)
l=length(a);
a(a==0)=inf;
k=1:l;
listV(k)=0;
listV(1)=1;
e=1;
while (e<l)
min=inf;
for i=1:l
if listV(i)==1
for j=1:l
if listV(j)==0 & min>a(i,j)