最小生成树入门（图解）

1.什么是最小生成树

来看百度百科的定义

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。

意思简单明了就是求最小的连通图
举个栗子

这幅图的极小连通图为

或者

就是从一个点能到达图的任意一点，且花费的代价最小（所有边的权值最小）

2.普里姆（Prim）算法

此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。

从点v1开始选择离v1最近的点，可以发现v1-v3的距离最小，所以把这条边连上

现在v1和v3作为一个整体，看那个点离v1和v3最近，此时有两个点离得最近，按顺序选择v4（也可以选择v6，是一样的）。

现在选择离v1，v3，v4最近的点，现在v4-v6这条边最短，所以选择v4-v6这条边

按照这个思路依次选择，直到把所有的点都选上

3.Prim代码

prim的核心代码为：

int prime()
{
   
    int tip = 0; //tip用来计算距离
    for(int i = 1 ; i <= n ; i++) // 初始化dis为无穷大
        dis[i] = inf;//inf = 99999999；
    memset(book , 0 , sizeof(book));//book用来标记点有没有被选择
    dis[1] = 0
1
2
3
4
5
6
7
8