"最小生成树MATLAB"
本文档主要讲解了最小生成树（Minimum Spanning Tree）的概念和MATLAB实现方法。最小生成树是指一个连通图的生成树中权值最小的那棵树。它广泛应用于网络架设、交通规划、资源分配等领域。
一、Prim算法
Prim算法是一种常见的最小生成树算法。算法的思想是从图中的一个顶点开始，选取具有最小权值的边，直到所有顶点都被连接起来。MATLAB实现代码如下：
```matlab
clc;clear;
M=1000;
a(1,2)=50; a(1,3)=60;a(2,4)=65; a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50;
a(4,6)=30;a(4,7)=42;a(5,6)=70;
a=[a;zeros(2,7)];
a=a+a';
a(find(a==0))=M;
result=[];
p=1;
tb=2:length(a);
while length(result)~=length(a)-1
temp=a(p,tb);
temp=temp(:);
d=min(temp);
[jb,kb]=find(a(p,tb)==d);
j=p(jb(1));
k=tb(kb(1));
result=[result,[j;k;d]];
p=[p,k];
tb(find(tb==k))=[];
end
```
二、Kruskal算法
Kruskal算法是另一种常见的最小生成树算法。算法的思想是从图中的所有边中选取最小权值的边，并且不构成圈，直到选够n-1条边为止。MATLAB实现代码如下：
```matlab
clc;clear;
M=1000;
a(1,2)=50; a(1,3)=60;a(2,4)=65; a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50;
a(4,6)=30;a(4,7)=42;a(5,6)=70;
[i,j]=find((a~=0)&(a~=M));
b=a(find((a~=0)&(a~=M)));
data=[i';j';b'];
index=data(1:2,:);
loop=max(size(a))-1;
result=[];
while length(result)<loop
temp=min(data(3,:));
flag=find(data(3,:)==temp);
flag=flag(1);
v1=data(1,flag);
v2=data(2,flag);
if index(1,flag)~=index(2,flag)
result=[result,data(:,flag)];
end
if v1>v2
index(find(index==v1))=v2;
else
index(find(index==v2))=v1;
end
data(:,flag)=[];
index(:,flag)=[];
end
```
三、中国邮递员问题
中国邮递员问题是指在一个有奇点的连通图中，增加一些重复边，使得新的连通图不含有奇点，并且增加的重复边总权最小。该问题可以使用Fleury算法解决。
四、Fleury算法
Fleury算法是解决中国邮递员问题的一种算法。算法的思想是从一个Euler图中找出Euler环游。
MATLAB实现代码如下：
```matlab
function [T,c]=fleuf1(d)
% 注:必须保证就是Euler环游,否则输出T=0,c=0
n=length(d);
b=d;
b(b==inf)=0;
b(b~=0)=1;
m=0;
a=sum(b);
eds=sum(a)/2;
ed=zeros(2,eds);
vexs=zeros(1,eds+1);
matr=b;
for i=1:n
if mod(a(i),2)==1
m=m+1;
end
end
if m~=0
% todo
end
end
```
本文档讲解了最小生成树的概念和MATLAB实现方法，并且讨论了中国邮递员问题和Fleury算法。
