clear?all;
%===============================================
%導(dǎo)入數(shù)據(jù)集并初始化中間變量
%?pointdata?=?load（‘mydataset.txt‘）‘;
pointdata=load（‘rings1.txt‘）;
pointdata（:length（pointdata（1:）））=[];
distarr=pdist（pointdata?‘euclidean‘）;
save=squareform（distarr）;%得到圖的距離（權(quán)值）矩陣
len=length（save（:1））;
edge=[];%記錄連接的邊

%cc存儲(chǔ)了連通分支，初始狀態(tài)設(shè)每個(gè)點(diǎn)為連通分支
cc=cell（1len）;
for?i=1:len
????cc{i}=i;
end

%=================================================
%生成最小生成樹，并按照閾值分割最小生成樹，得到幾個(gè)連通分支
threshold=0.6;%設(shè)置閾值
ccSize=size（cc）;
while?ccSize（2）>1
????%得到最小的權(quán)值的邊
????minpx=Inf;
????for?i=1:1:len
????????for?j=i+1:1:len
????????????if?save（ij）????????????????dot=[ij];
????????????????minpx=save（ij）;
????????????end
????????end
????end
????%判斷閾值
????if?minpx>threshold
????????break;
????end
????%======================================
????%核心算法步驟：
????%判斷上面得到的邊上的兩點(diǎn)是否在不同的連通分支上；
????%若在不同的連通分支，則將這兩個(gè)連通分支合并為一個(gè)連通分支，即把邊加入edge矩陣中；
????%若在同一連通分支則退出循環(huán)，繼續(xù)下一步，即忽略這條邊
????%======================================
????ccSize=size（cc）;
????flag1=0;
????flag2=0;
????for?i=1:ccSize（2）
????????if?ismember（dot（1）cc{i}）?
????????????flag1=1;?
????????????m=i;
????????end
????????if?ismember（dot（2）cc{i}）?
????????????flag2=1;
????????????n=i;
????????end
????????if?flag1&&flag2
????????????a=min（mn）;
????????????b=max（mn）;
????????????%判斷是否在同一連通分支
????????????if?m==n
????????????????break;
????????????else
????????????????%合并連通分支，并記錄邊的過程
????????????????cc{ccSize（2）+1}=[cc{m}cc{n}];
????????????????cc（:a）=[];
????????????????cc（:b-1）=[];
????????????????edge=[edge;dot（1）dot（2）];
????????????end
????????????break;
????????end
????end
????%使讀過的最小的邊失效，不在被讀取
????save（dot（1）dot（2））=Inf;
????save（dot（2）dot（1））=Inf;
end
%==================================================
%作最小生成樹的圖
for?i=1:length（edge（:1））
???plot（[pointdata（edge（i1）1）pointdata（edge（i2）1）][pointdata（edge（i1）2）pointdata（edge（i2）2）]‘-go‘）;
???hold?on;
end

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----
?????文件????????2227??2017-12-21?22:43??Kruskul.m
?????文件??????????40??2017-12-11?14:36??myTestDataset.txt
?????文件????????7525??2014-06-16?15:44??rings.txt
?????文件????????7525??2017-12-05?16:31??ringsDisorder.txt