老物了，网上的例子多的数不过来。不过我还是有必要练习一下的。

之所以看这个算法是因为最近在看颜色聚合向量时，有的论文用到了最小生成树，因此我就拿来熟悉一下。

Kruskal算法类似于连通分支算法，感觉和过去实现过的连通区域标记算法非常像。

步骤：

1.对于一个图，将图的每条边提取出来从小到大进行排序。

2.将已排序的边依次加入到新图中，如果新图中出现了环，那么就舍弃这条边。

3.不断重复第二步。

下面两个图就是kruskal算法前后的样子。

代码如下：

main.m

clear all;close all;clc;%算法导论P349的列子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;    %边的数量for i=1:m    for j=i:n        if G(i,j)~=0            E=[E;G(i,j) i j];   %提取边，三元组存储            k=k+1;        end    endendfor 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    endendA=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;    endend

huan.m

function re=huan(A)    [m n]=size(A);    while 1        pre_A=A;        for i=1:m            du=0;       %第m个元素的度            for j=1:n                if A(i,j)~=0                    du=du+1;                end            end            if du==1            %元素的度为1时删除这个元素，其相邻元素度减一               A(i,:)=0;               A(:,i)=0;            end        end        if pre_A==A     %图中没有度为1的元素则退出           break;         end    end        if sum(A(:))==0        re=0;    else        re=1;    endend