finallykruskal.m ( File view )

  • By mulangic 2016-05-09
  • View(s):0
  • Download(s):0
  • Point(s): 1
			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
...
...
(Please download the complete source code to view)
			
...
Expand> <Close

Want complete source code? Download it here

Point(s): 1

Download
0 lines left, continue to read
Sponsored links

File list

Tips: You can preview the content of files by clicking file names^_^
Name Size Date
finallykruskal.m1.98 kB14-06-08|10:51
finallyprim.m2.35 kB14-06-08|10:51
Graph1.m321.00 B09-06-08|15:26
Graph11.m333.00 B09-06-08|21:11
Graph2.m392.00 B09-06-08|16:17
Graph22.m408.00 B09-06-08|21:12
kruskalenhance.m2.12 kB14-06-08|13:08
Readme.txt83.00 B14-06-08|13:29
test.m153.00 B14-06-08|10:21
testsparse.m187.00 B14-06-08|10:44
计算机仿真final.doc586.50 kB16-09-08|18:31
code0.00 B17-11-08|22:23
prim0.00 B0|0%
...
Sponsored links

finallykruskal.m (330.27 kB)

Need 1 point
Your Point(s)

Your Point isn't enough.

Get point immediately by PayPal

More(Debit card / Credit card / PayPal Credit / Online Banking)

Submit your source codes. Get more point

LOGIN

Don't have an account? Register now
Need any help?
Mail to: support@codeforge.com

切换到中文版?

CodeForge Chinese Version
CodeForge English Version

Where are you going?

^_^"Oops ...

Sorry!This guy is mysterious, its blog hasn't been opened, try another, please!
OK

Warm tip!

CodeForge to FavoriteFavorite by Ctrl+D