基本信息
文件名称：小生成树算法构建城市间通讯网络优化方案.pdf
文件大小：1.74 MB
总页数：27 页
更新时间：2026-04-03
总字数：约6.95千字
文档摘要
8.4最小生成树
问题描述：
假设要在n个城市之间建立通讯联络网，则连通n个
城市只需要修建n-1条线路，如何在最节省的前提下
建立这个通讯网？
该问题等价于：
构造网的一棵最小生成树，即：在e条带权的边
中选取n-1条边（不构成回路），使“权值之和”为最
小，即最小生成树。
该问题等价于：
构造网的一棵最小生