上次我们介绍了图的邻接表存储结构基本操作的实现，这次介绍基于邻接矩阵的两种最小生成树算法的实现。
还是老规矩：
程序在码云上可以下载。
地址：https://git.oschina.net/601345138/DataStructureCLanguage.git
最小生成树有两个经典的算法：
1.普里姆算法：主要是针对顶点操作，选最小邻接边组成生成树。
2.克鲁斯卡尔算法：主要针对边操作，所有边里选最小权值的边组成生成树。
本次最小生成树共用到以下源文件，有一些已经在之前的文章介绍过。还是和以前一样，所有源文件需要放在同一目录下编译。
my_constants.h 各种状态码定义
MGraph.h 图的邻接矩阵存储结构表示定义
MGraph.cpp 基于邻接矩阵的基本操作实现
MiniSpanTree.cpp 普利姆算法和克鲁斯卡尔算法的实现（含有动态演示代码）
最小生成树测试.cpp 主函数，调用算法完成最小生成树的动态演示
邻接矩阵在《数据结构编程笔记十八：第七章 图 图的邻接矩阵存储表示及各基本操作的实现》一文有所介绍，my_constants.h、MGraph.h 和MGraph.cpp三个源文件与此文中的同名源文件内容完全一致，没有修改。这里不再重复贴了（否则文章会很长，不能突出重点），但在码云上你可以下载到全部源文件，我会把它放在一个目录下。
本次只贴最小生成树的核心代码和主函数：
源文件：MiniSpanTree.cpp
//-------------- 最小生成树 ----------------------------
//-------------------辅助数组的定义-------------------------------
struct Record{
VertexType adjvex; //顶点
VRType lowcost; //最低代价
}closedge[MAX_VERTEX_NUM];
/*
函数：printColsedge
参数：Record closedge[] 计算最小生成树的辅助数组closedge
int n 顶点数
返回值：无
作用：打印closedge数组
*/
void printColsedge(Record closedge[], MGraph G) {
//打印i一行
printf("+----------+");
for(int i = 0; i < G.vexnum; i++) {
printf("-----+");
}//for
printf("\n");
printf("| i |");
for(int i = 0; i < G.vexnum; i++) {
printf(" %2d |", i);
}//for
printf("\n");
printf("+----------+");
for(int i = 0; i < G.vexnum; i++) {
printf("-----+");
}//for
printf("\n");
//顶点值
printf("| 顶点 |");
for(int i = 0; i < G.vexnum; i++) {
printf(" %2d |", G.vexs[i]);
}//for
printf("\n");
printf("+----------+");
for(int i = 0; i < G.vexnum; i++) {
printf("-----+");
}//for
printf("\n");
//打印adjvex一行
printf("| adjvex |");
for(int i = 0; i < G.vexnum; i++) {
printf(" %3d |", closedge[i].adjvex);
}//for
printf("\n");
printf("+----------+");
for(int i = 0; i < G.vexnum; i++) {
printf("-----+");
}//for
printf("\n");
//打印lowcost一行
printf("| lowcost |");
for(int i = 0; i < G.vexnum; i++) {
if(closedge[i].lowcost != INFINITY) {
printf(" %3d |", closedge[i].lowcost);
}//if
else {
printf(" ∞ |");
}//else
}//for
printf("\n");
printf("+----------+");
for(int i = 0; i < G.vexnum; i++) {
printf("-----+");
}//for
printf("\n");
}//printColsedge
/*
函数：minimum
参数：Record closedge[] 计算最小生成树的辅助数组closedge
返回值：选出顶点的序号
作用：从closedge数组中选出符合条件的最小生成树的下一顶点
*/
int minimum(Record closedge[]){
//min是从closedge数组中选出的最小代价边的另一个顶点在图中的位置
//reserve是辅助参与比较的最小代价，初始值为65535，
//每一次发现代价比它更小的边则reserve会被更新为新的最小代价
int reserve = 65535, min = 0;
for(int i = 1; i < MAX_VERTEX_NUM; i++) {
//没有访问过但是存在路径并且代价更小（比记录最小代价的reserve还小）
if(closedge[i].lowcost < reserve && closedge[i].lowcost > 0){
printf("->发现比reserve = %d更小的权值：closedge[%d].lowcost = %d ！\n",
reserve, i, closedge[i].lowcost);
//reserve更新为新的最小代价
reserve = closedge[i].lowcost;
//min更新为最小代价边的另一顶点在图中的位置
min = i;
}//if
}//for
return min;
}//minimum
/* （普里姆算法求最小生成树）
函数：MiniSpanTree_PRIM
参数：MGraph G 图G
返回值：无
作用：用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边
记录从定点集U到V-U的代价最小的边的辅助数组定义
*/
void MiniSpanTree_PRIM(MGraph G, VertexType u){
//k是出发顶点u在图中的序号
int k = LocateVex(G, u);
//辅助数组初始化
for(int j = 0; j < G.vexnum; ++j) {
//j指示的顶点不是出发顶点
if(j != k){
//{adjvex, lowcost}
//设置邻接点为起始顶点u
closedge[j].adjvex = u;
//设置closedge数组初始最小代价，其实就是
//直接拷贝第G.arcs二维数组的第k行
closedge[j].lowcost = G.arcs[k][j].adj;
}//if
}//for
//设置出发点u的最小代价为0，此时U={u}
closedge[k].lowcost = 0;
printf("\n->最小生成树从顶点%d开始，所以该顶点此时已被加入最小生成树顶点集合！\n\n", G.vexs[k]);
//从顶点u开始生成最小生成树
for(int i = 1; i < G.vexnum; ++i) {
printf("\n->这是第%d趟循环：\n" , i);
printf("->更新closedge数组之前，closedge数组的值(adjvex是顶点序号，不是顶点名称，lowcost = 0表示该顶点已被纳入最小生成树的顶点集合)：\n");
//打印closedge数组
printColsedge(closedge, G);
printf("->开始求最小生成树的下一顶点：\n");
//求出最小生成树的下一个结点：第k顶点
//此时closedge[k].lowcost= MIN{ closedge[vi].lowcost
// | closedge[vi].lowcost > 0, vi ∈V-U}
k = minimum(closedge);
printf("->求得最小生成树的下一顶点为：%d，下一顶点序号k = %d, 最小代价为：%d\n", G.vexs[k], k, closedge[k].lowcost);
//输出生成树的边及其权值
printf("\n->得到最小生成树的一条新边： %2d <--- %2d ---> %2d \n\n", closedge[k].adjvex,
closedge[k].lowcost, G.vexs[k]);
//第k顶点并入U集
closedge[k].lowcost = 0;
//查找k的邻接顶点中代价更小的边对应的邻接顶点
//将新顶点并入U后重新选择最小边
//选出一个顶点k之后需要更新closedge数组中最小边信息
for(int j = 1; j < G.vexnum; ++j) {
//发现代价更小的边就更新closedge数组
//若没有发现则保持原值不变
if(G.arcs[k][j].adj < closedge[j].lowcost){
printf("从%d的所有邻接顶点中发现有G.arcs[%d][%d].adj = %d 比 closedge[%d].lowcost = %d 更小，更新closedge数组！\n",
G.vexs[k], k, j, G.arcs[k][j].adj, j, closedge[j].lowcost);
//更新closedge数组的邻接点信息adjvex
closedge[j].adjvex = G.vexs[k];
//更新closedge数组的最小边信息lowcost
closedge[j].lowcost = G.arcs[k][j].adj;
}//if
}//for
printf("\n->更新closedge数组之后，closedge数组的值(adjvex是顶点序号，不是顶点名称，lowcost = 0表示该顶点已被纳入最小生成树的顶点集合)：\n");
//打印closedge数组
printColsedge(closedge, G);
system("pause");
}//for
}//MiniSpanTree_PRIM
/*
函数：printSet
参数：int set[] 保存顶点所属集合状态的数组set
MGraph G 图G
返回值：无
作用：打印set数组
*/
void printSet(int set[], MGraph G) {
//打印i一行
printf("+----------+");
for(int i = 0; i < G.vexnum; i++) {
printf("-----+");
}//for
printf("\n");
printf("| i |");
for(int i = 0; i < G.vexnum; i++) {
printf(" %2d |", i);
}//for
printf("\n");
printf("+----------+");
for(int i = 0; i < G.vexnum; i++) {
printf("-----+");
}//for
printf("\n");
//顶点值
printf("| 顶点 |");
for(int i = 0; i < G.vexnum; i++) {
printf(" %2d |", G.vexs[i]);
}//for
printf("\n");
printf("+----------+");
for(int i = 0; i < G.vexnum; i++) {
printf("-----+");
}//for
printf("\n");
//打印set一行
printf("| set |");
for(int i = 0; i < G.vexnum; i++) {
printf(" %3d |", set[i]);
}//for
printf("\n");
printf("+----------+");
for(int i = 0; i < G.vexnum; i++) {
printf("-----+");
}//for
printf("\n");
}//printSet
/* （克鲁斯卡尔算法求最小生成树）
函数：MiniSpanTree_kruskal
参数：MGraph G 图G
返回值：无
作用：克鲁斯卡尔算法求最小生成树
*/
void MiniSpanTree_kruskal(MGraph G) {
int set[MAX_VERTEX_NUM];
int k = 0, a = 0, b = 0, setb, min = G.arcs[a][b].adj;
//set[]初态，各顶点分别属于各个集合
for(int i = 0; i < G.vexnum; i++) {
set[i] = i;
}//for
printf("->set数组初始状态（各顶点分别属于各个集合）：\n");
printSet(set, G);
printf("最小代价生成树的各条边及权值为:\n");
//最小生成树的边数应该有n-1条边，其中n为顶点数
while(k < G.vexnum-1) {
printf("\n->这是第%d趟循环，寻找更小权值的边：\n", k + 1);
//寻找最小权值的边
for(int i = 0; i < G.vexnum; ++i) {
//无向网，只在上三角查找
for(int j = i + 1; j < G.vexnum; ++j) {
//发现比min更小的权值
if(G.arcs[i][j].adj < min) {
printf("->发现比min = %d 更小的权值：%d，修改min为该值！\n", min, G.arcs[i][j].adj);
//最小权值
min = G.arcs[i][j].adj;
//边的一个顶点
a = i;
//边的另一个顶点
b = j;
}//if
}//for
}//for
//边的两顶点不属于同一集合
if(set[a] != set[b]) {
//输出该边
printf("->找到一条最小生成树的新边：%d <-- %d --> %d\n", G.vexs[a], G.arcs[a][b].adj, G.vexs[b]);
}//if
//重置min为极大值
min = G.arcs[a][b].adj = INFINITY;
//边的两顶点不属于同一集合
if(set[a] != set[b]) {
//边数+1
k++;
//保存setb的值
setb = set[b];
//将顶点b所在集合并入顶点a集合中
for(int i = 0; i < G.vexnum; i++) {
//不可以直接set[i] == set[b]作为比较条件，因为i可能等于b！
//一旦set[b]被修改，那么set[b]后面的元素将无法正确合并
if(set[i] == setb) {
printf("->合并顶点%d到顶点%d的集合中，注意set数组的变化。\n", G.vexs[i], G.vexs[a]);
set[i] = set[a];
}//if
}//for
printf("->set数组修改后的值：\n");
printSet(set, G);
}//if
}//while
printf("->set数组初最终状态(无向连通网所有顶点应该都在一个集合里)：\n");
printSet(set, G);
}//MiniSpanTree_kruskal源文件：最小生成树测试.cpp
//**************************引入头文件*****************************
#include <stdio.h> //使用了标准库函数
#include <stdlib.h> //使用了动态内存分配函数
#include "my_constants.h" //引入自定义的符号常量，主要是状态码
#include "MGraph.h" //引入图的邻接矩阵表示法的基本定义
#include "MGraph.cpp" //引入图的主要操作
#include "MiniSpanTree.cpp" //引入最小生成树实现
//----------------------主函数----------------------
int main(int argc, char *argv[]){
printf("\n-------------最小生成树（邻接矩阵）测试程序--------------\n\n");
//图G
MGraph G;
//临时变量，保存输入的顶点数
int n;
//图的创建
printf("->测试图的创建（最小生成树操作要求图的类型是无向连通网，请选择3）：\n");
CreateGraph(G);
//打印邻接矩阵
printf("\n->创建成功后图的邻接矩阵:\n\n");
PrintAdjMatrix(G);
//若为无向网，求其最小生成树
if(G.kind == UDN){
printf("\n->测试普利姆算法求无向网的最小生成树\n");
MiniSpanTree_PRIM(G, G.vexs[0]);
printf("\n->测试克鲁斯卡尔算法求无向网的最小生成树\n");
MiniSpanTree_kruskal(G);
}//if
else {
printf("\n->您生成的不是无向网，无法求最小生成树！\n");
}//else
//测试销毁
printf("\n->测试销毁图： ");
DestroyGraph(G);
printf("成功！\n");
printf("演示结束，程序退出！\n");
return 0;
} 程序运行输入的数据和输出（输入的无向图来自教材P174页，你可以对比图7.17的数据和输出的数据是否一致）：
-------------最小生成树（邻接矩阵）测试程序--------------
->测试图的创建（最小生成树操作要求图的类型是无向连通网，请选择3）：
请输入您想构造的图的类型:有向图输入0,有向网输入1,无向图输入2,无向网输入3):3
请依次输入无向网G的顶点数，弧数，用逗号隔开
6,10
请依次输入无向网G的顶点名称，用空格隔开
1 2 3 4 5 6
请依次输入无向网G每条弧依附的两顶点名称及权值，输完一组按回车
1 2 6
1 4 5
1 3 1
3 2 5
3 4 5
3 5 6
3 6 4
2 5 3
4 6 2
5 6 6
->创建成功后图的邻接矩阵:
1 2 3 4 5 6
+------------------------------
1 | ∞ 6 1 5 ∞ ∞
|
2 | 6 ∞ 5 ∞ 3 ∞
|
3 | 1 5 ∞ 5 6 4
|
4 | 5 ∞ 5 ∞ ∞ 2
|
5 | ∞ 3 6 ∞ ∞ 6
|
6 | ∞ ∞ 4 2 6 ∞
|
->测试普利姆算法求无向网的最小生成树
->最小生成树从顶点1开始，所以该顶点此时已被加入最小生成树顶点集合！
->这是第1趟循环：
->更新closedge数组之前，closedge数组的值(adjvex是顶点序号，不是顶点名称，lowcost = 0表示该顶点已被纳入最小生成树的顶点集合)：
+----------+-----+-----+-----+-----+-----+-----+
| i | 0 | 1 | 2 | 3 | 4 | 5 |
+----------+-----+-----+-----+-----+-----+-----+
| 顶点 | 1 | 2 | 3 | 4 | 5 | 6 |
+----------+-----+-----+-----+-----+-----+-----+
| adjvex | 0 | 1 | 1 | 1 | 1 | 1 |
+----------+-----+-----+-----+-----+-----+-----+
| lowcost | 0 | 6 | 1 | 5 | ∞ | ∞ |
+----------+-----+-----+-----+-----+-----+-----+
->开始求最小生成树的下一顶点：
->发现比reserve = 65535更小的权值：closedge[1].lowcost = 6 ！
->发现比reserve = 6更小的权值：closedge[2].lowcost = 1 ！
->求得最小生成树的下一顶点为：3，下一顶点序号k = 2, 最小代价为：1
->得到最小生成树的一条新边： 1 <--- 1 ---> 3
从3的所有邻接顶点中发现有G.arcs[2][1].adj = 5 比 closedge[1].lowcost = 6 更小，更新closedge数组！
从3的所有邻接顶点中发现有G.arcs[2][4].adj = 6 比 closedge[4].lowcost = 65535 更小，更新closedge数组！
从3的所有邻接顶点中发现有G.arcs[2][5].adj = 4 比 closedge[5].lowcost = 65535 更小，更新closedge数组！
->更新closedge数组之后，closedge数组的值(adjvex是顶点序号，不是顶点名称，lowcost = 0表示该顶点已被纳入最小生成树的顶点集合)：
+----------+-----+-----+-----+-----+-----+-----+
| i | 0 | 1 | 2 | 3 | 4 | 5 |
+----------+-----+-----+-----+-----+-----+-----+
| 顶点 | 1 | 2 | 3 | 4 | 5 | 6 |
+----------+-----+-----+-----+-----+-----+-----+
| adjvex | 0 | 3 | 1 | 1 | 3 | 3 |
+----------+-----+-----+-----+-----+-----+-----+
| lowcost | 0 | 5 | 0 | 5 | 6 | 4 |
+----------+-----+-----+-----+-----+-----+-----+
请按任意键继续. . .
->这是第2趟循环：
->更新closedge数组之前，closedge数组的值(adjvex是顶点序号，不是顶点名称，lowcost = 0表示该顶点已被纳入最小生成树的顶点集合)：
+----------+-----+-----+-----+-----+-----+-----+
| i | 0 | 1 | 2 | 3 | 4 | 5 |
+----------+-----+-----+-----+-----+-----+-----+
| 顶点 | 1 | 2 | 3 | 4 | 5 | 6 |
+----------+-----+-----+-----+-----+-----+-----+
| adjvex | 0 | 3 | 1 | 1 | 3 | 3 |
+----------+-----+-----+-----+-----+-----+-----+
| lowcost | 0 | 5 | 0 | 5 | 6 | 4 |
+----------+-----+-----+-----+-----+-----+-----+
->开始求最小生成树的下一顶点：
->发现比reserve = 65535更小的权值：closedge[1].lowcost = 5 ！
->发现比reserve = 5更小的权值：closedge[5].lowcost = 4 ！
->求得最小生成树的下一顶点为：6，下一顶点序号k = 5, 最小代价为：4
->得到最小生成树的一条新边： 3 <--- 4 ---> 6
从6的所有邻接顶点中发现有G.arcs[5][3].adj = 2 比 closedge[3].lowcost = 5 更小，更新closedge数组！
->更新closedge数组之后，closedge数组的值(adjvex是顶点序号，不是顶点名称，lowcost = 0表示该顶点已被纳入最小生成树的顶点集合)：
+----------+-----+-----+-----+-----+-----+-----+
| i | 0 | 1 | 2 | 3 | 4 | 5 |
+----------+-----+-----+-----+-----+-----+-----+
| 顶点 | 1 | 2 | 3 | 4 | 5 | 6 |
+----------+-----+-----+-----+-----+-----+-----+
| adjvex | 0 | 3 | 1 | 6 | 3 | 3 |
+----------+-----+-----+-----+-----+-----+-----+
| lowcost | 0 | 5 | 0 | 2 | 6 | 0 |
+----------+-----+-----+-----+-----+-----+-----+
请按任意键继续. . .
->这是第3趟循环：
->更新closedge数组之前，closedge数组的值(adjvex是顶点序号，不是顶点名称，lowcost = 0表示该顶点已被纳入最小生成树的顶点集合)：
+----------+-----+-----+-----+-----+-----+-----+
| i | 0 | 1 | 2 | 3 | 4 | 5 |
+----------+-----+-----+-----+-----+-----+-----+
| 顶点 | 1 | 2 | 3 | 4 | 5 | 6 |
+----------+-----+-----+-----+-----+-----+-----+
| adjvex | 0 | 3 | 1 | 6 | 3 | 3 |
+----------+-----+-----+-----+-----+-----+-----+
| lowcost | 0 | 5 | 0 | 2 | 6 | 0 |
+----------+-----+-----+-----+-----+-----+-----+
->开始求最小生成树的下一顶点：
->发现比reserve = 65535更小的权值：closedge[1].lowcost = 5 ！
->发现比reserve = 5更小的权值：closedge[3].lowcost = 2 ！
->求得最小生成树的下一顶点为：4，下一顶点序号k = 3, 最小代价为：2
->得到最小生成树的一条新边： 6 <--- 2 ---> 4
->更新closedge数组之后，closedge数组的值(adjvex是顶点序号，不是顶点名称，lowcost = 0表示该顶点已被纳入最小生成树的顶点集合)：
+----------+-----+-----+-----+-----+-----+-----+
| i | 0 | 1 | 2 | 3 | 4 | 5 |
+----------+-----+-----+-----+-----+-----+-----+
| 顶点 | 1 | 2 | 3 | 4 | 5 | 6 |
+----------+-----+-----+-----+-----+-----+-----+
| adjvex | 0 | 3 | 1 | 6 | 3 | 3 |
+----------+-----+-----+-----+-----+-----+-----+
| lowcost | 0 | 5 | 0 | 0 | 6 | 0 |
+----------+-----+-----+-----+-----+-----+-----+
请按任意键继续. . .
->这是第4趟循环：
->更新closedge数组之前，closedge数组的值(adjvex是顶点序号，不是顶点名称，lowcost = 0表示该顶点已被纳入最小生成树的顶点集合)：
+----------+-----+-----+-----+-----+-----+-----+
| i | 0 | 1 | 2 | 3 | 4 | 5 |
+----------+-----+-----+-----+-----+-----+-----+
| 顶点 | 1 | 2 | 3 | 4 | 5 | 6 |
+----------+-----+-----+-----+-----+-----+-----+
| adjvex | 0 | 3 | 1 | 6 | 3 | 3 |
+----------+-----+-----+-----+-----+-----+-----+
| lowcost | 0 | 5 | 0 | 0 | 6 | 0 |
+----------+-----+-----+-----+-----+-----+-----+
->开始求最小生成树的下一顶点：
->发现比reserve = 65535更小的权值：closedge[1].lowcost = 5 ！
->求得最小生成树的下一顶点为：2，下一顶点序号k = 1, 最小代价为：5
->得到最小生成树的一条新边： 3 <--- 5 ---> 2
从2的所有邻接顶点中发现有G.arcs[1][4].adj = 3 比 closedge[4].lowcost = 6 更小，更新closedge数组！
->更新closedge数组之后，closedge数组的值(adjvex是顶点序号，不是顶点名称，lowcost = 0表示该顶点已被纳入最小生成树的顶点集合)：
+----------+-----+-----+-----+-----+-----+-----+
| i | 0 | 1 | 2 | 3 | 4 | 5 |
+----------+-----+-----+-----+-----+-----+-----+
| 顶点 | 1 | 2 | 3 | 4 | 5 | 6 |
+----------+-----+-----+-----+-----+-----+-----+
| adjvex | 0 | 3 | 1 | 6 | 2 | 3 |
+----------+-----+-----+-----+-----+-----+-----+
| lowcost | 0 | 0 | 0 | 0 | 3 | 0 |
+----------+-----+-----+-----+-----+-----+-----+
请按任意键继续. . .
->这是第5趟循环：
->更新closedge数组之前，closedge数组的值(adjvex是顶点序号，不是顶点名称，lowcost = 0表示该顶点已被纳入最小生成树的顶点集合)：
+----------+-----+-----+-----+-----+-----+-----+
| i | 0 | 1 | 2 | 3 | 4 | 5 |
+----------+-----+-----+-----+-----+-----+-----+
| 顶点 | 1 | 2 | 3 | 4 | 5 | 6 |
+----------+-----+-----+-----+-----+-----+-----+
| adjvex | 0 | 3 | 1 | 6 | 2 | 3 |
+----------+-----+-----+-----+-----+-----+-----+
| lowcost | 0 | 0 | 0 | 0 | 3 | 0 |
+----------+-----+-----+-----+-----+-----+-----+
->开始求最小生成树的下一顶点：
->发现比reserve = 65535更小的权值：closedge[4].lowcost = 3 ！
->求得最小生成树的下一顶点为：5，下一顶点序号k = 4, 最小代价为：3
->得到最小生成树的一条新边： 2 <--- 3 ---> 5
->更新closedge数组之后，closedge数组的值(adjvex是顶点序号，不是顶点名称，lowcost = 0表示该顶点已被纳入最小生成树的顶点集合)：
+----------+-----+-----+-----+-----+-----+-----+
| i | 0 | 1 | 2 | 3 | 4 | 5 |
+----------+-----+-----+-----+-----+-----+-----+
| 顶点 | 1 | 2 | 3 | 4 | 5 | 6 |
+----------+-----+-----+-----+-----+-----+-----+
| adjvex | 0 | 3 | 1 | 6 | 2 | 3 |
+----------+-----+-----+-----+-----+-----+-----+
| lowcost | 0 | 0 | 0 | 0 | 0 | 0 |
+----------+-----+-----+-----+-----+-----+-----+
请按任意键继续. . .
->测试克鲁斯卡尔算法求无向网的最小生成树
->set数组初始状态（各顶点分别属于各个集合）：
+----------+-----+-----+-----+-----+-----+-----+
| i | 0 | 1 | 2 | 3 | 4 | 5 |
+----------+-----+-----+-----+-----+-----+-----+
| 顶点 | 1 | 2 | 3 | 4 | 5 | 6 |
+----------+-----+-----+-----+-----+-----+-----+
| set | 0 | 1 | 2 | 3 | 4 | 5 |
+----------+-----+-----+-----+-----+-----+-----+
最小代价生成树的各条边及权值为:
->这是第1趟循环，寻找更小权值的边：
->发现比min = 65535 更小的权值：6，修改min为该值！
->发现比min = 6 更小的权值：1，修改min为该值！
->找到一条最小生成树的新边：1 <-- 1 --> 3
->合并顶点3到顶点1的集合中，注意set数组的变化。
->set数组修改后的值：
+----------+-----+-----+-----+-----+-----+-----+
| i | 0 | 1 | 2 | 3 | 4 | 5 |
+----------+-----+-----+-----+-----+-----+-----+
| 顶点 | 1 | 2 | 3 | 4 | 5 | 6 |
+----------+-----+-----+-----+-----+-----+-----+
| set | 0 | 1 | 0 | 3 | 4 | 5 |
+----------+-----+-----+-----+-----+-----+-----+
->这是第2趟循环，寻找更小权值的边：
->发现比min = 65535 更小的权值：6，修改min为该值！
->发现比min = 6 更小的权值：5，修改min为该值！
->发现比min = 5 更小的权值：3，修改min为该值！
->发现比min = 3 更小的权值：2，修改min为该值！
->找到一条最小生成树的新边：4 <-- 2 --> 6
->合并顶点6到顶点4的集合中，注意set数组的变化。
->set数组修改后的值：
+----------+-----+-----+-----+-----+-----+-----+
| i | 0 | 1 | 2 | 3 | 4 | 5 |
+----------+-----+-----+-----+-----+-----+-----+
| 顶点 | 1 | 2 | 3 | 4 | 5 | 6 |
+----------+-----+-----+-----+-----+-----+-----+
| set | 0 | 1 | 0 | 3 | 4 | 3 |
+----------+-----+-----+-----+-----+-----+-----+
->这是第3趟循环，寻找更小权值的边：
->发现比min = 65535 更小的权值：6，修改min为该值！
->发现比min = 6 更小的权值：5，修改min为该值！
->发现比min = 5 更小的权值：3，修改min为该值！
->找到一条最小生成树的新边：2 <-- 3 --> 5
->合并顶点5到顶点2的集合中，注意set数组的变化。
->set数组修改后的值：
+----------+-----+-----+-----+-----+-----+-----+
| i | 0 | 1 | 2 | 3 | 4 | 5 |
+----------+-----+-----+-----+-----+-----+-----+
| 顶点 | 1 | 2 | 3 | 4 | 5 | 6 |
+----------+-----+-----+-----+-----+-----+-----+
| set | 0 | 1 | 0 | 3 | 1 | 3 |
+----------+-----+-----+-----+-----+-----+-----+
->这是第4趟循环，寻找更小权值的边：
->发现比min = 65535 更小的权值：6，修改min为该值！
->发现比min = 6 更小的权值：5，修改min为该值！
->发现比min = 5 更小的权值：4，修改min为该值！
->找到一条最小生成树的新边：3 <-- 4 --> 6
->合并顶点4到顶点3的集合中，注意set数组的变化。
->合并顶点6到顶点3的集合中，注意set数组的变化。
->set数组修改后的值：
+----------+-----+-----+-----+-----+-----+-----+
| i | 0 | 1 | 2 | 3 | 4 | 5 |
+----------+-----+-----+-----+-----+-----+-----+
| 顶点 | 1 | 2 | 3 | 4 | 5 | 6 |
+----------+-----+-----+-----+-----+-----+-----+
| set | 0 | 1 | 0 | 0 | 1 | 0 |
+----------+-----+-----+-----+-----+-----+-----+
->这是第5趟循环，寻找更小权值的边：
->发现比min = 65535 更小的权值：6，修改min为该值！
->发现比min = 6 更小的权值：5，修改min为该值！
->这是第5趟循环，寻找更小权值的边：
->发现比min = 65535 更小的权值：6，修改min为该值！
->发现比min = 6 更小的权值：5，修改min为该值！
->找到一条最小生成树的新边：2 <-- 5 --> 3
->合并顶点1到顶点2的集合中，注意set数组的变化。
->合并顶点3到顶点2的集合中，注意set数组的变化。
->合并顶点4到顶点2的集合中，注意set数组的变化。
->合并顶点6到顶点2的集合中，注意set数组的变化。
->set数组修改后的值：
+----------+-----+-----+-----+-----+-----+-----+
| i | 0 | 1 | 2 | 3 | 4 | 5 |
+----------+-----+-----+-----+-----+-----+-----+
| 顶点 | 1 | 2 | 3 | 4 | 5 | 6 |
+----------+-----+-----+-----+-----+-----+-----+
| set | 1 | 1 | 1 | 1 | 1 | 1 |
+----------+-----+-----+-----+-----+-----+-----+
->set数组初最终状态(无向连通网所有顶点应该都在一个集合里)：
+----------+-----+-----+-----+-----+-----+-----+
| i | 0 | 1 | 2 | 3 | 4 | 5 |
+----------+-----+-----+-----+-----+-----+-----+
| 顶点 | 1 | 2 | 3 | 4 | 5 | 6 |
+----------+-----+-----+-----+-----+-----+-----+
| set | 1 | 1 | 1 | 1 | 1 | 1 |
+----------+-----+-----+-----+-----+-----+-----+
->测试销毁图： 成功！
演示结束，程序退出！
--------------------------------
Process exited with return value 0
Press any key to continue . . .
总结：
普利姆算法主要针对的是顶点，与图中的边数无关，适合求稠密网（边比较多的网）的最小生成树。
克鲁斯卡尔主要针对边，与图中顶点数无关，适合求稀疏网（边较少的网）的最小生成树
下次的文章会介绍最短路径两种算法的实现，感谢大家一直以来的关注。再见！