新闻详情

新闻详情

首页 / 资讯中心 / 详情

深入解析最小生成树:从原理到实战

发布时间:2026/11/20 19:13:55来源:尧图网络
深入解析最小生成树:从原理到实战
在图论与算法设计中最小生成树Minimum Spanning Tree, MST是一个既经典又极具实用价值的问题。它描述的核心任务是对于一个含有nnn个顶点的连通无向带权图G(V,E)G(V,E)G(V,E)我们需要找到一个子图TTT使得TTT是一棵树包含原图的所有顶点并且所有边的权值之和最小。形式上若记各边的权值为w(e)w(e)w(e)则最小生成树的目标是最小化∑e∈Tw(e)\sum_{e \in T} w(e)e∈T∑​w(e)。这里的“生成树”意味着TTT必须连通且无环因此必然恰好包含n−1n-1n−1条边。最小生成树之所以重要是因为它在现实世界中无处不在。无论是通信网络铺设、道路规划还是聚类分析与图像分割本质上都是在寻找一种“代价最低的连接方式”。而解决这一问题的两大基石算法——Kruskal与Prim正是贪心算法思想的完美体现。为了直观理解我们考虑一个经典示例假设有一个包含999个节点、141414条边的无向图其边集如下每条边表示为(u,v,w)(u,v,w)(u,v,w)其中www为权值(0,1,4), (0,7,8), (1,2,8), (1,7,11), (2,3,7), (2,8,2), (2,5,4), (3,4,9), (3,5,14), (4,5,10), (5,6,2), (6,7,1), (6,8,6), (7,8,7)(0,1,4),\ (0,7,8),\ (1,2,8),\ (1,7,11),\ (2,3,7),\ (2,8,2),\ (2,5,4),\ (3,4,9),\ (3,5,14),\ (4,5,10),\ (5,6,2),\ (6,7,1),\ (6,8,6),\ (7,8,7)(0,1,4),(0,7,8),(1,2,8),(1,7,11),(2,3,7),(2,8,2),(2,5,4),(3,4,9),(3,5,14),(4,5,10),(5,6,2),(6,7,1),(6,8,6),(7,8,7)。我们的目标是求出该图的最小生成树及其总权值。Kruskal 算法的思路非常直接且优雅它从“边”的角度出发始终选择当前可用的最短边前提是该边不会与已选边构成环。这种策略的正确性依赖于贪心选择性质。在实现上关键在于高效地判断环这通常借助并查集Union-Find数据结构完成。我们首先对所有边按权值www升序排序然后依次尝试合并两个不连通的顶点集合。最终当成功加入n−1n-1n−1条边时算法结束。下面是 Kruskal 算法的完整 Python 实现classUnionFind:def__init__(self,n):self.parentlist(range(n))deffind(self,x):ifself.parent[x]!x:self.parent[x]self.find(self.parent[x])returnself.parent[x]defunion(self,x,y):fx,fyself.find(x),self.find(y)iffxfy:returnFalseself.parent[fx]fyreturnTruedefkruskal(edges,n):edges.sort(keylambdax:x[2])ufUnionFind(n)mst_weight0mst_edges[]foru,v,winedges:ifuf.union(u,v):mst_weightw mst_edges.append((u,v,w))iflen(mst_edges)n-1:breakreturnmst_weight,mst_edges edges[(0,1,4),(0,7,8),(1,2,8),(1,7,11),(2,3,7),(2,8,2),(2,5,4),(3,4,9),(3,5,14),(4,5,10),(5,6,2),(6,7,1),(6,8,6),(7,8,7)]weight,treekruskal(edges,9)print(Kruskal 最小生成树权值:,weight)运行结果为373737这意味着我们找到了一棵总代价为373737的最优连接方案。与 Kruskal 不同Prim 算法是从“点”的角度进行扩展。它从一个任意选定的起始顶点开始逐步将距离当前生成树最近的未访问顶点纳入集合中。这个过程与 Dijkstra 单源最短路径算法极为相似区别在于 Prim 关注的是连接两个集合的“跨边”的最小权值而非路径累计长度。为了保证每次都能快速找到最小权边通常使用优先队列最小堆来维护候选边。以下是 Prim 算法的实现代码importheapqdefprim(graph,start0):visitedset()min_heap[(0,start,-1)]mst_weight0mst_edges[]whilelen(visited)len(graph):w,u,parentheapq.heappop(min_heap)ifuinvisited:continuevisited.add(u)mst_weightwifparent!-1:mst_edges.append((parent,u,w))forv,weightingraph[u]:ifvnotinvisited:heapq.heappush(min_heap,(weight,v,u))returnmst_weight,mst_edges# 定义边列表edges[(0,1,4),(0,7,8),(1,2,8),(1,7,11),(2,3,7),(2,8,2),(2,5,4),(3,4,9),(3,5,14),(4,5,10),(5,6,2),(6,7,1),(6,8,6),(7,8,7)]# 构建邻接表graph[[]for_inrange(9)]foru,v,winedges:graph[u].append((v,w))graph[v].append((u,w))weight,treeprim(graph)print(Prim 最小生成树权值:,weight)同样Prim 算法也输出了373737。这验证了无论采用哪种贪心策略只要逻辑正确最终都能收敛到全局最优解尽管具体的树结构可能不唯一。那么在实际应用中应该如何选择这两种算法呢这取决于图的密度。Kruskal 算法的时间复杂度主要由边的排序决定为O(Elog⁡E)O(E \log E)O(ElogE)因此它更适合稀疏图尤其是当边数EEE远小于顶点数平方时。此外Kruskal 的代码通常更简洁。而 Prim 算法使用堆优化后的时间复杂度为O(Elog⁡V)O(E \log V)O(ElogV)在处理稠密图时表现更优因为它不需要对边进行排序且可以通过邻接矩阵进一步优化至O(V2)O(V^2)O(V2)。简而言之Kruskal 看边Prim 看点。值得注意的是最小生成树并不一定是唯一的。当图中存在权值相同的边时不同的选择顺序可能会导致不同形态的生成树但只要权值相同它们都是最优解。这一性质在某些需要多样性决策的场景中也具有重要的应用价值。掌握最小生成树不仅是掌握了一种算法更是理解了如何将复杂的系统优化问题转化为清晰的数学模型。
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/20 0:44:51

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/19 15:17:14

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/19 20:26:12

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/20 16:11:20

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/20 18:41:01

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/20 0:44:55

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉