|
时间久远，文档又找不到了，我已经忘记到底特色点具体在什么地方，归结为一点，就是充分利用了MATLAB语言的批量计算特性。直接贴代码吧，有需要的人自然能看出名堂来。
  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 remember it must be between 1 and %d ',len); start_point=input(k);%输入最小生成树产生起点 while((start_point<=0)|(start_point>len))%如果输入的结点位置不合法即：小于等于零，或大于结点数，则重新输入 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=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;%表明该节点已经加入了最小生成树中 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),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);
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(superedge(len-1,1)==0) [Y,I]=sort(temp);%将temp的每列按从小到大排序，数组Y保存temp 排序后的结果，I中保存相应结果对应的在temp中的下标 cost_min=min(Y(1,:));%找出权值最小的边 index=find(Y(1,:)==cost_min);%找出权值最小的边对应的顶点 index=index(1);%一条边对应两个节点，且不同的边的权值可能一样，这里为了方便处理人为规定了顺序，取标号最小的顶点进行处理 anotherpoint=I(1,index);%找到该边对应的另一个顶点 %将该边对应的权值修改为最大，防止该边在下次循环中再次被选为最优边 temp(index,anotherpoint)=100; temp(anotherpoint,index)=100; if(tag(anotherpoint)~=tag(index))%当两个点不属于一个连通集时，这两个点之间的边为最小生成树的边 superedge(i,:)=[index,anotherpoint];%将其加入最小生成树的边集中 i=i+1;%下标加1 %下面的语句的作用是将两个连通分支变成一个连通分支，即tag值一样 for j=1:len%以index的tag值为标准 if((tag(j)==tag(anotherpoint))&(j~=anotherpoint))%遍搜tag数组，先将和anotherpoint tag值一样的点的tag值变为index的tag值 tag(j)=tag(index); end end tag(anotherpoint)=tag(index);%将anotherpoint的tag值变为index的tag值 end end %*************************结果显示模块************************************ s=0; for ii=1:len-1 k=sprintf('最小生成树第%d条边：（%d,%d），权值为%d',ii,superedge(ii,1),superedge(ii,2),graph_adjacent(superedge(ii,1),superedge(ii,2)));%格式化字符串 %disp(k);%显示 %disp(' ');%空一行 s=s+graph_adjacent(superedge(ii,1),superedge(ii,2)); %求最小生成树的代价 end %显示最小生成树的代价 disp('最小生成树的总代价为：') disp(s);
源码下载：http://download.csdn.net/source/1030348 找到了以前写的实验报告，也传上去吧，这是一年半以前写的，当时还是个上大学的小P孩子，觉得代码是最有用的东东，所以很多东西都只保存了代码，没有保存文档，现在转过头来意识到了文档的重要性。 文档在：http://download.csdn.net/source/1963473 |
|
|
