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

最小生成树的两种构造方法
离散数学大作业
■■■最小生成树
姓名：陈强学号:**********辅导老师：李阳阳一、最小生成树的概念：
给定一个连通图，要求构造具有最小代价的生成树时，也即使生成树各边的权值总和达到和第k列交换
v=T(2,k);
%v
中存放新找到的最短边在
?
U
中的顶点
V
forj=(k+1):(n-1)%修改所存储的最小边集d=G_dist(v,T(2,j));ifd<T(3,j)T(3,j)=d;T(1,j)=v;end
endend
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
的各边权值，自身到自身的权值和不直接相连的顶点的权值设为
10000
%G
1=1;T1=[1,2J,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:
%画图
Prim生成的最小生成树:
Node1
-Node6]2?Kruskal(克鲁斯卡尔)算法算法：
假设G(V,E)是有n个顶点的无向连通图。
初始化：设置最小生成树的初始状态为只有n个顶点而无任何边的非连通图T(V,{})。
(2)依次选择E中的最小代价边，若该代价边依附于T中两个不同的连通分量，则将该边加入
TE中。否则，舍去此边而选择下一条代价最小的边。
重复步骤(2)直到所有顶点都在同意连通分量上为止。这时T就是G的一棵最小生成树代码：
function[T]=Kruscal(T1,e,m)%%T是返回的最小生成树%T1是图G的边信息%e表示的是图G中的边的数目%m是图G的顶点数目%%%初始化存放顶点连通信息的矩阵GGGG=zeros(1,m);fori=1:mGG(i)=i；end%%j=0；%直到选够)条边即可结束程序
%whilej<m-1
fori=1:e讦T1(4,i)==0%更新最小代价值，将改变标记为己经选择过的边endifGG(k)==GG(l)T1(4,i)=2;%标记为2的边为舍去的边elsej=j+1;%将最短边的两个顶点并入同一分量L=GG(l);fort=1:mifGG(t)==L;GG(t)=GG(k);endendendifj>=m-1break;endendfori=1:eifT1(4,i)==2||T1(4,i)==0T1(:,i)=[0；0;0;0];end
endT1=T1(:,any(T1));T=T1(1:3,:);DG=sparse(T(2,:),T1(3,:),m,m);%用稀疏矩阵view(biograph(DG,[],'ShowArrows',off,'ShowWeights1,on*));%画图调用函数e=9;%图G的边的数目m=6;%图G的顶点数目T仁[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仃1(1,:),T1(2,:),T1(3,:),m,m);%用稀疏矩阵view(biograph(DG,[],'ShowArrows',off,'ShowWeights'，‘orf));%画图T1=T1*;T1=sortrows(T1,3)；%将T1的转置按照权值生序排列T1=T1*;%转置回来
Kruscal(T1,e,m);
结果