Page 110 - 数学建模算法与应用

Mathematical Modeling Algorithms and Applications
数学建模算法与应用

1. 最小生成树
function [w，E] = MinTree(A)
% 遍圈法求最小生成树

% A 为图的赋权邻接矩阵
% w 记录最小树的权值之和 E 记录最小树上的边
n = size(A，1)；
T = A + inf；

w = 0；
k = 1；
s1 = []；

s2 = []；
for i = 1：n
A(i，i) = inf；
end
for i = 1：n

T(1，：) = A(1，：)；
T(：，1) = A(：，1)’；
end
while k < n

[pl，q1] = min(T)；
while q1 <= k
[pl，q1] = min(T)；
end

[p2，q2] = min(pl)；
[i，j] = find(s1 == q2 | s2 == q2)；
s1 = [s1；i]；

s2 = [s2；j]；
w = w + pl；
k = k + 1；
T(q2，：) = inf；

100