*17.解释一下最小生成树

最小生成树：就是生成树里面最小的。

那么先讲什么是生成树：

生成树必须具备的几个条件：

1.是连通图；

2.含有图的所有顶点（n）;

3.只有n-1条边；

4.任意加一边构成环。

那生成树有什么意义呢？举个例子，假如现在n个村子，这n个村子之间 还没通网络，他们想要彼此之间通网，那么也就是需要把大家连在一个网络里，也就是把每个村子当做顶点放在连通图里。这样子就解决问题了，但是这样子的连通图有很多个，每个村子之间可能会有很多条线，显然会浪费，那么我们就要求只有n-1条网线。这就是生成树。那问题来了，他们最后发现只有n-1条网线的方案也有很多种，他们想知道哪一种线路是总网线长度最短？这个时候他们想出来最小生成树。

从上面我们可以得出最小生成树的概念：

生成树+路径最短

这个时候我就很好奇，这些村民是怎么找出最小生成树的呢？要把所有的生成树画出来后再计算吗？

答案并不是的。他们发明了两种算法：

**Kruskal算法：**就是把每个村的距离先写出来，然后把最小距离的村子之间连起来，然后再看距离第二小的两个村子，如果这两个村子还没连通，那么就把它们连起来，如果连通了就放弃，直接看距离第三小的两个村子。就这样子重复知道所有的顶点都连通。这是一个叫做克鲁斯卡尔的村民提出来，所有叫克鲁斯卡尔算法；

**Prim算法：**对，这是另一个村民提出来的算法，叫普里姆算法。这个算法是基于顶底。首先先选一个村子，然后算出其他相邻的村子到这个村子的距离，把最短的村子连起来。然后再把这两个村子看成 一个整体，看看其他的村子到这两个村子的距离，然后再挑选最短的连起来。重复知道所有的村子都被连起来了。

这个时候有一个村长就说了，克鲁斯卡尔和普里姆两个人算出来的是同一个吗？会不会出现两种不同的方案？

确实，克鲁斯卡尔算法和普里姆算法会有可能出现不同的最小生成树。