Siv*_*man 1 minimum-spanning-tree spanning-tree data-structures
你们中有人知道使用生成树数据结构的任何实际应用程序吗？
在网络中，我们经常使用最小生成树算法。所以问题如这里所述，给定一个带加权边的图，找到满足这三个属性的最小总权重的边树：连接、无环和由 |V| 组成。- 1 条边。（事实上，这三个条件中的任何两个都意味着第三个条件。）
举个例子，
例如，如果你有一个有很多交换机的大型局域网，找到一个最小生成树可能很有用，这样只有最少数量的数据包需要通过网络中继，并且同一数据包的多个副本不需要'不会通过不同的路径到达（请记住，任何两个节点仅通过生成树中的一条路径连接）。
其他现实世界的问题包括布置电网，据报道这是 Boruvka 算法的最初动机，Boruvka 算法是最早用于寻找最小生成树的算法之一。找到最小生成树比任何旧生成树都更好，这不足为奇；如果网络上的一棵生成树涉及采用最拥挤、最慢的路径，它可能不会是理想的！
除了计算机网络之外，还有许多其他应用程序，我在下面列出了参考资料：
网络设计： – 电话、电气、液压、电视电缆、计算机、道路 标准应用是针对电话网络设计之类的问题。您的企业有多个办事处；您想租用电话线将它们相互连接起来；电话公司收取不同数量的钱来连接不同的城市对。您需要一组以最低总成本连接所有办公室的线路。它应该是一棵生成树，因为如果网络不是一棵树，您总是可以删除一些边并节省资金。
NP 难问题的近似算法： – 旅行商问题，斯坦纳树 一个不太明显的应用是最小生成树可用于近似解决旅行商问题。定义这个问题的一种方便的正式方法是找到至少访问每个点一次的最短路径。
请注意，如果您有一条路径只访问所有点一次，则它是一种特殊的树。例如在上面的例子中，十六棵生成树中的十二棵实际上是路径。如果你有一条路径不止一次访问某些顶点，你总是可以放下一些边来得到一棵树。所以一般来说，MST 权重小于 TSP 权重，因为它是对严格更大的集合的最小化。
另一方面，如果围绕最小生成树绘制路径跟踪，则对每条边进行两次跟踪并访问所有点，因此 TSP 权重小于 MST 权重的两倍。因此，这次旅行是最佳的两倍。
间接应用： – 最大瓶颈路径 – 用于纠错的 LDPC 代码 – 与 Renyi 熵的图像配准 – 学习用于实时面部验证的显着特征 – 减少蛋白质中氨基酸测序的数据存储 – 湍流流体中粒子相互作用的模型局部性– 以太网桥接的自动配置协议，以避免网络中的循环
聚类分析： k 聚类问题可以看作是找到一个 MST 并删除 k-1 条最昂贵的边。