正在查看旧版本。 查看 当前版本.
与当前比较 查看页面历史记录
« 前一个 版本 3 下一个 »
最小生成树代表的问题是如何以最小的代价将所有结点连接起来，比如典型地求游历全部城市的最小旅行费用，求给村庄接通电线的最短布线。
最小生成树不是唯一的，比如有相同权值的边的情况。
一个结点发出的最小边一定是生成树里的一条边。
最小生成树对应的图是n个结点n-1条边，也就是没有冗余，断一条边图就不连通了。
