一、Kruskal算法
? ? ? ? 克魯斯卡爾算法（Kruskal）是一種使用貪婪方法的最小生成樹算法。 該算法初始將圖視為森林，圖中的每一個頂點視為一棵單獨的樹。 一棵樹只與它的鄰接頂點中權(quán)值最小且不違反最小生成樹屬性（不構(gòu)成環(huán)）的樹之間建立連邊。
二、具體效果
?文章來源：http://www.zghlxwxcb.cn/news/detail-535815.html
最小生成樹法生成網(wǎng)絡(luò)文章來源地址http://www.zghlxwxcb.cn/news/detail-535815.html
三、代碼
clc
clear
close all
P=[20,100;3,31;83,44;93,19;77,14;85,44;18,35;84,39;18,49;37,46;9,86;46,85;68,40;9,5;45,15;23,89;5,40;44,61;72,50;46,68];
%計算距離矩陣
D=inf*ones(size(P,1),size(P,1));
for i=1:size(P,1)-1
for j=i+1:size(P,1)
D(i,j)=norm(P(i,:)-P(j,:));
end
end
plot(P(:,1),P(:,2),'.k','MarkerSize',20)
hold on
%Kruskal算法
temp=[]; %已經(jīng)選擇的節(jié)點
while size(unique(temp),1)<size(P,1)
%尋找最短的邊
[xx,yy]=find(D==min(min(D)));
ii=xx(1);
jj=yy(1);
%判斷ii和jj加進去是否成環(huán)
io=judge(P,temp,ii,jj);
if io==0
temp=[temp;ii,jj];
plot([P(ii,1),P(jj,1)],[P(ii,2),P(jj,2)],'-b')
hold on
pause(0.1)
end
D(ii,jj)=inf;
end
到了這里，關(guān)于最小生成樹matlab代碼Kruskal算法，用于二維網(wǎng)絡(luò)生成的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
