《最小生成树地两种构造方法》由会员分享，可在线阅读，更多相关《最小生成树地两种构造方法（11页珍藏版）》请在金锄头文库上搜索。
1、word离散数学大作业 -最小生成树 某某：陈强 辅导教师：李阳阳一、最小生成树的概念： 给定一个连通图，要求构造具有最小代价的生成树时，也即使生成树各边的权值总和达到最小。把生成树各边的权值总和定义为生成树的权，那么具有最小权值的生成树就构成了连通图的最小生成树，最小生成树可简记为MST。二、构造无向连通图的最小生成树的方法：1. Prim普里姆算法算法: 假设G(V,E)是有n个顶点的无向连通图，用T(U,TE)表示要构造的最小生成树，其中U为顶点集合，TE为边的集合。（1） 初始化：令V= ,TE=。从V中取一个顶点u0放入生成树的顶点集U中，作为第一个顶点，此时T=u0，；（2） 从的
2、边u,v中找一条代价最小的边，将其放入TE中，并将放入U中。（3） 重复步骤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=nv=i;%将选定的顶点放入中间变量v中T=zeros(3,m-1);%最小生成树有m-1条边。第一行存放边的起点
3、，第二行存放边的终点，第三行存放边的权值%初始化最小生成树的矩阵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); endend%求第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;endend e=T(:,mid);T(:,mid)=T(:,k);T(:,k)=
4、e;%将最短的边所在的一列和第k列交换 v=T(2,k);%v中存放新找到的最短边在V-U中的顶点for j=(k+1):(n-1)%修改所存储的最小边集 d=G_dist(v,T(2,j);if dT(3,j) T(3,j)=d;T(1,j)=v;endendendDG=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
5、,10000;10000,8,10000,10000,7,11;10000,6,2,7,10000,17;10000,10000,10000,11,17,10000;%G表示图G的各边权值，自身到自身的权值和不直接相连的顶点的权值设为10000i=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,:)
6、,m,m);%用稀疏矩阵view(biograph(DG,ShowArrows,off,ShowWeights,on);%画图Prim(i,G);结果：图G：Prim生成的最小生成树：2. Kruskal(克鲁斯卡尔)算法算法： 假设G(V,E)是有n个顶点的无向连通图。1初始化：设置最小生成树的初始状态为只有n个顶点而无任何边的非连通图TV,。2依次选择E中的最小代价边，假如该代价边依附于T中两个不同的连通分量，如此将该边参加TE中。否如此，舍去此边而选择下一条代价最小的边。3重复步骤2直到所有顶点都在同意连通分量上为止。这时T就是G的一棵最小生成树。代码：function T=Krusca
7、l(T1,e,m)%T是返回的最小生成树%T1是图G的边信息%e表示的是图G中的边的数目%m是图G的顶点数目%初始化存放顶点连通信息的矩阵GGGG=zeros(1,m);for i=1:m GG(i)=i;end%j=0;%直到选够m-1条边即可完毕程序%while j=m-1break;endendfor i=1:eif T1(4,i)=2 | T1(4,i)=0 T1(:,i)=0;0;0;0;endendT1=T1(:,any(T1);T=T1(1:3,:);DG=sparse(T1(1,:),T1(2,:),T1(3,:),m,m);%用稀疏矩阵view(biograph(DG,Sho
8、wArrows,off,ShowWeights,on);%画图调用函数e=9;%图G的边的数目m=6;%图G的顶点数目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);%画图T1=T1;T1=sortrows(T1,3);%将T1的转置按照权值生序排列T1=T1;%转置回来Kruscal(T1,e,m);结果：图G：Kruscal最小生成树：文案大全
