最小生成树MATLAB代码实现

假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。

function findcycle（wN）
%isfind=findcycle（wN）
%本程序用于判断所给的边能否构成圈：有圈，返回1；否则返回0????%w：输入的边的矩阵????%N：原图的点数??
%原理：不断除去出现次数小于2的端点所在的边，最后观察是否有边留下????
len=length（w（:1））;
index=1:len;
while 1
num=length（index）;%边数??
p=zeros（1N）; %用于存储各点的出现的次数（一条边对应两个端点）??
for i=1:num %统计各点的出现次数??
p（w（index（i）2））=p（w（index（i）2））+1;p（w（index（i）3））=p（w（index（i）3））+1;
end
index_tmp=zeros（1num）; %记录除去出现次数小于2的端点所在的边的边的下标集合??
 discard=find（p<2）; %找到出现次数小于2的端点????
 count=0; %记录剩余的边数????
 for i=1:nu