数据结构（最小生成树）

傷城~ 2022-06-05 04:28 183阅读 0赞

对于一个无相连通网，他的所有生成树中必有一棵边的权值总和最小的生成树，称之为最小代价生成树，简称最小生成树。  
最小生成树必须满足三个条件:  
1>构造的最小生成树必须包括n个顶点；  
2>构造的最小生成树有且仅有n-1条边；  
3>构造的最小生成树中不存在回路。  
![这里写图片描述][SouthEast]  
**普利姆算法（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;
            }

**克鲁斯卡尔算法（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所示。这个结果与用普里姆算法得到的结果相同。

[SouthEast]: /images/20220605/a0432d0e37d244779289101d18066e27.png