当前位置:首页 > C++目录 > 正文内容

最小生成树—基本概念

亿万年的星光3个月前 (12-20)C++目录352

一、最小生成树核心概念

1. 基本定义

一个带权无向连通图的最小生成树,是指从该图中选择若干条边,构成一个包含图中所有顶点的树结构(无环、连通),且所有选中边的权值之和最小

2. 关键性质

  • 生成树的本质:包含图中全部n个顶点,且仅有n-1条边(保证无环且连通,增减一条边都会破坏树的性质)。

  • 最小性:所有可能的生成树中,边权总和是最小的。

  • 不唯一性:当图中存在多条相同权值的边时,可能存在多个不同结构但权值和相同的最小生成树。

  • 适用范围:仅适用于无向连通图(非连通图只能求最小生成森林,即每个连通分量的最小生成树集合)。

二、两种经典求解算法

最小生成树的核心求解算法有两种:Kruskal 算法和 Prim 算法,二者思路不同但都能高效求得最优解。

算法 1:Kruskal(克鲁斯卡尔)算法

1. 核心思想

“贪心选边,避环构建”:将所有边按权值从小到大排序,依次遍历每条边,若该边连接的两个顶点属于不同的连通分量(添加后不会形成环),则将其加入生成树;若属于同一连通分量(添加后会形成环),则跳过该边。重复此过程,直到生成树包含n-1条边。

2. 核心依赖:并查集(Union-Find)

并查集是 Kruskal 算法的关键数据结构,用于快速判断两个顶点是否属于同一连通分量,以及合并两个连通分量,操作的时间复杂度接近 O (1)(带路径压缩和按秩合并优化)。

3. 时间复杂度

  • 边排序的时间复杂度:O (E log E)(E 为边数),这是算法的主导复杂度。

  • 并查集操作的时间复杂度:O (E α(V))(α 为阿克曼函数的反函数,增长极慢,可视为常数)。

  • 总体复杂度:O (E log E),适合稀疏图(边数 E 远小于 V²,V 为顶点数)。

算法 2:Prim(普里姆)算法

1. 核心思想

“贪心选点,逐步扩张”:从任意一个起始顶点出发,维护一个 “已加入生成树” 的顶点集合,每次从 “集合内顶点” 与 “集合外顶点” 的所有边中,选择权值最小的那条边,将对应的集合外顶点加入生成树。重复此过程,直到所有顶点都被加入生成树(此时已选n-1条边)。

2. 优化方式:优先队列(最小堆)

使用最小堆(C++ 中priority_queue默认是最大堆,需手动调整为最小堆)可以高效获取 “当前最小权值的跨集合边”,避免暴力遍历所有边,优化时间复杂度。

3. 时间复杂度

  • 未优化(暴力找最小边):O (V²),适合稠密图(边数 E 接近 V²)。

  • 优先队列优化:O (E log V),兼顾稀疏图和稠密图,适用性更广。

三、算法选择指南

特性Kruskal 算法Prim 算法(优先队列优化)
核心思路选边(避环)选点(扩张)
数据结构依赖并查集 + 边集合优先队列 + 邻接表
时间复杂度O(E log E)O(E log V)
适用场景稀疏图(E 较小)稠密图(E 较大),兼顾稀疏图
实现复杂度较简单(并查集需提前实现)稍复杂(邻接表构建)
空间复杂度O (E)(存储所有边)O (V + E)(邻接表存储)

四、应用场景

  1. 网络搭建:如通信网络、公路 / 铁路网络、电力网络等,在连接所有节点的前提下,最小化建设成本(对应边权为建设费用)。

  2. 聚类分析:将数据点视为顶点,点间距离视为边权,最小生成树可用于划分聚类(移除权值较大的边,得到多个连通分量即为不同聚类)。

  3. 图像分割:将图像像素视为顶点,像素间的相似度 / 差异度视为边权,通过最小生成树实现图像的前景与背景分割。

  4. 路径规划:在分布式系统中,通过最小生成树构建高效的消息传递路径,减少通信开销。





    扫描二维码推送至手机访问。

    版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

    分享给朋友:

    相关文章

    【题解】盈亏问题

    【题目描述】一群人团购一件物品:如果每人出 a元,所付总金额比物价多出了x 元;如果每人少出 1元,也就是每人出a-1元,所付总金额比物价少了y元。给定 a,x,y求参与团购的人数及该物品的...

    【数论】杨辉三角

    【数论】杨辉三角

    一、起源 杨辉三角,是二项式系数在三角形中的一种几何排列。在欧洲,这个表叫做帕斯卡三角形。帕斯卡(1623----1662)是在1654年发现这一规律的,比杨辉要迟393年,比贾宪迟600年。杨辉三角...

    如何使用code::blocks编写C++代码

    如何使用code::blocks编写C++代码

    在前面的文章中,已经简单介绍了如何下载code::blocks了,这篇文章介绍一下如何使用code::blocks编写一个C++代码我们打开code::blocks软件,点击”New File“然后点...

    【题解】均分纸牌

    【题目描述】有n堆纸牌,编号分别为 1,2,…, n。每堆上有若干张,但纸牌总数必为n的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编号为1的堆上取的纸牌,只能移到编号为 2 的堆上;在...

    图的访问与存储—临接表

    图的访问与存储—临接表

            在图论中,邻接表(Adjacency List) 是表示图(包括无向图、有向图、带权图)的一种高效数据结构,核心思想是为图中的每个顶点...

    c++ 如何用链表存取数据

    c++ 如何用链表存取数据

    由于单链表的每个结点都有一个数据域和一个指针域。所以,每个结点可以定义成一个记录。其中,DATA数据元素,可以为你想要储存的任何数据格式,可以是数组,可以是int,甚至可以是结构体(这就是传说中的结构...