最小生成树matlab实现.docx

《最小生成树matlab实现.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、primclearall;closeall;Graph1;%调用Graph1M文件，产生图1的邻接矩阵%Graph2;%调用Graph2M文件，产生图2的邻接矩阵len=length(graph_adjacent);%求图中有多少个顶点k=sprintf('pleaseinputthepointwhereyouwanttostart,dorememberitmustbebetween1and%d',len);start_point=input(k);%输入最小生成树产生起点while((start_point<=0)

2、(start_point>le

3、n))%如果输入的结点位置不合法即：小于等于零，或大于结点数，则重新输入disp('badpositon,pleaseinputagain!');start_point=input(k);end;%************************************下面完成prim算法****************************%相关变量初始设置tree=zeros(len-1,2);%用于保存选入最小生成树的边lowcost=zeros(1,len);%用来保存集合V-U与集合U中顶点的最短边权值，lowcost[v]=0表示顶点

4、v已经%加入最小生成树中adjvex=zeros(1,len);%用来保存依附于该边在集合U中的节点，U集合为生成最小生成树的辅助集合，%首先U={start_point},之后依次确定为把最小生成树的一边的另一节点加入U%依次下去，直到图的全部顶点都在U中能找到lowcost=graph_adjacent(start_point,:);%lowcost(i)的值为节点i与start_point的权值；adjvex=start_point.*ones(1,len);%adjvex中所有元素的值都为初始节点%以下循n-1次，用于找出最小生成树的len

5、-1条边fori=1:len-1k=lowcost>0;%k为一逻辑数组，它和lowcost同维，对于每一个位置i1lowcost(i)>0则k(i)=1%否则k(i)=0;稍候将用这个数组进行辅助寻址cost_min=min(lowcost(k));%找出lowcost中除0外的最小值index=find(lowcost==cost_min);%找出此最小值在lowcost中的下标，即找到相应的节点index=index(1);%因为最小值的下标可能不止一个，这里取第一个下标进行处理lowcost(index)=0;%表明该节点已经加入了最小生成

6、树中tree(i,:)=[adjvex(index),index];%对lowcost和adjvex进行更新forj=1:leniflowcost(j)>graph_adjacent(j,index);lowcost(j)=graph_adjacent(j,index);adjvex(j)=index;endendend;%*************************结果显示模块************************************s=0;forii=1:len-1k=sprintf('最小生成树第%d条边：（%d,%d），

7、权值为%d',ii,tree(ii,1),tree(ii,2),graph_adjacent(tree(ii,1),tree(ii,2)));%格式化字符串%disp(k);%显示%disp('');%空一行s=s+graph_adjacent(tree(ii,1),tree(ii,2));%求最小生成树的代价end%显示最小生成树的代价disp('最小生成树的总代价为：')disp(s);kruskalclearall;closeall;Graph11;%调用以邻接矩阵储存的图所在的M文件%Graph22;len=length(graph_adj

8、acent);%计算图中的顶点数temp=graph_adjacent;%将原图内容拷贝到temp中，以防对原图做改动superedge=zeros(len-1,2);%用于保存生成最小生成树的边i=1;%指向superedge的下标forj=1:lentag(j)=j;%关联标志初始化，将每个顶点的关联标志设为其本身end;%以下的循环完成kruskal算法while(superedge(len-1,1)==0)[Y,I]=sort(temp);%将temp的每列按从小到大排序，数组Y保存temp排序后的结果，I中保存相应结果对应的在temp中的

9、下标cost_min=min(Y(1,:));%找出权值最小的边index=find(Y(1,:)==cost_min);