最小生成树问题—Prim算法与Kruskal算法实现（MATLAB语言实现）
首先引入概念：
何为树：连通且不含圈的图称为树。
图T=(V,E),|V|=n,|E|=m,下列关于树的说法等价： T是一个树。 T无圈，且m=n-1。 T连通，且m=n-1。 T无圈，但每加一新边记得到唯一一个圈。 T连通，但任舍去一边就不连通。 T中任意两点，有唯一道路相连。
何为生成树：若图G=(V,E)的生成子图是一棵树，则称该树为图G的生成树，也称支撑树，简称为图G的数。图G中属于生成树的边称为数枝（Branch）。
何为最小生成树：连通图G=(V,E),每条边上有非负权L(e)。一棵树上所有树枝权的总和，称为这个生成树的权。具有最小权的生成树称为最小生成树，也就是说最小支撑树，简称最小树。
Prim算法：
给定连通赋权图G=(V,E,W)，其中W为邻接矩阵，设两个集合P和Q，其中P用于存放G的最小生成树中的节点，集合Q存放G的最小G的最小生成树中的边。另集合P的初值为P={v1}(假设构造最小生成树时从v1出发)，集合Q的初值为P={空集}。
（1）P = {v1},Q = {空集}；
（2）while P ~= Q
找到最小边pv,其中p∈P,v∈V-P;
P = P + {v};
Q = Q + {pv};
end
Kruskal算法
（1）选e1∈E(G)，使得w(e1) = min（选e1的权值最小）。
（2）e1,e2,…,ei已选好，则从E(G)-{e1,e2,…,ei}中选取ei+1,使得G[{e1,e2,…,ei,ei+1}]中无圈，且，w(ei+1) = min。
（3）直到选得en-1为止。
预输入：
1 A = zeros(9);
2 A(1,2:9) = [2 1 3 4 4 2 5 4];
3 A(2,[3, 9]) = [4 1];
4 A(3, 4) = 1;
5 A(4, 5) = 1;
6 A(5, 6) = 5;
7 A(6, 7) = 2;
8 A(7, 8) = 3;
9 A(8, 9) = 5;
Prim算法实现：
1 A = A+A';
2 A(A==0) = Inf;
3 P = zeros(1, 9);
4 P(1,1) = 1;
5 V = 1:9;
6 V_P = V - P;
7 link = zeros(8,2);
8 k=1;
9 while k> link
link =
1 3
3 4
4 5
1 2
2 9
1 7
7 6
7 8
Kruskal算法实现：
1 A = sparse(A');
2 A(A==0) = Inf; 3 B = sparse(9, 9);
4 link = graphallshortestpaths(B, 'directed', false);
5 while sum(sum(link)) == Inf%如果不连通，则和无穷大
6 ind = find(A==min(min(A)));
7 [x, y] = ind2sub(size(A), ind);%寻找最短边
8 for i=1:length(x)
9 if link(x(i), y(i))==Inf%判断是否连通，关键！！
10 B(x(i), y(i)) = A(x(i), y(i));
11 A(x(i), y(i))=Inf;%取差集
12 end
13 end
14 link = graphallshortestpaths(B, 'directed', false);
15 end
输出：
B =
(2,1) 2
(3,1) 1
(7,1) 2
(9,2) 1
(4,3) 1
(5,4) 1
(7,6) 2
(8,7) 3
