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

1、离散数学大作业 最小生成树姓名：陈强学号：辅导老师：李阳阳一、最小生成树的概念：给定一个连通图， 要求构造具有最小代价的生成树时， 也即使生成树各边的权值总和达到最小。 把生成树各边的权值总和定义为生成树的权， 那么具有最小权值的生成树就构成了连通图的最小生成树，最小生成树可简记为mst。二、构造无向连通图的最小生成树的方法：1.prim （普里姆）算法算法 :假设g（v,e是有n个顶点的无向连通图，用t（u,te表示要构造的最小生成树，其中 u为顶点集合，te为边的集合。（1）初始化： 令 v= ,te= 。 从 v 中取一个顶点 u0 放入生成树的顶点集u 中， 作为第一个顶点，此时t=（

2、 u0 ， ） ；（2）从u v,v v u的边（u,v）中找一条代价最小的边（u*, v*）,将其放入te中，并*将 v 放入 u 中。（3）重复步骤（2）,直至u=v为止。此时te集合中必有n-1条边，t即为所要构造的最小生成树。特殊处理：如果两个顶点之间没有直接相连的边，权值置为一个max 的数自身和自身的权值置为 max 的值代码：function t=prim（i,g_dist）%prim.m 实现了普里姆的方法生成无向连通图 g 的最小生成树%t 是返回的最小生成树%i 为输入的为最小生成树选定的第一个顶点%g_dist 是待输入的数据，是图 g 边( u,v )的权值矩阵m,n=

3、size(g_dist);%读入无向图的顶点数目为m=nv=i;%将选定的顶点放入中间变量v 中第二行存放边的终点，t=zeros(3,m-1);%最小生成树有( m-1 ) 条边。 第一行存放边的起点，第三行存放边的权值%初始化最小生成树的矩阵for j=1:m-1t(1,j)=v;%将第一个顶点放入最小生成树的矩阵中if j=vt(2,j)=j+1;t(3,j)=g_dist(v,j+1);elset(2,j)=j;t(3,j)=g_dist(v,j);endend%求第k 条边for k=1:(n-1)min=10000;%初始化一个最小的权值%找出最短边，并将最短变的下标记录在mid

4、中for j=k:(n-1)if t(3,j)minmin=t(3,j);mid=j;endende=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 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 , sho

5、wweights , 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,100 00,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;

6、%t1 表示图 g 的边的信息，第一行是边的起始点，第二行是边的终点，第三行是边的权重，第四行表示对边的选择t=t1(1:3,:);dg=sparse(t1(1,:),t1(2,:),t1(3,:),m,m);蜘稀疏矩阵view(biograph(dg,showarrows , off , showweights , on ); %0图prim(i,g);结果:图g:q biograph viewer 10 一面 1prim生成的最小生成树:2.kruskal(克鲁斯卡尔)算法算法：假设g(v,e是有n个顶点的无向连通图。(1)初始化：设置最小生成树的初始状态为只有n个顶点而无任何边的非连通图

7、t( v, )。(2)依次选择e中的最小代价边，若该代价边依附于t中两个不同的连通分量，则将该边加入te中。否则，舍去此边而选择下一条代价最小的边。(3)重复步骤(2)直到所有顶点都在同意连通分量上为止。这时t就是g的一棵最小生成树。代码：functiont=kruscal(t1,e,m)g 的最小生成树%kruscal.m 实现了克鲁斯克尔的方法生成无向连通图%t 是返回的最小生成树%t1 是图 g 的边信息%e表示的是图g中的边的数目%m是图g的顶点数目%初始化存放顶点连通信息的矩阵gggg=zeros(1,m);for i=1:mgg(i)=i;end%j=0;%直到选够(m-1 )条边

8、即可结束程序%while j=m-1break ;endendfor i=1:eif t1(4,i)=2 | t1(4,i)=0t1(:,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,showarrows , 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 , showwei