数据结构（最小生成树）_最小生成树的条件

对于一个无相连通网，他的所有生成树中必有一棵边的权值总和最小的生成树，称之为最小代价生成树，简称最小生成树。
最小生成树必须满足三个条件:
1>构造的最小生成树必须包括n个顶点；
2>构造的最小生成树有且仅有n-1条边；
3>构造的最小生成树中不存在回路。

普利姆算法（Prim）
假设G=（V，E）为一无向连通网，其中，V为网中顶点的集合，E为网中边的集合。设置两个新的集合U和T，其中，U为G的最小生成树的顶点的集合，T为G的最小生成树的边的集合。普里姆算法的思想是：令集合U的初值为U={u1}（假设构造最小生成树时从顶点u1开始），集合T的初值为T={}。从所有的顶点 u∈U 和顶点 v∈V-U 的带权边中选出具有最小权值的边（u,v），将 顶点 v 加入集合 U 中，将边（u,v）加入集合 T 中。如此不断地重复直到 U=V 时，最小生成树构造完毕。此时，集合 U 中存放着最小生成树的所有顶点，集合T中存放着最小生成树的所有边。
对于邻接矩阵实现的图，Prim算法：

  public int []Prim()
        {
            int[] lowcost = new int[nodes.Length];//存储最小边的权值
            int [] closevex=new int[nodes.Length];//存储最小的边
            //初始化,0加入集合U中
            for (int i = 1; i < nodes.Length; i++)
            {
                lowcost[i] = matrix[0, i];
                closevex[i] = 0;
            }
            lowcost[0] = 0;
            closevex[0] = 0;
            for (int i = 0; i < nodes.Length; i++)
            {
                int k = 1;
                int j = 1;
                int mincost = Int32.MaxValue;
                while (j<nodes.Length)
                {
                    if (lowcost[j]<mincost&&lowcost[j]!=0)
                    {
                        mincost = matrix[i, j];
                        k = j;
                    }
                    ++j;
                }
                lowcost[k] = 0;
                for (j = 1; j < nodes.Length; j++)
                {
                    if (matrix[j,k]<lowcost[j])
                    {
                        lowcost[j] = matrix[j, k];
                        closevex[j] = k;
                    }
                }
            }
            return closevex;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

克鲁斯卡尔算法（Kruskal）
第一步：首先比较网中所有边的权值，找到最小的权值的边(D,E)，加入到生成树的边集TE中，TE={(D,E)}。
第二步：再比较图中除边(D,E)的边的权值，又找到最小权值的边(A,D)并且不会形成回路，加入到生成树的边集TE中，TE={(A,D),(D,E)}。
第三步：再比较图中除TE以外的所有边的权值，找到最小的权值的边(A,B) 并且不会形成回路，加入到生成树的边集TE中，TE={(A,D),(D,E),(A,B)}。
第四步：再比较图中除TE以外的所有边的权值，找到最小的权值的边(E,C) 并且不会形成回路，加入到生成树的边集TE中，TE={(A,D),(D,E),(A,B),(E,C)}。此时，边集TE中已经有n-1条边，所以求图6.15(a)的无向连通网的最小生成树的过程已经完成，如图6.16所示。这个结果与用普里姆算法得到的结果相同。