前言在数据结构和算法的图论中，（生成的）最小生成树算法是一种贴近生活的常用算法。但是很多人可能对这个概念不是很清楚。什么是最小生成树？n个节点连通图的生成树是原图的最小连通子图，包含原图中所有的n个节点。并具有最少的边来保持图的连接。最小生成树可以通过克鲁斯卡尔（Kruskal）算法或普里姆（Prime）算法得到。通俗地说，最小生成树包含了原始图的所有节点，并且只使用了最少的边和最小的权重距离。因为n个节点至少需要n-1条边连接，距离远近需要一定的策略来选择合适的边。在学习最小生成树实现算法之前，首先要定义最小生成树的结构和意义。让我们首先希望您根据一些图片更好地理解。一个故事在城市道路规划中，是一个很科学的研究（只是假设学习不必认真）。道路时代，城市连通的主要矛盾是时间慢，而与交通时间相比，成本是次要矛盾。所以在高速公路时代，我们尽量让城市直接相连，缩短城市之间的联系时间，稍微考虑一下修路成本！随着科学技术的发展，铁路发达，信息传递比公路运输快很多，所以事件的主要矛盾是从运输时间转化为成本，所以有时候我们会注意所有连接的距离（最短）点，它使用最小生成树算法。城市道路铺设可能经历以下几个阶段。最初，每个城市都没有公路（铁路）。政府打算在各个城市铺设公路（铁路）。每个城市都想成为交通枢纽，快速到达其他城市，但每个城市都有这个想法。如果实现了，成本就太高了。并造成巨大的浪费。最终国家选择联通一些大城市，部分城市只能稍微绕路，而绕路时间太长、人口多的国家考虑新建公路（铁路），适当提高效率。但由于上述铁路规划人口众多，可能无法满足“有铁路”的需求。人们一直在追求速度、距离、直接访问等条件……但你可以想象这样一个场景：有些东西造假成本非常非常高，使用效率非常高。我假设是铺金镶钻的电缆，所以每个城市只要不让自己掉队，能连通就够了（没人敢跳）。需要从圆图中选择成本最小、成本最小的路线，一方面成本最小（总距离最小，最省金），另一方面连接所有城市。不过根据上图，我们可以得到下面的最小生成树，不过最后生成这个最小生成树就是下面要讲的内容了。而同样，部分地区有岛屿与桥梁相连，或多或少会用到成本高昂的海底通道。上面的Kruskal算法介绍了什么是最小生成树，现在我们要掌握和理解最小生成树是怎么形成的。给定一个图，使用规则生成最小生成树。在实现最小生成树方面，有prim和kruskal算法。这两种算法的策略不同，但时间复杂度是一样的。Kruskal算法与前面提到的联合搜索有很大关系。它的主要思想是：首先构造一个只包含n个顶点和一个空边集的子图，并将子图中的每个顶点都看成一棵树之后，从网络的边集E中选出一条权值最小的边。如果这条边的两个顶点属于不同的树，则将其加入到子图中，即把两棵树合为一棵树，反之，如果这条边的两个顶点已经落在同一棵树上，则不可取,但应采用权重最小的下一条边并再次尝试。以此类推，直到森林中只有一棵树，即子图包含n-1条边。简而言之，Kruskal算法的调度单位是边，它的信念是：所有的边都可以是小的或小的，算法的实现需要使用和搜索来判断两个点是否在同一个集合中。该算法的具体步骤是：将图中的所有边对象（边长，两端）依次加入到集合（优先队列）q1中。最初所有的点都是相互独立的。取出集合（优先队列）q1中最小的边，判断边的两点是否连通。如果连接表明这两个点已经有其他边连接这两个点，则跳过它。如果没有连接，则使用union（以及搜索和合并）合并两个顶点，并使用这条边（可以存储或计算值）。重复操作2和3，直到集合（优先队列）q1为空。此时选择的边构成最小生成树。普里姆算法除了Kruskal算法外，普里姆算法（Prim'salgorithm）也是一种常用的最小生成树算法。虽然效率差不多。但贪欲之道与克鲁斯卡尔完全不同。prim算法的核心思想是：从已知的扩散中找到最小值。它的实现类似于Dijkstra算法，但略有不同。Dijkstra求的是单源最短路径，每计算一个点，需要更新这个点的距离，而prim不需要更新距离。只要找到已知点的相邻边的最小连接！prim和kruskal算法从边缘开始。具体算法的具体步骤，大致如下：找图中任意一点，以它为起点，将其所有边V加入集合（优先队列）q1，设一个布尔数组bool[]标记位置（边缘有两个点，每次添加所有没有标记该点的边缘）。找到距离集合q1距离最小的边v1，判断边上是否有未标记的点p。如果p不存在，说明已经确定，则跳过当前的边处理。如果未标记（访问），则标记它。点p，以及连接p的未知点（未标记）形成的边加入到集合q1，边v1（距离可以计算，边构成最小生成树）。重复1、2直到q1为空，形成最小生成树！大致步骤如下图所示：因为prim从头到尾都是整体传播的，所以不需要考虑合并两棵树的问题。此时实现起来稍微方便一些。当然需要注意的是，最小生成树并不是唯一的，甚至同一个算法生成的最小生成树也可能不同，但是不管生成什么样的最小生成树都是一样的：它可以保证所有节点都连通（能满足要求和条件）能保证所有路径和最小（结果和目的一样）最小生成树不唯一，各种代码实现都是可以的。上面分析了逻辑实现。下面我们简单的用代码实现上面的算法。primpackage图论；importjava.util.ArrayList；importjava.util.Arrays；importjava.util.Comparator；importjava.util.List；importjava.util.PriorityQueue；importjava.util.Queue；publicclassprim{publicstaticvoidmain(String[]args){intminlength=0;//最小生成树的最短路径长度intmax=66666;Stringcityname[]={"北京","武汉","南京","上海","杭州","广州","深圳""};intcity[][]={{max,8,7,max,max,max,max},//北京和武汉南京联通{8,max,6,max,9,8,max},//武汉——北京、南京、杭州、广州{7,6,max,3,4,max,max},//南京——北京、武汉、上海、杭州{max,max,3,max,2,max,max},//上海-南京,杭州{max,9,4,2,max,max,10},//杭州-武汉,南京,上海,深圳{max,8,max,max,max,max,2},//广州——武汉、深圳{max,max,max,max,10,2,max}//深圳——杭州、广州};//地图booleanistrue[]=newboolean[7];//南京队列
