?? kruskal.m
字號:
%
%---------------------kruskal.m---------------------
%
% Kruskal algorithm for finding minimum spanning tree
%
% Input: PV = nx3 martix. 1st and 2nd row's define the edge (2 vertices) and
% the 3rd is the edge's weight
% Output: w = Minimum spanning tree's weight
% T = Minimum spanning tree's adjacency matrix
%
% N.Cheilakos,2006
%----------------------------------------------------
%function [w,T] = kruskal(PV)
PV=[inf 3 2 4 inf inf 3;
3 inf 4 inf inf inf 6;
2 4 inf inf inf 1 inf;
4 inf inf inf 5 inf inf;
inf inf inf 5 inf 3 inf;
inf inf 1 inf 3 inf 2;
inf 6 inf inf inf 2 inf];
row = size(PV,1);
X = [];
% create graph's adjacency matrix
for i = 1 : row
X(PV(i,1),PV(i,2)) = 1;
X(PV(i,2),PV(i,1)) = 1;
end
n = size(X,1);
% Check if graph is connected
con = connected(X);
if con == 1
error('Graph is not connected');
end
% sort PV by ascending weights order. (we use bubble sort)
PV = fysalida(PV,3);
korif = zeros(1,n);
T = zeros(n);
for i = 1 : row
% control if we insert edge[i,j] in the graphic. Then the graphic has
% circle
akmi = PV(i,[1 2]);
[korif,c] = iscycle(korif,akmi);
if c == 1
PV(i,:) = [0 0 0];
end
end
% Calculate Minimum spanning tree's weight
w = sum(PV(:,3)');
% Create minimum spanning tree's adjacency matrix
for i = 1 : row
if PV(i,[1 2]) ~= [0 0]
T(PV(i,1),PV(i,2)) = 1;
T(PV(i,2),PV(i,1)) = 1;
end
end
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -