【数据结构】最小生成树

1. 最小生成树的概念

对于一个带权连通无向图G=(V,E)，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则T称为G的最小生成树（Minimum-Spanning-Tree,MST）。

• 最小生成树可能有多个，但边的权值之和总是唯一且最小的。
• 最小生成树的边数=定点数-1。砍掉一条则不连通，增加一条边则会出现回路。
• 如果一个连通图本身就是一棵树，则其最小生成树就是它本身。
• 只有连通图才有生成树，非连通图只有生成森林。

2. Prim（普里姆）算法

从某一个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。

说明：从P城开始，1的权值最小，将P城和学校相连，组成一个整体，然后4的权值最小，将P城与矿场相连，组成一个新的整体，依次得到最小生成树。

从其他点开始的方式相同。

3. Kruskal（克鲁斯卡尔）算法

每次选择一条权值最小的边，使这两条边的两头连通（原本已经连通的就不选），直到所有结点都连通。

说明：首先找到了权值为1的边，是P成和学校相连，然后找到了权值为2的边，是矿场和渔村相连，再找到了权值为3的边，是农场和电站相连，再找到权值为4的边，使P城和矿场相连，组成了新的整体，之后找到权值为5的边，使P城和农场相连，这样所有的点就连通起来了。

4. Prim算法 V.S. Kruskal算法

1. Prim算法实现思想

lowCost的值并不是不变的，每一轮会进行更新。

2. Kruskal算法实现思想