Kruskal算法的C语言实现（并查集版）

Kruskal算法求加权连通图的最小生成树的算法。kruskal算法总共选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。

首先，文章不是LZ写的，在网上看到比我写的更好的，直接拿过来了。编写程序：对于如下一个带权无向图，给出所有边以及权值，用kruskal算法求最小生成树。样例输入:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


11
A B 7
A D 5
B C 8
B D 9
B E 7
C E 5
D E 15
D F 6
E F 8
E G 9
F G 11

样例输出:

1
2
3
4
5
6
7


A - D : 5
C - E : 5
D - F : 6
A - B : 7
B - E : 7
E - G : 9
Total:39

代码如下：

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108


#include <stdio.h>
#include <string.h>
#define MAX 100

/* 定义边(x,y)，权为w */
typedef struct
{
	int x, y;
	int w;
}edge;
 
edge e[MAX];
/* rank[x]表示x的秩 */
int rank[MAX];
/* father[x]表示x的父节点 */
int father[MAX];
int sum;
 
/* 比较函数，按权值(相同则按x坐标)非降序排序 */
int cmp(const void *a, const void *b)
{
	if ((*(edge *)a).w == (*(edge *)b).w)
	{
		return (*(edge *)a).x - (*(edge *)b).x;
	}
	return (*(edge *)a).w - (*(edge *)b).w;
}
 
/* 初始化集合 */
void Make_Set(int x)
{
	father[x] = x;
	rank[x] = 0;
}
 
/* 查找x元素所在的集合,回溯时压缩路径 */
int Find_Set(int x)
{
	if (x != father[x])
	{
		father[x] = Find_Set(father[x]);
	}
	return father[x];
}
 
/* 合并x,y所在的集合 */
void Union(int x, int y, int w)
{
 
	if (x == y) return;
	/* 将秩较小的树连接到秩较大的树后 */
	if (rank[x] > rank[y])
	{
		father[y] = x;
	}
	else
	{
		if (rank[x] == rank[y])
		{
			rank[y]++;
		}
		father[x] = y;
	}
	sum += w;
}
 
/* 主函数 */
int main()
{
	int i, n;.
	int x, y;
	char chx, chy;
	//freopen("kruskal.in", "r",stdin);
	//freopen("kruskal.out", "w", stdout);
	/* 读取边的数目 */
	scanf("%d", &n);
	getchar();
 
	/* 读取边信息并初始化集合 */
	for (i = 0; i < n; i++)
	{
		scanf("%c %c %d", &chx, &chy, &e[i].w);
		getchar();
		e[i].x = chx - 'A';
		e[i].y = chy - 'A';
		Make_Set(i);
	}
 
	/* 将边排序 */
	qsort(e, n, sizeof(edge), cmp);
 
	sum = 0;
 
	for (i = 0; i < n; i++)
	{
		x = Find_Set(e[i].x);
		y = Find_Set(e[i].y);
		if (x != y)
		{
			printf("%c - %c : %d\n", e[i].x + 'A', e[i].y + 'A', e[i].w);
			Union(x, y, e[i].w);
		}
	}
 
	printf("Total:%d\n", sum);
	//system("pause");
	return 0;	
}

文章作者：姜南(Slyar) 文章来源：Slyar Home