根据Prim算法求出图的最小生成树(给出生成过程).

Question

已知图G的邻接矩阵A=

Answer 1

解：Floyd算法的Matlab程序如下：
clear;clc;
n=5; a=zeros(n);
a(1,2)=1;a(1,3)=12;a(1,4)=6;a(1,5)=10;
a(2,3)=8;a(2,4)=9;
a(3,5)=2;
a(4,5)=4;
a=a+a';M=max(max(a))*n^2; %M为充分大的正实数
a=a+((a==0)-eye(n))*M;
path=zeros(n);
for k=1:n
for i=1:n
for j=1:n
ifa(i,j)>a(i,k)+a(k,j)
a(i,j)=a(i,k)+a(k,j);
path(i,j)=k;
end
end
end
end
a, path

Matlab输出结果：

a =

0 1 9 6 10
1 0 8 7 10
9 8 0 6 2
6 7 6 0 4
10 10 2 4 0

path =

0 0 2 0 0
0 0 0 1 3
2 0 0 5 0
0 1 5 0 0
0 3 0 0 0