Open lucashaozh opened 1 year ago
https://lucas-hao.github.io/hexo_zh/2022/09/28/algorithms/suan-fa-minimum-spanning-tree/?#more
生成树指的是一个连通图G的覆盖所有顶点的无环子图，最小生成树指的是所有支撑树中加权和最小的生成树。
最小生成树的应用：聚类分析、网络架构设计、VLSI布线设计等诸多实际应用问题，都可转化并描述为最小支 撑树的构造问题。在这些应用中，边的权重大多对应于某种可量化的成本，因此作为对应优化问 题的基本模型，最小支撑树的价值不言而喻。——《数据结构C++版》
求最小支撑树的算法主要采用贪心算法
https://lucas-hao.github.io/hexo_zh/2022/09/28/algorithms/suan-fa-minimum-spanning-tree/?#more
生成树指的是一个连通图G的覆盖所有顶点的无环子图，最小生成树指的是所有支撑树中加权和最小的生成树。
最小生成树的应用：聚类分析、网络架构设计、VLSI布线设计等诸多实际应用问题，都可转化并描述为最小支 撑树的构造问题。在这些应用中，边的权重大多对应于某种可量化的成本，因此作为对应优化问 题的基本模型，最小支撑树的价值不言而喻。——《数据结构C++版》
求最小支撑树的算法主要采用贪心算法