最小生成树

定义：

求最小生成树的算法：

Prim（普里姆）算法：

1：P城纳入（以该顶点开始）

2.寻找代价最小的边，并将对应顶点纳入最小生成树中：

3.p城和学校看作一个整体（一颗生成树），在寻找能纳入树的代价最小的边和对应的顶点：
此时有两条边对应的代价最小（都为4），任取一条先纳入，取的不同最后的最小生成树也不同，之后会有，先取矿场所对应的边

4.依次类推

5.

6.

最后得到的最小生成树如下：

如果步骤3选择渔村对应的边则最后生成的最小生成树如下：

Kruskal（克鲁斯卡尔）算法：

过程王道P224

两种算法的比较：