最小生成树在实际生活中的应用非常广泛，可以在很多地方看到最小生成树应用的实例。例如：在一个偏僻的村庄，村户都散落在村庄四处，现在需要进行供电建设，需要使用一条电缆将每家每户连接起来，由于村户距离都间隔比较远，那么这时候需要考虑到成本问题，就需要用最短的距离去连接，而最小生成树的成本就是最少的
什么是最小生成树：
对于一个图来说，如果一个子图包含了图中所有的节点，那么这个子图称为图的一个生成树，在所有子图中，边的权值相加得到的总和最小的子图，称为最小生成树。-
最小生成树的求解算法
- Prim算法
- Kruskal算法
两种算法都采用了贪心的思想，关于贪心的思想，这里先给出解释：贪心的思想核心为在求解问题的时候，只是考虑到当前情况下的最优解，而不是全局的，所以说其实是局部上的最优解，因此贪心的思想不是总是最好的，使用贪心算法必须考虑到是否局部的求解是否会影响到后面，如果会影响，那么贪心算法的效果往往不尽人意。
-
Prim算法
-
Prim算法的求解思想：
先选择一个点，然后选出最短路径，找到这个最短路径连接的点，然后再比较这两个点到其他点的最短路径，依次按照这种贪心思想进行下去，直到每个顶点都被找到。 - Prim算法的具体代码：
-
Prim算法的求解思想：
int c[MAXINT][MAXINT]={{32767,6,1,5,32767,32767},{6,32767,5,32767,3,32767},{1,5,32767,5,6,4},{5,32767,5,32767,32767,2},{32767,3,6,32767,32767,6},{32767,32767,4,2,6,32767}};
void Prim(int n)
{
int lowcost[MAXINT];// 存储最小生成树中的节点到达其他节点的最短距离
int closest[MAXINT];// 其他节点到达最小生成树中最近的节点（实际上就是前驱节点）
bool visited[MAXINT];//bool型变量的S数组表示i是否已经包括在S中
int i,k;
visited[0] = true;//从第一个结点开始
for(i = 1; i <= n; i++)//简单初始化
{
lowcost[i] = c[0][i];
closest[i] = 0; //现在所有的点对应的生成树的最近的点是0
visited[i] = false;
}
for(i = 0; i < n; i++)
{
int min = 32767;
int j = 1;
for(k = 1; k <= n; k++)//寻找lowcost中的最小值
{
if((lowcost[k] < min)&&(!visited[k]))
{
min = lowcost[k];
j = k;
}
}
visited[j] = true;
for(k = 1; k <= n; k++)//因为新加入了j点,所以要查找新加入的j点到未在生成树中的点K中的权值是不是可以因此更小
{
if((c[j][k] < lowcost[k])&&(!visited[k])) {
lowcost[k] =c [j][k];
closest[k] = j;
}
}
}
}
-
Prim算法的细节分析
可以发现，Prim算法中使用到了三个数组：- lowcost [ ]：用来存储最小生成树中的节点到达其他节点的最短距离
- closest [ ]：用来存储其他节点到最小生成树中最近的点（实际上是为了打印最小生成树而建立的前驱节点集合）
- visited [ ]：用来存储每个节点的状态（是否已经在最小生成树中了）
使用到了三个循环：
- 第一个循环：是循环N次，每次加入一个节点到生成树中
- 第二个循环：找到当前lowcost中最小值，并且将改点添加到生成树中来
- 第三个循环：由于新添加了节点，所以需要更新一下lowcost中每个节点的值，同时将符合条件的节点的前驱节点设置为这个新添加的节点
-
Kruskal算法
-
Kruskal算法的求解思想：
求解过程其实是以边为核心的，首先会将所有的边进行排序，按照权重的升序进行排列，然后依次取出，取出的操作为，如果这条边的两个顶点在最小生成树的不同的连通分量中，那么就讲这条边加入到最小生成树中，如果这条边的两个顶点在相同的连通分量中，那么就忽视掉这条边，对下一条边进行操作，直到所有顶点都被加入到了最小生成树中。
-
Kruskal算法的求解思想：
