算法系列15天速成——第十五天 图【下】（大结局）

一： 最小生成树

1. 概念

首先看如下图，不知道大家能总结点什么。

对于一个连通图G，如果其全部顶点和一部分边构成一个子图G1，当G1满足：

① 刚好将图中所有顶点连通。②顶点不存在回路。则称G1就是G的“生成树”。

其实一句话总结就是：生成树是将原图的全部顶点以最小的边连通的子图，这不，如下的连通图可以得到下面的两个生成树。

② 对于一个带权的连通图，当生成的树不同，各边上的权值总和也不同，如果某个生成树的权值最小，则它就是“最小生成树”。

2. 场景

实际应用中“最小生成树”还是蛮有实际价值的，教科书上都有这么一句话，若用图来表示一个交通系统，每一个顶点代表一个城市，

边代表两个城市之间的距离，当有n个城市时，可能会有n(n-1)/2条边，那么怎么选择(n-1)条边来使城市之间的总距离最小，其实它

的抽象模型就是求“最小生成树”的问题。

3. prim算法

当然如何求“最小生成树”问题，前人都已经给我们总结好了，我们只要照葫芦画瓢就是了，

第一步：我们建立集合“V,U"，将图中的所有顶点全部灌到V集合中，U集合初始为空。

第二步： 我们将V1放入U集合中并将V1顶点标记为已访问。此时：U（V1）。

第三步： 我们寻找V1的邻接点（V2,V3,V5)，权值中发现(V1,V2)之间的权值最小，此时我们将V2放入U集合中并标记V2为已访问，

此时为U（V1，V2）。

第四步： 我们找U集合中的V1和V2的邻接边，一阵痉挛后，发现（V1，V5）的权值最小，此时将V5加入到U集合并标记为已访问，此时

U的集合元素为（V1，V2，V5）。

第五步：此时我们以（V1，V2，V5）为基准向四周寻找最小权值的邻接边，发现（V5，V4）的权值最小，此时将V4加入到U集合并标记

为已访问，此时U的集合元素为（V1，V2，V5，V4）。

第六步： 跟第五步形式一样，找到了（V1，V3）的权值最小，将V3加入到U集合中并标记为已访问，最终U的元素为（V1，V2，V5，V4，V3），

最终发现顶点全部被访问，最小生成树就此诞生。

复制代码 代码如下:

#region prim算法获取最小生成树
        /// <summary>
/// prim算法获取最小生成树
/// </summary>
/// <param></param>
        public void Prim(MatrixGraph graph, out int sum)
        {
            //已访问过的标志
            int used = 0;

//非邻接顶点标志
            int noadj = -1;

//定义一个输出总权值的变量
            sum = 0;

//临时数组，用于保存邻接点的权值
            int[] weight = new int[graph.vertexNum];

//临时数组，用于保存顶点信息
            int[] tempvertex = new int[graph.vertexNum];

//取出邻接矩阵的第一行数据，也就是取出第一个顶点并将权和边信息保存于临时数据中
            for (int i = 1; i < graph.vertexNum; i++)
            {
                //保存于邻接点之间的权值
                weight[i] = graph.edges[0, i];

//等于0则说明V1与该邻接点没有边
                if (weight[i] == short.MaxValue)
                    tempvertex[i] = noadj;
                else
                    tempvertex[i] = int.Parse(graph.vertex[0]);
            }

//从集合V中取出V1节点，只需要将此节点设置为已访问过，weight为0集合
            var index = tempvertex[0] = used;
            var min = weight[0] = short.MaxValue;

//在V的邻接点中找权值最小的节点
            for (int i = 1; i < graph.vertexNum; i++)
            {
                index = i;
                min = short.MaxValue;

for (int j = 1; j < graph.vertexNum; j++)
                {
                    //用于找出当前节点的邻接点中权值最小的未访问点
                    if (weight[j] < min && tempvertex[j] != 0)
                    {
                        min = weight[j];
                        index = j;
                    }
                }
                //累加权值
                sum += min;

Console.Write("({0},{1})  ", tempvertex[index], graph.vertex[index]);

（编辑：焦作站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!