【运筹学】最小生成树问题

【运筹学】最小生成树问题

引用

CSDN

1.

https://blog.csdn.net/TuTuTuhong/article/details/141144832

最小生成树问题（MST，Minimum Spanning Tree）是运筹学中的一个经典问题，在计算机网络、通信网络、电力网络规划等领域有着广泛的应用。本文将从基础知识出发，逐步介绍最小生成树的定义、实际应用和求解方法。

1 最小生成树问题

1.1 基础知识（树与生成树）

在讲最小生成树问题之前，我们先回顾树和生成树的概念。

树就是连通的、不包含圈的图；生成树就是在某个图中，连通所有节点的树。

1.2 问题定义

最小生成树（MST，Minimum Spanning Tree），或者最小权重生成树，就是从某一图中找出其总权重最小的生成树。对应的有最大生成树问题，也就是找出总权重最大的生成树。

如图，我们展示了这个图所有的生成树的情况， 我们可以很直观的计算出，按顺序对应的总权重是92，86，68，78，78，94，84，88，因此最小生成树就是图c)对应的生成树，最大生成树就是图f)对应的生成树。

1.3 实际应用

为什么我们想要求取最小生成树，在实际问题中有何用呢？最小生成树在现实中应用十分广泛。如计算机网络或通信网络设计、电力网络规划、交通网络优化等等。

1.4 求解方法

求解最小生成树问题有许多经典有效的算法，其核心都是贪心算法，下一章我们会从贪心算法的角度讲解如何求解最小生成树问题，并对比几种经典算法。

2 参考资料

来自教材：运筹学（原书第2版）_百度百科 (baidu.com)