克鲁斯卡尔算法的构造解释及代码编写
一，大致的遍历过程图解及过程讲解
总连通网如右下角所示。
从所有权值中找到最小值，若不连通，则添加该边无回路则正确
1，如下图（a），先找到最小边AC,加入；
2，图（b），找到下一个最小边DF，加入；
3，图（c），图（d），按照大小排序，一次找到BE，CF加入；
4，图（e），因为有三个边的长度都为5，但是由图可知，当AD或者CD加入时，都会产生回路，而BC正好合适，所以BC加入
二，实现方法
第一步：构造邻接矩阵，只不过这保存方法与前面不同.
只需要构造一个能够保存每条边起点Head终点Tail和权值lowcost的结构体数组。
第二步：将上面构造的结构体数组进行从小到大排序。
本文代码运用的是归并排序https://blog.****.net/qq_46423166/article/details/105493704
也可以用冒泡排序，插入排序，选择排序，快速排序都等可以，可以看以往博客。
但是这里注意交换值的时候一次要交换结构体里面的所有值。我这里一次就要交换Head，Tailm，lowcast三个的值
eg： S1[k].lowcost = S[i].lowcost;
S1[k].Head = S[i].Head;
S1[k].Tail = S[i].Tail;（将S[i]的值赋给S1[k]）
第三步：进行克鲁斯卡尔算法
即再将上面排序好的结构体数组进行遍历，符合要求即输出。
此时需要判断的就是加入某一边，是否会产生环，所以加入一个新的数组Vexset[ ]，每个顶点一个数组位置；
刚开始数组都赋值为本身，即自身和自身相连，假设当n点可以连接m时，将Vexset[n]=m（最后产生的结果就是，一条连通的边上，每个顶点的Vexset值都一样），此时若新加入的顶点的Vexset与将要加入的连通边相同，则判断错误，不能加入。
eg：如下图运行截图表现出的数组Vexset的值
0 1 2 3 4 5（最开始赋值，每个顶点连接自己）
0 1 0 3 4 5（AC连接，所以将C的值变成0）
0 1 0 3 4 3（DF连接，所以将F的值变成3）
0 1 0 3 1 3（BE连接，所以将E的值变为1）
0 1 0 0 1 0（CF连接，所以此时ACFD成为连通边，所以都变成一样的值（用的循环判断赋值），，所以ACDF都变为0）
下面多出来的一次0 1 0 0 1 0，是因为出现了边的连通情况，若这一步时AD因为AD的Vexset都为0，所以不能连通。
最后加入BE边，此时六个点全部连通，所以值都变成1（可能此处赋值是按照BE连通边的值进行赋值，不是用ACDF赋值）
运行截图：
代码：
#include<iostream>
#include<stdlib.h>
using namespace std;
#define pointMax 30
#define cloEdge 30
struct Node
{
char Head; //边的始点
char Tail; //边的终点
int lowcost; //权值
};
int Vexset[cloEdge];
struct AMgroup
{
char VTchart[pointMax]; //顶点表
int point, vert; //点，边
};
int AMlocate(AMgroup &Map, char x) //找到某一顶点的位置
{
for (int i = 0; i < Map.point; i++)
{
if (Map.VTchart[i] == x)
{
return i;
break;
}
}
cout << "error；";
return -1;
}
//邻接矩阵创造，以及边的赋值
void CreatAM(Node *S, AMgroup &Map) //构造邻接矩阵
{
cout << "输入邻接矩阵顶点数：";
cin >> Map.point;
cout << "输入邻接矩阵边数：";
cin >> Map.vert;
getchar();
char a[100];
cout << "输入点的信息：";
gets_s(a);
for (int i = 0; i < Map.point; i++) //依次输入点的信息
{
Map.VTchart[i] = a[i];
}
char v1, v2; int len;
for (int i = 0; i < Map.vert; i++) //构造邻接矩阵的各个边存储到Node结构体里面
{
cout << "输入第" << i + 1 << "条边的两个顶点以及权值：";
cin >> v1 >> v2 >> len;
int m, n;
m = AMlocate(Map, v1);
n = AMlocate(Map, v2);
S[i].Head = v1;
S[i].Tail = v2;
S[i].lowcost = len;
}
cout << "当前所有权情况：" << endl;
for (int i = 0; i < Map.vert; i++)
{
cout << S[i].Head << "--" << S[i].Tail << " " << S[i].lowcost << endl;
}
cout << endl;
}
//合并过程（治的过程） //归并排序过程
void Merge(Node *S, Node *S1, int start, int mid, int end)
{
int i = start, j = mid + 1, k = start;
while (i != mid + 1 && j != end + 1)
{
if (S[i].lowcost > S[j].lowcost)
{
S1[k].lowcost = S[j].lowcost;
S1[k].Head = S[j].Head;
S1[k].Tail = S[j].Tail;
k++; j++;
}
else
{
S1[k].lowcost = S[i].lowcost;
S1[k].Head = S[i].Head;
S1[k].Tail = S[i].Tail;
k++; i++;
}
}
while (i != mid + 1)
{
S1[k].lowcost = S[i].lowcost;
S1[k].Head = S[i].Head;
S1[k].Tail = S[i].Tail;
k++; i++;
}
while (j != end + 1)
{
S1[k].lowcost = S[j].lowcost;
S1[k].Head = S[j].Head;
S1[k].Tail = S[j].Tail;
k++; j++;
}
for (i = start; i <= end; i++)
{
S[i].lowcost = S1[i].lowcost;
S[i].Head = S1[i].Head;
S[i].Tail = S1[i].Tail;
}
}
//递归部分（分的部分） //归并排序过程
void MergeSort(Node *S, Node *S1, int start, int end)
{
int mid;
if (start < end)
{
mid = start + (end - start) / 2;
MergeSort(S, S1, start, mid);
MergeSort(S, S1, mid + 1, end);
Merge(S, S1, start, mid, end);
}
}
void Sort(Node *S, AMgroup &Map) //将数组中的权值排序
{
struct Node S1[30];
MergeSort(S, S1, 0, Map.vert - 1);
}
void MST_Kruskal(struct AMgroup &Map, struct Node *S) //克鲁斯卡算法
{
int v1, v2;
int vs1, vs2;
Sort(S, Map); //将元素按权值从小到大排序
cout << "排序后权值：" << endl;
for (int i = 0; i < Map.vert; i++)
{
cout << S[i].Head << "--";
cout << S[i].Tail << " ";
cout << S[i].lowcost << endl;
}
cout << endl;
for (int i = 0; i < Map.point; i++) //将所有顶点的Vexset赋值为本身
{
Vexset[i] = i;
}
for (int i = 0; i < Map.vert; i++) //遍历所有边
{
for (int p = 0; p < Map.point; p++)
{
cout << Vexset[p] << " ";
}
cout << endl;
v1 = AMlocate(Map, S[i].Head); //找到最小边的两个顶点
v2 = AMlocate(Map, S[i].Tail);
vs1 = Vexset[v1]; //两个顶点的Vexset值
vs2 = Vexset[v2];
if (vs1 != vs2) //如果不等代表不连通
{
cout << S[i].Head << "->" << S[i].Tail << endl;
for (int j = 0; j < Map.vert; j++) //通过遍历将将要加入的所有顶点都赋值为一样
{
if (Vexset[j] == vs2)
{
Vexset[j] = vs1;
}
}
}
}
}
int main()
{
struct AMgroup Jzhen[30]; //邻接矩阵
struct Node Szu[30]; //边的数组
CreatAM(Szu, *Jzhen);
MST_Kruskal(*Jzhen, Szu);
system("pause");
return 0;
}