最小生成树 克鲁斯卡尔算法 kruskal

clear all; close all; clc; %课本367页图为例； G=[0 4 0 0 0 0 0 8 0; 4 0 8 0 0 0 0 11 0; 0 8 0 7 0 4 0 0 2; 0 0 7 0 9 14 0 0 0; 0 0 0 9 0 10 0 0 0; 0 0 4 14 10 0 2 0 0; 0 0 0 0 0 2 0 1 6; 8 11 0 0 0 0 1 0 7; 0 0 2 0 0 0 6 7 0]; [m n]=size(G); E=[]; k=0; %k为边的数量 for i=1:m; for j=1:n; if G(i,j)~=0 %G中相应位置不为0即为（i j）有边 E=[E;G(i,j) i j]; %E为边的信息 k=k+1;%k为边的数量 end; end end for i=k:-1:1;%排序方法 冒泡法 for j=1:i-1; if E(j,1)>E(j+1,1) tmp=E(j,:); E(j,:)=E(j+1,:); E(j+1,:)=tmp; end end end A=zeros(m,n); for i=1:k; A(E(i,2),E(i,3))=E(i,1); A(E(i,3),E(i,2))=E(i,1);%此图为无向图 if huan(A) %加入边后判断图中是否含有环 A(E(i,2),E(i,3))=0; A(E(i,3),E(i,2))=0; end end tree=zeros(m,2); for i=1:m for j=i:n leng=find(tree(:,1)>0); len=length(leng); if A(i,j)~=0 tree(len+1,1)=i; tree(len+1,2)=j; end end end s=0; for ii=1:m-1 k2=sprintf('最小生成树边：（%c,%c），权值为%d',char(tree(ii,1)+96),char(tree(ii,2)+96),G(tree(ii,1),tree(ii,2))); disp(k2);%显示 disp(' ');%空一行 s=s+G(tree(ii,1),tree(ii,2)); %求最小生成树的代价 end disp('最小生成树的总代价为：') disp(s);