什么是最小生成树？

Question

如题所述

Answer 1

最小生成树是指从一个给定的连通网络中，选择若干条边，使得所选边的权值之和最小，而且这些边连接了所有的顶点，形成一棵树。

离散数学中求最小生成树的方法有Prim算法和Kruskal算法。

Prim算法：

1. 从图中任意选择一个顶点作为起始顶点，将其加入到最小生成树中；

2. 在未被加入最小生成树的顶点中，找出一条权值最小的边，将该边的另一个顶点加入到最小生成树中；

3. 重复步骤2，直到最小生成树中包含了所有的顶点。

Kruskal算法：

1. 将图中所有的边按照权值从小到大的顺序排列；

2. 从权值最小的边开始，依次选择边加入到最小生成树中，但是要保证加入的边不会形成环；

3. 重复步骤2，直到最小生成树中包含了所有的顶点。