文章作者:Slyar 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。
今天数据结构课讲了最小生成树的Kruskal算法和Prim算法,不过都只是概念,可能是怕他们听不懂吧,反正算法实现一概不讲...囧
下午抱着《算法导论》跑去图书馆看Kruskal算法,发现《算法导论》真的是牛XXXX的书啊,看完之后豁然开朗,而且惊讶地发现Kruskal算法居然用到了前两天研究的并查集,爽歪歪了...
Kruskal比较适用于稀疏图,是一种贪心算法:为使生成树上边的权值和最小,则应使生成树中每一条边的权值尽可能地小。
具体做法:找出森林中连接任意两棵树的所有边中,具有最小权值的边,如果将它加入生成树中不产生回路,则它就是生成树中的一条边。这里的关键就是如何判断"将它加入生成树中不产生回路"。
《算法导论》提供的一种方法是采用一种"不相交集合数据结构",也就是并查集了。具体的实现看代码好了,反正核心内容就是如果某两个节点属于同一棵树(Find_Set),那么将它们合并(Union)后一定会形成回路。
编写程序:对于如下一个带权无向图,给出所有边以及权值,用kruskal算法求最小生成树。
输入数据:
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
输出:
A - D : 5
C - E : 5
D - F : 6
A - B : 7
B - E : 7
E - G : 9
Total:39
代码如下,其实代码可以优化的地方很多,例如当生成树的边数已经等于n-1时即可停止循环...因为不是ACM题,故优化省略不写,只当做算法学习...
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 <stdlib.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;
/* 读取边的数目 */
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;
}
|
分享到:
相关推荐
最小生成树kruskal算法并查集版 C语言实现 - Slyar Home
最小生成树kruskal算法并查集版+C语言实现
编写算法能够建立带权图,并能够用Kruskal算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。
图论算法:最小生成树——Prim算法和Kruskal算法C 实现
该程序是我写的博客“一起talk C栗子吧(第五十回:C语言实例--最小生成树二)”的配套程序,共享给大家使用
详细的c语言实现最小生成树的prim算法和kruskal算法,非常有用的
在贪婪算法这一章提到了最小生成树的一些算法,首先是Kruskal算法,实现如下: MST.h 代码如下:#ifndef H_MST#define H_MST #define NODE node *#define G graph *#define MST edge ** /* the undirect graph start...
求最小生成树的避圈法之一——克鲁斯卡尔算法
克鲁斯卡下面答卷分别就课程的销售预测、市场满意度指标、市场占有率指标、计划准确度指标,展开讨论。 尔最小生成树的C语言算法
问题描述:给定一个地区的n个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并计算得到的最小生成树的代价。 基本要求: 1.城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本中给出的...
数据结构,最小生成树克鲁斯卡尔算法的实现.pdf
用C语言实现的prim和kruskal最小生成树算法
最小生成树 最小生成树(minimum spanning tree)是由n个顶点,n-1条边,将一个连通图连接起来,且使权值最小的结构。 最小生成树可以用Prim(普里姆)算法或kruskal(克鲁斯卡尔)算法求出。 我们将以下面的带权...
利用Kruskal算法,用C语言编写出给定无向连通加权图G,构造一棵最小生成树的程序。
5.2 最小生成树: Kruskal算法:每次取当前最小权值的边,如果这条边连接的两个节点不在同一个连通分量中,则添加到最小生成树中,直到所有顶点被覆盖。 Prim算法:从任意根顶点开始,每次取到树中任意一个顶点权值...
C数据结构课的一个实验,用Prim算法和Kruskal算法实现最小生成树,
C语言 Prim Kruskal 算法求最小生成树
Kruskal算法是数据结构中求图的最小生成树的一个经典算法,也是数据结构课程设计的重点,这里把自己的一点工作分享给大家交流参考,希望能够造福后来者
最小生成树c语言实现,采用Kruskal算法。