数据结构基础温故5.图(中):最小生成树算法

图的“多对多”特性使得图在结构设计和算法实现上较为困难,这时就需要根据具体应用将图转换为不同的树来简化问题的求解。

一、生成树与最小生成树

1.1 生成树

  对于一个无向图,含有连通图全部顶点的一个极小连通子图成为生成树(Spanning Tree)。其本质就是从连通图任一顶点出发进行遍历操作所经过的边,再加上所有顶点构成的子图。

  采用深度优先遍历获得的生成树称为深度优先生成树(DFS生成树),采用广度优先遍历获得的生成树称为广度优先生成树(BFS生成树)。如下图所示,无向图的DFS生成树和BFS生成树分别如图的中间和右边所示。

数据结构基础温故5.图(中):最小生成树算法

1.2 最小生成树

  如果连通图是一个带权的网络,称该网络的所有生成树中权值综合最小的生成树最小生成树(Minimum Spanning Tree,MST),简称MST生成树。

数据结构基础温故5.图(中):最小生成树算法

  求网络的最小生成树的重要意义就在于:假如要在n个城市之间铺设光缆,由于地理环境的不同,各个城市之间铺设光缆的费用也不同。一方面要使得这n个城市可以直接或间接通信,另一方面要考虑铺设光缆的费用最低。解决这个问题的方法就是在n个顶点(城市)和不同权值的边(这里指铺设光缆的费用)所构成的无向连通图中找出最小生成树。

二、Prim算法

2.1 算法思想

  假设N=(V,{E})是连通网,TE是N上最小生成树中边的集合。算法从U={u0}(u0∈V),TE={}开始。重复执行下述操作:在所有u∈U,v∈V-U的边(u,v)∈E中找一条代价最小的边(u0,v0)并入集合TE,同时v并入U,直至U=V为止。此时TE中必有n-1条边,则T=(V,{TE})为N的最小生成树。

数据结构基础温故5.图(中):最小生成树算法

2.2 算法实现

  下面实现的Prim算法主要基于邻接矩阵来构建:

        #region Test03:最小生成树算法之Prim算法测试:基于邻接矩阵
        static void PrimTest()
        {
            int[,] cost = new int[6, 6];
            // 模拟图的邻接矩阵初始化
            cost[0, 1] = cost[1, 0] = 6;
            cost[0, 2] = cost[2, 0] = 6;
            cost[0, 3] = cost[3, 0] = 1;
            cost[1, 3] = cost[3, 1] = 5;
            cost[2, 3] = cost[3, 2] = 5;
            cost[1, 4] = cost[4, 1] = 3;
            cost[3, 4] = cost[4, 3] = 6;
            cost[3, 5] = cost[5, 3] = 4;
            cost[4, 5] = cost[5, 4] = 6;
            cost[2, 5] = cost[5, 2] = 2;
            // Prim算法构造最小生成树:从顶点0开始
            Console.WriteLine("Prim算法构造最小生成树:(从顶点0开始)");
            double sum = 0;
            Prim(cost, 0, ref sum);
            Console.WriteLine("最小生成树权值和为:{0}", sum);
        }

        static void Prim(int[,] V, int vertex, ref double sum)
        {
            int length = V.GetLength(1);  // 获取元素个数
            int[] lowcost = new int[length]; // 待选边的权值集合V
            int[] U = new int[length]; // 最终生成树值集合U

            for (int i = 0; i < length; i++)
            {
                lowcost[i] = V[vertex, i]; // 将邻接矩阵起始点矩阵中所在行的值加入V
                U[i] = vertex; // U集合中的值全为起始顶点
            }

            lowcost[vertex] = -1; // 起始节点标记为已使用:-1代表已使用,后续不再判断

            for (int i = 1; i < length; i++)
            {
                int k = 0;  // k标识V集合中最小值索引
                int min = int.MaxValue; // 辅助变量:记录最小权值
                // 下面for循环中寻找V集合中权值最小的与顶点i邻接的顶点j
                for (int j = 0; j < length; j++)
                {
                    if (lowcost[j] > 0 && lowcost[j] < min) // 寻找范围不包括0、-1以及无穷大值
                    {
                        min = lowcost[j];
                        k = j; // k记录最小权值索引
                    }
                }
                // 找到了并进行打印输出
                Console.WriteLine("找到边({0},{1})权为:{2}", U[k], k, min);
                lowcost[k] = -1;  // 标志为已使用
                sum += min; // 累加权值

                for (int j = 0; j < length; j++)
                {
                    // 如果集合U中有多个顶点与集合V中某一顶点存在边
                    // 则选取最小权值边加入lowcost集合中
                    if (V[k, j] != 0 && (lowcost[j] == 0  V[k, j] < lowcost[j]))
                    {
                        lowcost[j] = V[k, j]; // 更新集合lowcost
                        U[j] = k; // 更新集合U
                    }
                }
            }
        }
        #endregion

  运行结果如下图所示,最小生成树的权值和为15:

数据结构基础温故5.图(中):最小生成树算法

Summary:Prim算法主要是对图的顶点进行操作,它适用于稠密图。

三、Kruskal算法

3.1 算法思想

  Kruskal算法是一种按权值的递增顺序来选择合适的边来构造最小生成树的方法。假设N=(V,{E})是连通网,则令最小生成树的初始状态为只有n个顶点而无边的非连通图T={V,{}},图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T中,否则舍去此边而选择下一条代价最小的边。依次类推,直至T中所有顶点都在同一连通分量上为止。

数据结构基础温故5.图(中):最小生成树算法

  下面是一个Kruskal算法的演示:

数据结构基础温故5.图(中):最小生成树算法

3.2 算法实现

  (1)存放边信息的结构体:记录边的起点、终点以及权值

        struct Edge : IComparable
        {
            public int Begin;  // 边的起点
            public int End;    // 边的终点
            public int Weight; // 边的权值

            public Edge(int begin, int end, int weight)
            {
                this.Begin = begin;
                this.End = end;
                this.Weight = weight;
            }

            public int CompareTo(object obj)
            {
                Edge edge = (Edge)obj;
                return this.Weight.CompareTo(edge.Weight);
            }
        }

  (2)创建按权值排序的边的集合

        static List<Edge> BuildEdgeList(int[,] cost)
        {
            int length = cost.GetLength(1);
            List<Edge> edgeList = new List<Edge>(); // 边集合
            for (int i = 0; i < length - 1; i++)
            {
                for (int j = i + 1; j < length; j++)
                {
                    if (cost[i, j] > 0)
                    {
                        if (i < j) // 将序号较小的顶点放在前面
                        {
                            Edge newEdge = new Edge(i, j, cost[i, j]);
                            edgeList.Add(newEdge);
                        }
                        else
                        {
                            Edge newEdge = new Edge(j, i, cost[i, j]);
                            edgeList.Add(newEdge);
                        }
                    }
                }
            }
            edgeList.Sort(); // 让各边按权值从小到大排序
            return edgeList;
        }

  (3)Kruskal核心代码:Kruskal的实现过程是将森林变成树的过程,可以给森林中的每一棵树配置一个唯一的分组号,当两棵树合并为一棵树后,使它们具有相同的分组号。因此,在树合并时,如果两棵树具有相同的分组号,表明合并后的树存在回路

        static void Kruskal(int[,] cost, int vertex, ref double sum)
        {
            int length = cost.GetLength(1);
            List<Edge> edgeList = BuildEdgeList(cost); // 获取边的有序集合
            int[] groups = new int[length]; // 存放分组号的辅助数组

            for (int i = 0; i < length; i++)
            {
                // 辅助数组的初始化:每个顶点配置一个唯一的分组号
                groups[i] = i;
            }

            for (int k = 1, j = 0; k < length; j++)
            {
                int begin = edgeList[j].Begin; // 边的起始顶点
                int end = edgeList[j].End; // 边的结束顶点
                int groupBegin = groups[begin]; // 起始顶点所属分组号
                int groupEnd = groups[end]; // 结束顶点所属分组号
                // 判断是否存在回路:通过分组号来判断->不是一个分组即不存在回路
                if (groupBegin != groupEnd)
                {
                    // 打印最小生成树边的信息
                    Console.WriteLine("找到边({0},{1})权值为:{2}", begin, end, edgeList[j].Weight);
                    sum += edgeList[j].Weight; // 权值之和累加
                    k++;
                    for (int i = 0; i < length; i++)
                    {
                        // 两棵树合并为一课后,将树的所有顶点所属分组号设为一致
                        if (groups[i] == groupEnd)
                        {
                            groups[i] = groupBegin;
                        }
                    }
                }
            }
        }

数据结构基础温故5.图(中):最小生成树算法

Summary:Kruskal算法主要针对图的边进行操作,因此它适用于稀疏图。

参考资料

(1)程杰,《大话数据结构》

(2)陈广,《数据结构(C#语言描述)》

(3)段恩泽,《数据结构(C#语言版)》

 

作者:周旭龙

出处:http://edisonchou.cnblogs.com

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。

更多相关文章
  • 前言: 看了别人的一些文章,为了用起来方便,总结了如下规律,其中*****1A3代表虚拟地址的后3位,估计大家和我的应该一样 首先要做的就是用Lordpe查看OEP,用OD载入后计算出基址大小. 1.dump文件 在如下位置: *****1A3 0F851EFFFFFF JNZ 00C700C7&l ...
  • Change the ball Time Limit: 2/1 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 552    Accepted Submission(s): 193 P ...
  • 目录结构如下: 行转列 列转行 [一].行转列   1.1.初始测试数据   表结构:TEST_TB_GRADE   Sql代码  create table TEST_TB_GRADE  (    ID        NUMBER(10) not null,    USER_NAME VARCHAR ...
  • 要实现精灵的翻转,非常简单,先看实际效果点这里. 代码只有区区几行: var sp = this.getWindow().find("ui-status2-general"); var ac1 = {scaleXEnd:0}; var ac2 = {scaleXEnd:1}; s ...
  • 图是由顶点和边连接而成,如果边是没有方向的是就是之前文章中说的无向图,关于无向图可以参考本人之前的文章,如果边是有方向的,则称之为有向图.从顶点A→B,我们可以理解为A到B可达,有向图和无向图一样通过邻接表保存每一条边,由于边是有方向的,因此在添加边的过程中只需要添加一条边即可.关于可达性一个节点数 ...
  • 3个消息分别是:WM_SIZE.WM_SIZING.WM_GETMINMAXINFO:分别对应相应的处理函数:OnSize.OnSizing.OnGetMinMaxInfo. 当窗口大小发生变化时,响应的顺序依次是:WM_GETMINMAXINFO-->WM_SIZING-->WM_SI ...
一周排行
  • 一直对回调机制不明白?回调?什么鬼?干嘛使的?有毛用? 其实顾名思义,回调就是“回过头来调用对方”.即:当我联系你时,你又回过头来联系我.对,没错,就是好莱坞法则——“Don't call me; I'll call ...
  • 含义 ENCTYPE="multipart/form-data" 说明:  通过 http 协议上传文件 rfc1867协议概述,jsp 应用举例,客户端发送内容构造    1.概述在最初的 ht ...
  • 要注意的问题:1.android4.0后,代码不能卸载ui. 2.想想,就是通过url取网络图片嘛,我直接给他一个url好了嘛,然后它就给我取出来. 这边分享一个比较简洁的实现方式: private class Do ...
  • 信息.状态和控制的关系(头脑风暴) 刘建文略译(http://blog.csdn.net/keminlau ) KEY:信息处理 计算理论 形式语言 编程语言   信息.状态和控制的关系 计算的两本质元素是,第一,状 ...
  • 不用多想 暴力撸就行 枚举每个点 向四周延伸的两条最远距离 最多能转一次90度的弯 #include #include #include using namespace std; int dir[8][2]={0,1 ...
  • (一)虚拟化技术概述 虚拟化技术可针对具体应用目的创建特定目的的虚拟环境,安全.效率高,快照.克隆.备份.迁移等方便.系统虚拟化是将一台物理计算机虚拟成一台或多台虚拟计算机系统,每个都有自己的虚拟硬件,其上的操作系统 ...
  • 1.两种方式给Wordpress首先,你可以去wordpress最新的官方网站看看wordpress多少下载.例wordpress 3.9.1下载地址:http://cn.wordpress.org/wordpres ...
  • 上海公积金管理中心一览表  名称 地址 电话 邮编 上海市公积金管理中心  金陵东路569号 63843088 200021 浦东新区公积金管理中心  乳山路235弄32号-38号 58306993,68671700 ...
  • (教材P394习题9)分别定义Teacher(教师)类和Cadre(干部)类,采用多重继承方式由这两个类派生出新类Teacher_Cadre(教师兼干部).要求: (1)在两个基类中都包含姓名.年龄.性别.地址.电话 ...
  • 近期,微博中正在上演现实版的"土豪就是任性".热门话题#帮土豪求婚#求爱问答在微博上迅速蹿红,"花100元如何把家装满?"女主角调皮发问.问题一出便引发全民热议,众网友脑洞大开 ...