最小生成树地两种构造方法

《最小生成树地两种构造方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实用标准离散数学大作业---最小生成树姓名：陈强学号：13020510084辅导老师：李阳阳文案大全实用标准一、最小生成树的概念：给定一个连通图，要求构造具有最小代价的生成树时，也即使生成树各边的权值总和达到最小。把生成树各边的权值总和定义为生成树的权，那么具有最小权值的生成树就构成了连通图的最小生成树，最小生成树可简记为MST。二、构造无向连通图的最小生成树的方法：1.Prim（普里姆）算法算法:假设G(V,E)是有n个顶点的无向连通图，用T(U,TE)表示要构造的最小生成树，其中U为顶点集合，TE为边的集合。（1）初始化

2、：令V={},TE={}。从V中取一个顶点u0放入生成树的顶点集U中，作为第一个顶点，此时T=（{u0}，{}）；（2）从的边（u,v）中找一条代价最小的边，将其放入TE中，并将放入U中。（3）重复步骤（2），直至U=V为止。此时TE集合中必有n-1条边，T即为所要构造的最小生成树。特殊处理：如果两个顶点之间没有直接相连的边，权值置为一个max的数自身和自身的权值置为MAX的值代码：function[T]=Prim(i,G_dist)%Prim.m实现了普里姆的方法生成无向连通图G的最小生成树%T是返回的最小生成树%i为输入

3、的为最小生成树选定的第一个顶点%G_dist是待输入的数据，是图G边（u,v）的权值矩阵[m,n]=size(G_dist);%读入无向图的顶点数目为m=nv=i;%将选定的顶点放入中间变量v中T=zeros(3,m-1);%最小生成树有（m-1）条边。第一行存放边的起点，第二行存放边的终点，第三行存放边的权值%%%初始化最小生成树的矩阵forj=1:m-1T(1,j)=v;%将第一个顶点放入最小生成树的矩阵中ifj>=vT(2,j)=j+1;T(3,j)=G_dist(v,j+1);elseT(2,j)=j;T(3,j)=

4、G_dist(v,j);endend文案大全实用标准%%%求第k条边fork=1:(n-1)min=10000;%初始化一个最小的权值%找出最短边，并将最短变的下标记录在mid中forj=k:(n-1)ifT(3,j)

5、fd

6、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,:),m,m);%用稀疏矩

7、阵view(biograph(DG,[],'ShowArrows','off','ShowWeights','on'));%画图Prim(i,G);结果：图G：文案大全实用标准Prim生成的最小生成树：文案大全实用标准1.Kruskal(克鲁斯卡尔)算法算法：假设G(V,E)是有n个顶点的无向连通图。（1）初始化：设置最小生成树的初始状态为只有n个顶点而无任何边的非连通图T（V,{}）。（2）依次选择E中的最小代价边，若该代价边依附于T中两个不同的连通分量，则将该边加入TE中。否则，舍去此边而选择下一条代价最小的边。（3）重

8、复步骤（2）直到所有顶点都在同意连通分量上为止。这时T就是G的一棵最小生成树。代码：function[T]=Kruscal(T1,e,m)%Kruscal.m实现了克鲁斯克尔的方法生成无向连通图G的最小生成树%T是返回的最小生成树%T1是图G的边信息%e表示的是图G中的边的数目%m是图G的