数据结构：最小生成树--Kruskal算法

╰半橙微兮° 2022-06-12 04:23 150阅读 0赞

# 数据结构：最小生成树--Kruskal算法  #

标签： [ Kruskal算法][Kruskal][图][Link 1][并查集][Link 2][kruskal][][数据结构][Link 3]

2014-08-07 11:45  2308人阅读 评论(1) 收藏 举报

![category_icon.jpg][] 分类：

数据结构与算法*（49）* ![arrow_triangle_20_down.jpg][] ![arrow_triangle_up.jpg][]

[作者同类文章][Link 4] *X*

目录(?)\[+\]

1.  Kruskal算法
2.  算法说明
3.  代码

Kruskal算法

### Kruskal算法 ###

求解最小生成树的另一种常见算法是Kruskal算法，它比[Prim算法][Prim]更直观。从直观上看，Kruskal算法的做法是：每次都从剩余边中选取权值最小的，当然，这条边不能使已有的边产生回路。

手动求解会发现Kruskal算法异常简单，下面是一个例子

![20140804235619510][]

先对边的权值排个序：1(0,1) 2(2,6) 4(1,3) 6(1,2) 8(3,6) 10(5,6) 12(3,5) 15(4,5) 20(0,1)

首选边1(0,1)、2(2,6)、4(1,3)、6(1,2)，此时的图是这样

![20140807115832258][]

![Image 1][]

显然，若选取边8(3,6)会出现环，则必须抛弃8(3,6)，选择下一条10(5,6)没有问题，此时图变成这样

![20140807115531687][]

![Image 1][]

显然，12(3,5)同样不可取，选取15(4,5)，边数已达到要求，算法结束。最终的图是这样的

![20140807115445558][]

![Image 1][]

算法逻辑人很容易理解，但用代码判断当前边是否会引起环的出现，则很棘手。

### 算法说明 ###

为了判断环的出现，我们换个角度来理解Kruskal算法的做法：初始时，把图中的n个顶点看成是独立的n个连通分量，从树的角度看，也是n个根节点。我们选边的标准是这样的：若边上的两个顶点从属于两个不同的连通分量，则此边可取，否则考察下一条权值最小的边。

于是问题又来了，如何判断两个顶点是否属于同一个连通分量呢？这个可以参照并查集的做法解决。它的思路是：如果两个顶点的根节点是一样的，则显然是属于同一个连通分量。这也同样暗示着：在加入新边时，要更新父节点。具体细节看代码：

### 代码 ###

**\[cpp\]**  view plain  copy

print ?

1.  \#include<iostream> 
2.  \#include<algorithm>
3.  using namespace std;
4.  \#define MAXWEIGHT 100
5.  /\*
6.  全局变量
7.  numV顶点数
8.  numE边数
9.  \*/
10. int numV, numE;
11. //边
12. typedef struct edge\_tag
13. \{
14. int tail;
15. int head;
16. int weight;
17. \}Edge;
18. //检测边
19. bool checkEdge(int tail, int head, int weight)
20. \{
21. if (tail == head
22. || tail < 0 || tail >= numV
23. || head < 0 || head >= numV
24. || weight <= 0 || weight >= MAXWEIGHT)
25. return false;
26. return true;
27. \}
28. //输入边
29. void inputEdge(Edge \*edge, int numE)
30. \{
31. int i, tail, head, weight;
32. cout << "输入边的起点、终点和权值" << endl;
33. i = 0;
34. while (i < numE)
35. \{
36. cin >> tail >> head >> weight;
37. while (!checkEdge(tail, head, weight))
38. \{
39. cout << "输入错误！重新输入" << endl;
40. cin >> tail >> head >> weight;
41. \}
42. edge\[i\].tail = tail;
43. edge\[i\].head = head;
44. edge\[i\].weight = weight;
45. i++;
46. \}
47. \}
48. int cmp(const void \*edge1, const void \*edge2)
49. \{
50. return ((Edge\*)edge1)->weight - ((Edge\*)edge2)->weight;
51. \}
52. 
53. //并查集的常见操作
54. /\*
55. 压缩查找
56. 查找child的根节点
57. \*/
58. int Find(int child, int \*parent)
59. \{
60. if (parent\[child\] == child)
61. return child;
62. parent\[child\] = Find(parent\[child\], parent); //压缩路径
63. return parent\[child\];
64. \}
65. //合并
66. bool Union(Edge \*e, int \*parent, int \*childs)
67. \{
68. //处于同一个棵树中，则不能合并，否则会出现环
69. int root1, root2;
70. root1 = Find(e->tail, parent);
71. root2 = Find(e->head, parent);
72. if (root1 != root2)
73. \{
74. //把小树合并到大树根下
75. if (childs\[root1\] > childs\[root2\])
76. \{
77. parent\[root2\] = root1;
78. childs\[root1\] += childs\[root2\] + 1;
79. \}
80. else
81. \{
82. parent\[root1\] = root2;
83. childs\[root2\] += childs\[root2\] + 1;
84. \}
85. return true;
86. \}
87. return false;
88. \}
89. /\*
90. Kruskal算法
91. 求最小生成树
92. \*/
93. void Kruskal(int numV, int numE)
94. \{
95. //边的集合
96. Edge \*edge = new Edge\[numE\];
97. inputEdge(edge, numE);
98. /\*
99.  parent\[i\]是顶点i的父顶点
100.  childs\[i\]是顶点i的孩子数
101.  child的复数是children，这里的childs是杜撰的
102.  \*/
103. int \*parent = new int\[numV\];
104. int \*childs = new int\[numV\];
105. //初始化
106. for (int i = 0; i < numV; i++)
107. \{
108. /\*
109.  初始时，每一个顶点都是根，且无孩子
110.  把每个顶点的的父节点设置为自身下标，也是标明类别
111.  \*/
112. parent\[i\] = i;
113. childs\[i\] = 0;
114. \}
115. //对边按权值进行从小到大排序
116. qsort(edge, numE, sizeof(Edge), cmp);
117. int i, count;
118. i = count = 0;
119. cout << "最小生成树的边..." << endl;
120. while (i < numE)
121. \{
122. if (Union(&edge\[i\], parent, childs))
123. \{
124. cout << edge\[i\].tail << "---" << edge\[i\].head << endl;
125. count++;
126. \}
127. if (count == numV - 1) //边数达到要求
128. break;
129. i++;
130. \}
131. if (count != numV - 1)
132. cout << "此图为非连通图！无法构成最小生成树。" << endl;
133. delete\[\]edge;
134. delete\[\]parent;
135. delete\[\]childs;
136. \}
137. //检测顶点数和边数
138. bool checkVE(int numV, int numE)
139. \{
140. if (numV <= 0 || numE <= 0 || numE > numV\*(numV - 1) / 2)
141. return false;
142. return true;
143. \}
144. int main()
145. \{
146. cout << "\*\*\*\*\*\*Kruskal\*\*\*by David\*\*\*" << endl;
147. cout << "输入顶点数、边数 ";
148. cin >> numV >> numE;
149. while (!checkVE(numV, numE))
150. \{
151. cout << "输入数据有问题！重新输入 ";
152. cin >> numV >> numE;
153. \}
154. cout << endl << "Kruskal..." << endl;
155. Kruskal(numV, numE);
156. system("pause");
157. return 0;
158. \}

#include<iostream> 
    #include<algorithm>
    using namespace std;
    #define MAXWEIGHT 100
    /*
    全局变量
    numV顶点数
    numE边数
    */
    int numV, numE;
    //边
    typedef struct edge_tag
    {
    	int tail;
    	int head;
    	int weight;
    }Edge;
    //检测边
    bool checkEdge(int tail, int head, int weight)
    {
    	if (tail == head
    		|| tail < 0 || tail >= numV
    		|| head < 0 || head >= numV
    		|| weight <= 0 || weight >= MAXWEIGHT)
    		return false;
    	return true;
    }
    //输入边
    void inputEdge(Edge *edge, int numE)
    {
    	int i, tail, head, weight;
    	cout << "输入边的起点、终点和权值" << endl;
    	i = 0;
    	while (i < numE)
    	{
    		cin >> tail >> head >> weight;
    		while (!checkEdge(tail, head, weight))
    		{
    			cout << "输入错误！重新输入" << endl;
    			cin >> tail >> head >> weight;
    		}
    		edge[i].tail = tail;
    		edge[i].head = head;
    		edge[i].weight = weight;
    		i++;
    	}
    }
    int cmp(const void *edge1, const void *edge2)
    {
    	return ((Edge*)edge1)->weight - ((Edge*)edge2)->weight;
    }
    
    //并查集的常见操作
    /*
    压缩查找
    查找child的根节点
    */
    int Find(int child, int *parent)
    {
    	if (parent[child] == child)
    		return child;
    	parent[child] = Find(parent[child], parent); //压缩路径
    	return parent[child];
    }
    //合并
    bool Union(Edge *e, int *parent, int *childs)
    {
    	//处于同一个棵树中，则不能合并，否则会出现环
    	int root1, root2;
    	root1 = Find(e->tail, parent);
    	root2 = Find(e->head, parent);
    	if (root1 != root2)
    	{
    		//把小树合并到大树根下
    		if (childs[root1] > childs[root2])
    		{
    			parent[root2] = root1;
    			childs[root1] += childs[root2] + 1;
    		}
    		else
    		{
    			parent[root1] = root2;
    			childs[root2] += childs[root2] + 1;
    		}
    		return true;
    	}
    	return false;
    }
    /*
    Kruskal算法
    求最小生成树
    */
    void Kruskal(int numV, int numE)
    {
    	//边的集合
    	Edge *edge = new Edge[numE];
    	inputEdge(edge, numE);
    	/*
    	parent[i]是顶点i的父顶点
    	childs[i]是顶点i的孩子数
    	child的复数是children，这里的childs是杜撰的
    	*/
    	int *parent = new int[numV];
    	int *childs = new int[numV];
    	//初始化
    	for (int i = 0; i < numV; i++)
    	{
    		/*
    		初始时，每一个顶点都是根，且无孩子
    		把每个顶点的的父节点设置为自身下标，也是标明类别
    		*/
    		parent[i] = i;
    		childs[i] = 0;
    	}
    	//对边按权值进行从小到大排序
    	qsort(edge, numE, sizeof(Edge), cmp);
    	int i, count;
    	i = count = 0;
    	cout << "最小生成树的边..." << endl;
    	while (i < numE)
    	{
    		if (Union(&edge[i], parent, childs))
    		{
    			cout << edge[i].tail << "---" << edge[i].head << endl;
    			count++;
    		}
    		if (count == numV - 1)  //边数达到要求
    			break;
    		i++;
    	}
    	if (count != numV - 1)
    		cout << "此图为非连通图！无法构成最小生成树。" << endl;
    	delete[]edge;
    	delete[]parent;
    	delete[]childs;
    }
    //检测顶点数和边数
    bool checkVE(int numV, int numE)
    {
    	if (numV <= 0 || numE <= 0 || numE > numV*(numV - 1) / 2)
    		return false;
    	return true;
    }
    int main()
    {
    	cout << "******Kruskal***by David***" << endl;
    	cout << "输入顶点数、边数 ";
    	cin >> numV >> numE;
    	while (!checkVE(numV, numE))
    	{
    		cout << "输入数据有问题！重新输入 ";
    		cin >> numV >> numE;
    	}
    	cout << endl << "Kruskal..." << endl;
    	Kruskal(numV, numE);
    	system("pause");
    	return 0;
    }

运行

![20140807113039186][]

转载请注明出处，本文地址：[http://blog.csdn.net/zhangxiangdavaid/article/details/38414683][http_blog.csdn.net_zhangxiangdavaid_article_details_38414683]

若有所帮助，顶一个哦！

专栏目录：

*  [数据结构与算法目录][Link 5]
 *  [c指针][c]

顶

踩

*  上一篇[数据结构：最小生成树--Prim算法][--Prim]
 *  下一篇[挑战面试编程：回文串、回文数字][Link 6]

####  ####

相关文章推荐

*  *•* [ 最小生成树之Kruskal算法][_Kruskal]
 *  *•* [ 图论500题][_500]
 *  *•* [ Kruskal算法（贪心+并查集=最小生成树）][Kruskal 1]
 *  *•* [ 最小生成树-Prim算法和Kruskal算法][_-Prim_Kruskal]
 *  *•* [ 最小生成树（kruskal算法，模板）oj2144][_kruskal_oj2144]

*  *•* [ Java实现最小生成树Kruskal算法][Java_Kruskal]
 *  *•* [ \[C++\]最小生成树--Prim算法&Kruskal算法][_C_--Prim_Kruskal]
 *  *•* [ 最小生成树-kruskal算法][_-kruskal]
 *  *•* [ 最小生成树(prim算法与kruskal算法)(模板)][_prim_kruskal]
 *  *•* [ 最小生成树（prime算法、kruskal算法） 和 最短路径算法（floyd、dijkstra）][_prime_kruskal_ _ _floyd_dijkstra]

[Kruskal]: http://www.csdn.net/tag/Kruskal%e7%ae%97%e6%b3%95
[Link 1]: http://www.csdn.net/tag/%e5%9b%be
[Link 2]: http://www.csdn.net/tag/%e5%b9%b6%e6%9f%a5%e9%9b%86
[kruskal]: http://www.csdn.net/tag/kruskal
[Link 3]: http://www.csdn.net/tag/%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84
[category_icon.jpg]: /images/20220612/c3f74ede1b794194b1e738a16e7eb22c.png
[arrow_triangle_20_down.jpg]: http://static.blog.csdn.net/images/arrow_triangle%20_down.jpg
[arrow_triangle_up.jpg]: /images/20220612/260e729888394cd1a06e7b51f0578372.png
[Link 4]: http://blog.csdn.net/zhangxiangDavaid/article/category/2242097
[Prim]: http://blog.csdn.net/zhangxiangdavaid/article/details/38377091
[20140804235619510]: /images/20220612/4ee082e0f1154ecc83cab26eed2336dc.png
[20140807115832258]: /images/20220612/752cc43245e0405abc447aa6bbedb15d.png
[Image 1]: 
[20140807115531687]: /images/20220612/5e9cdf018f7048f38ca06bbf7ca3d6fc.png
[20140807115445558]: /images/20220612/97ac8553af3845029e27e59d0a05bdcb.png
[20140807113039186]: /images/20220612/ac68302e6df9419f94c5fc49a90e60b6.png
[http_blog.csdn.net_zhangxiangdavaid_article_details_38414683]: http://blog.csdn.net/zhangxiangdavaid/article/details/38414683
[Link 5]: http://blog.csdn.net/zhangxiangdavaid/article/details/25082013
[c]: http://blog.csdn.net/zhangxiangdavaid/article/details/37885275#t1
[--Prim]: http://blog.csdn.net/zhangxiangDavaid/article/details/38377091
[Link 6]: http://blog.csdn.net/zhangxiangDavaid/article/details/38467195
[_Kruskal]: http://blog.csdn.net/luomingjun12315/article/details/47700237
[_500]: http://blog.csdn.net/luomingjun12315/article/details/47438607
[Kruskal 1]: http://blog.csdn.net/liangzhaoyang1/article/details/51169090
[_-Prim_Kruskal]: http://blog.csdn.net/gettogetto/article/details/53216951
[_kruskal_oj2144]: http://blog.csdn.net/qz13110802018/article/details/38872071
[Java_Kruskal]: http://blog.csdn.net/mengxiangyue/article/details/7052066
[_C_--Prim_Kruskal]: http://blog.csdn.net/stary_yan/article/details/51427864
[_-kruskal]: http://blog.csdn.net/turingwy/article/details/50698407
[_prim_kruskal]: http://blog.csdn.net/zwj1452267376/article/details/47603933
[_prime_kruskal_ _ _floyd_dijkstra]: http://blog.csdn.net/hurmishine/article/details/51244216