离散数学实验五c语言(并查集处理，Kruskal算法求最小生成树)

一、算法描述、算法思想

（一）相关数据结构

#define Totaledge 100
#define TotalNode 100
int fa[TotalNode];

定义Totaledge为初始化存边数组的大小，TotalNode为初始化存点数组的大小，fa数组存储每个点对应的集合号

typedef struct ty *E;
typedef struct ty Edge;
struct ty
{int x, y, len;
} edge[Totaledge];
struct ty2
{int x, y, len;
} ans[Totaledge];

定义ty存储每条边的信息，因为该图为一个无向图，因此x,y存储边的两点，len为该边的长度(权值)，然后edge结构体数组则存储所有边的信息。

定义ty2为最终加入最小生成树的边，ans数组存储组成最小生成树的所有边。

（二）相关算法实现

1、并查集处理

for (int i = 1; i <= TotalNode; i++)fa[i] = i;

首先先将所有点对应的集合设为自己。

int find(int x)
{return x == fa[x] ? x : find(fa[x]);
}

那么找一点对应的集合，利用路径压缩的思想。

int fx = find(x), fy = find(y);
if (fx != fy)
{fa[fx] = fy;
}

合并两点的集合，先找到两点的集合，如果不相同就进行合并。

2、Kruskal算法求最小生成树

算法思想：将所有边按照权值从小到大排序，按照该顺序挑边，若该边不会使该树变成一个回路，则将其加入最小生成树中。

（1）边排序

for (int i = 0; i < total; i++)
{int x, y, len;scanf("%d%d%d", &x, &y, &len);edge[i].x = x;edge[i].y = y;edge[i].len = len;
}
qsort(edge, total, sizeof(edge[0]), cmp);

int cmp(const void *a, const void *b) 
{Edge p1 = *(E)a;Edge p2 = *(E)b;return p1.len - p2.len; // 按照长度从小到大
}

利用可以给结构体排序的qsort函数，让其按照结构体的边从小到大排序

（2）挑边

判断加入的边是否会形成回路，看该边两点的集合是否为同一个，若为同一个就说明会形成回路，不为同一个就不会形成回路。

for (int i = 0; i < total; i++)
{int x = edge[i].x;int y = edge[i].y;int fx = find(x), fy = find(y);if (fx != fy){totalvalue += edge[i].len;ans[++cnt].x = x;ans[cnt].y = y;ans[cnt].len = edge[i].len;fa[fx] = fy;}
}

按照边长度从小到大开始加边，若该边两点的集合不为同一个，那么就将该边加入最小生成树中，totalvalue为最小生成树的权值，该权值加上该边的长度。然后ans数组中加入该边的信息，方便后序输出。

（三）流程图

1、main函数

2、find(int x)（找点所在的集合）

二、程序运行截图，及相关样例解释

根据分析，程序输出满足要求。

三、源程序

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define Totaledge 100
#define TotalNode 100
typedef struct ty *E;
typedef struct ty Edge;
struct ty
{int x, y, len;
} edge[Totaledge];
struct ty2
{int x, y, len;
} ans[Totaledge];
int fa[TotalNode];
int cmp(const void *a, const void *b) 
{Edge p1 = *(E)a;Edge p2 = *(E)b;return p1.len - p2.len; // 按照长度从小到大
}
int find(int x)
{return x == fa[x] ? x : find(fa[x]);
}
int main()
{int cnt = 0, n, total = 0, totalvalue = 0;for (int i = 1; i <= TotalNode; i++)fa[i] = i;printf("请输入结点个数:");scanf("%d", &n);printf("请输入边的个数：");scanf("%d", &total);printf("请依次输入边的信息，x, y, 长度\neg:1 2 5,表示1和2连边，长度为5\n");for (int i = 0; i < total; i++){int x, y, len;scanf("%d%d%d", &x, &y, &len);edge[i].x = x;edge[i].y = y;edge[i].len = len;}qsort(edge, total, sizeof(edge[0]), cmp);for (int i = 0; i < total; i++){int x = edge[i].x;int y = edge[i].y;int fx = find(x), fy = find(y);if (fx != fy){totalvalue += edge[i].len;ans[++cnt].x = x;ans[cnt].y = y;ans[cnt].len = edge[i].len;fa[fx] = fy;}}printf("最小生成树的权值为: ");printf("%d\n", totalvalue);printf("最小生成树中边的信息：（按照，x,y,len顺序，表示x与y连边，长度为len）\n");for (int i = 1; i <= cnt; i++)printf("%d %d %d\n", ans[i].x, ans[i].y, ans[i].len);return 0;
}