最小生成树的应用

1. 考虑要使用通信网络链接n个站点, 并且在任意两个站点之间铺设通信链接会产生成本。理想的解决方案是提取称为最小成本生成树的子图。
2. 假设你要构建跨越多个城市的高速公路或铁路, 那么我们可以使用最小生成树的概念。
3. 设计局域网。
4. 铺设连接海上钻井现场, 炼油厂和消费市场的管道。
5. 假设你要套一套带有电力的房屋水电话线污水线

为了降低成本, 你可以使用成本最低的生成树连接房屋。

例如, 问题在于铺设电话线。