最小生成树的两种构造方法样稿.docx

离散数学大作业
---最小生成树


姓名：陈强
学号：
教导老师：李阳阳
一、最小生成树概念：
给定一个连通图，要求结构含有最小代价生成树时，也即使生成树各边权值总和达成最小。把生成树各边权值总和定义为生成树权，那么含有最小权值生成树就组成了连通图最小生成树，最小生成树可简记为MST。
二、结构无向连通图最小生成树方法：
Prim（普里姆）算法
算法:
假设G(V,E)是有n个顶点无向连通图，用T(U,TE)表示要结构最小生成树，其中U为顶点集合，TE为边集合。
初始化：令V={} ,TE={}。从V中取一个顶点u0放入生成树顶点集U中，作为第一个顶点，此时T=（{u0}，{}）；
从边（u,v）中找一条代价最小边，将其放入TE中，并将放入U中。
反复步骤（2），直至U=V为止。此时TE集合中必有n-1条边，T即为所要结构最小生成树。
特殊处理：假如两个顶点之间没有直接相连边，权值置为一个max数
本身和本身权值置为MAX值
代码：
function [T]=Prim(i,G_dist)
%
%T是返回最小生成树
%i为输入为最小生成树选定第一个顶点
%G_dist是待输入数据，是图G边（u,v）权值矩阵
[m,n]=size(G_dist);%读入无向图顶点数目为m=n
v=i;%将选定顶点放入中间变量v中
T=zeros(3,m-1);%最小生成树有（m-1）条边。第一行存放边起点，第二行存放边终点，第三行存放边权值
%%
%初始化最小生成树矩阵
for j=1:m-1
T(1,j)=v;%将第一个顶点放入最小生成树矩阵中
if j>=v
T(2,j)=j+1;
T(3,j)=G_dist(v,j+1);
else
T(2,j)=j;
T(3,j)=G_dist(v,j);
end
end
%%
%求第k条边
for k=1:(n-1)
min=10000;%初始化一个最小权值
%找出最短边，并将最短变下标统计在mid中
for j=k:(n-1)
if T(3,j)<min
min=T(3,j);
mid=j;
end
end
e=T(:,mid);T(:,mid)=T(:,k);T(:,k)=e;%将最短边所在一列和第k列交换
v=T(2,k);%v中存放新找到最短边在V-U中顶点
for j=(k+1):(n-1)%修改所存放最小边集
d=G_dist(v,T(2,j));
if d<T(3,j)
T(3,j)=d;T(1,j)=v;
end
end
end
DG=sparse(T(1,:),T(2,:),T(3,:),m,m);%用稀疏矩阵
view(biograph(DG,[],'ShowArrows','off','ShowWeights','on'));%画图
调用函数
G=[10000,10,3,10000,10000,10000;10,10000,5,8,6,10000;3,5,10000,10000,2,10000;10000,8,10000,10000,7,11;10000,6,2,7,10000,17;10000,10000,10000,11,17,10000;];
%G表示图G各边权值，本身到本身权值和不直接相连顶点权值设为10000
i=1;
T1=[1,2,1,3,2,2,4,4,5;3,3,2,5,5,4,5,6,6;3,5,10,2,6,8,7,11,17;0,0,0,0,0,0,0,0,0];
%T1表示图G边信息，第一行是边起始点，第二行是边终点，第三行是边权重，第四行表示对边选择
T=T1(1:3,:);
DG=sparse(T1(1,:),T1(2,:),T1(3,:),m,m);%用稀疏矩阵
view(biograph(DG,[],'ShowArrows','off','ShowWeights','on'));%画图
Prim(i,G);
结果：
图G