最小生成树matlab实现.docxVIP

prim clear all; close all; Graph1;%调用 Graph1M 文件，产生图 1 的邻接矩阵%Graph2;%调用 Graph2M 文件，产生图 2 的邻接矩阵 len=length(graph_adjacent);%求图中有多少个顶点 k=sprintf(please input the point where you want to start ,do rem ember it must be between 1 and %d ,len); start_point=input(k);%输入最小生成树产生起点 while((start_point=0)|(start_pointlen))%如果输入的结点位置不合法即： 小于等于零，或大于结点数，则重新输入 disp(bad positon,please input again!); start_point=input(k); end; %************************************下面完成 prim 算法************** ************** %相关变量初始设置 tree=zeros(len-1,2);%用于保存选入最小生成树的边 lowcost=zeros(1,len);%用来保存集合 V-U 与集合 U 中顶点的最短边权值，lowcost [v]=0 表示顶点 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-1 条边 for i=1:len-1 k=lowcost0;%k 为一逻辑数组，它和 lowcost 同维，对于每一个位置 i1lowcos t(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;%表明该节点已经加入了最小生成树中 tree(i,:)=[adjvex(index),index]; %对 lowcost 和 adjvex 进行更新 for j=1:len if lowcost(j)graph_adjacent(j,index); lowcost(j)=graph_adjacent(j,index); adjvex(j)=index; end end end; %*************************结果显示模块***************************** ******* s=0; for ii=1:len-1 k=sprintf(最小生成树第%d 条边：（%d,%d），权值为%d,ii,tree(ii,1),tr ee(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); kruskal clear all; close all; Graph11;%调用以邻接矩阵储存的图所在的 M 文件 %Graph22; len=length(graph_adjacent);%计算图中的顶点数 temp=graph_adjacent;%将原图内容拷贝到 temp 中，以防对原图做改动superedge=zeros(len-1,2);%用于保存生成最小生成树的边i=1;%指向 superedge 的下标 for j=1:len tag(j)=j;%关联标志初始化，将每个顶点的关联标志设为其本身 end; %以下的循环完成 kruskal 算法 while(super