贪心算法(Greedy Algorithm)之最小生成树 克鲁斯卡尔算法(Kruskal's algorithm)

克鲁斯卡尔算法(Kruskal's algorithm)是两个经典的最小生成树算法的较为简单理解的一个。这里面充分体现了贪心算法的精髓。大致的流程可以用一个图来表示。这里的图的选择借用了Wikipedia上的那个。非常清晰且直观。

首先第一步，我们有一张图，有若干点和边

如下图所示：

第一步我们要做的事情就是将所有的边的长度排序，用排序的结果作为我们选择边的依据。这里再次体现了贪心算法的思想。资源排序，对局部最优的资源进行选择。

排序完成后，我们率先选择了边AD。 这样我们的图就变成了

第二步，在剩下的变中寻找。我们找到了CE。这里边的权重也是5

依次类推我们找到了6,7,7。完成之后，图变成了这个样子。

下一步就是关键了。下面选择那条边呢？ BC或者EF吗？都不是，尽管现在长度为8的边是最小的未选择的边。但是现在他们已经连通了（对于BC可以通过CE,EB来连接，类似的EF可以通过EB, BA, AD, DF来接连）。所以我们不需要选择他们。类似的BD也已经连通了（这里的连通线用红色表示了）。所以最后就剩下EG和FG了。当然我们选择了EG。 最后成功的图就是下图：

到这里所有的边点都已经连通了，一个最小生成树构建完成。

如果要简要得描述这个算法的话就是，首先边的权重排序。（从小到大）循环的判断是否需要选择这里的边。判断的依据则是边的两个顶点是否已经连通，如果连通则继续下一条。不连通就选择使其连通。这个流程还是非常清晰明了。

但是在实现的时候，困难的地方在于如何描述2个点已然连通？ 这里用到了并查集做辅助，至于并查集可以到这里去看看。

这里贴出并查集的代码和Kruscal的C++实现：

[cpp] view plaincopyprint?

1. /*
2. *
3. * Disjoint_Set_Forest.h -- an implementation for disjoint set data structure
4. *
5. * Created by Ge Chunyuan on 04/09/2009.
6. *
7. * version: 0.1
8. */
9. #pragma once
10. #ifndef _DISJOINT_SET_H_
11. #define _DISJOINT_SET_H_
12. #include <vector>
13. template <typename T> class DisjointSet
14. {
15. public:
16. DisjointSet();
17. ~DisjointSet();
18. void makeSet ( const std::vector<T>& s );
19. bool findSet ( const T& s, T& parent);
20. void Union ( const T& s1, const T& s2 );
21. protected:
22. struct Node
23. {
24. int rank;
25. T data;
26. Node* parent;
27. };
28. int m_nElementCnt;
29. int m_nSetCnt;
30. std::vector<Node*> m_Nodes;
31. };
32. template< class T> DisjointSet<T>::DisjointSet()
33. {
34. m_nElementCnt = 0;
35. m_nSetCnt = 0;
36. }
37. template< class T> DisjointSet<T>::~DisjointSet()
38. {
39. for (int i=0;i<m_nElementCnt;i++)
40. delete m_Nodes[i];
41. }
42. template< class T> void DisjointSet<T>::makeSet( const std::vector<T>& s )
43. {
44. m_nElementCnt += (int)s.size();
45. m_nSetCnt += (int)s.size();
46. std::vector<T>::const_iterator it = s.begin();
47. for (;it != s.end(); ++ it)
48. {
49. Node* pNode = new Node;
50. pNode->data = *it;
51. pNode->parent = NULL;
52. pNode->rank = 0;
53. m_Nodes.push_back(pNode);
54. }
55. }
56. template< class T> bool DisjointSet<T>::findSet( const T& s, T& parent)
57. {
59. Node* curNode = NULL;
60. bool find =false;
61. for (int i=0;i<(int)m_Nodes.size();i++)
62. {
63. curNode = m_Nodes[i];
64. if (curNode->data == s)
65. {
66. find = true;
67. break;
68. }
69. }
71. if (!find) return false;
73. // find the root
74. Node* pRoot = curNode;
75. while (pRoot->parent != NULL)
76. {
77. pRoot = pRoot->parent;
78. }
80. // update all curNode's parent to root
81. while (curNode != pRoot)
82. {
83. Node* pNext = curNode->parent;
84. curNode->parent = pRoot;
85. curNode = pNext;
86. }
87. parent = pRoot->data;
88. return true;
89. }
90. template< class T> void DisjointSet<T>::Union( const T& s1, const T& s2 )
91. {
92. Node* pNode1 = NULL;
93. Node* pNode2 = NULL;
94. int find = 0;
95. for (int i=0;i<(int)m_Nodes.size();++i)
96. {
97. if (m_Nodes[i]->data == s1 || m_Nodes[i]->data == s2 )
98. {
99. find ++;
100. if (m_Nodes[i]->data == s1)
101. pNode1 = m_Nodes[i];
102. else
103. pNode2 = m_Nodes[i];
104. }
105. }
106. // not found
107. if ( find != 2) return ;
109. if (pNode1->rank > pNode2->rank)
110. pNode2->parent = pNode1;
111. else if (pNode1->rank < pNode2->rank)
112. pNode1->parent = pNode2;
113. else
114. {
115. pNode2->parent = pNode1;
116. ++ pNode1->rank;
117. }
118. --m_nSetCnt;
119. }
120. #endif //_DISJOINT_SET_H_

[cpp] view plaincopyprint?

1. // Kruscal_Algorithm.cpp : Defines the entry point for the console application.
2. //
3. #include "stdafx.h"
4. #include <string>
5. #include <vector>
6. #include <algorithm>
7. #include <iostream>
8. #include "Disjoint_Set_Forest.h"
9. struct Vertex
10. {
11. Vertex () { }
12. Vertex (std::string n)
13. {
14. name = n;
15. }
17. bool operator==(const Vertex& rhs)
18. {
19. return name == rhs.name;
20. }
21. bool operator!=(const Vertex& rhs)
22. {
23. return name != rhs.name;
24. }
25. std::string name;
26. };
27. struct Edge
28. {
29. Edge () {}
30. Edge (Vertex v1, Vertex v2, int w)
31. {
32. this->v1 = v1;
33. this->v2 = v2;
34. this->w = w;
35. }
37. Vertex v1;
38. Vertex v2;
39. int w;
40. };
41. struct EdgeSort
42. {
43. bool operator()(const Edge& e1, const Edge& e2)
44. {
45. return e1.w<e2.w;
46. }
47. };
48. struct PrintEdge
49. {
50. void operator() (Edge e)
51. {
52. std::cout<< "edge start from "<<e.v1.name <<" to "<<e.v2.name << " with length = "<<e.w <<std::endl;;
53. }
54. };
55. class Graph
56. {
57. public:
58. void appendVertex ( const Vertex& v1)
59. {
60. m_vertexs.push_back(v1);
61. }
63. void appendEdge ( const Vertex& v1, const Vertex& v2, int w)
64. {
65. m_edges.push_back( Edge(v1,v2,w) );
66. }
67. void minimumSpanningKruskal ()
68. {
69. std::vector<Edge> result;
70. std::sort (m_edges.begin(), m_edges.end(), EdgeSort());
72. DisjointSet<Vertex> dv;
73. dv.makeSet(m_vertexs);
74. std::vector<Edge>::iterator it = m_edges.begin();
75. for (;it!= m_edges.end();++it)
76. {
77. Vertex p1;
78. Vertex p2;
79. bool b1 = dv.findSet(it->v1, p1 );
80. bool b2 = dv.findSet(it->v2, p2 );
81. if ( b1&& b2 && (p1 != p2))
82. {
83. dv.Union(p1, p2);
84. result.push_back(*it);
85. }
86. }
87. for_each(result.begin(), result.end(), PrintEdge());
88. }
89. protected:
90. std::vector<Vertex> m_vertexs;
91. std::vector<Edge> m_edges;
92. };
93. int _tmain(int argc, _TCHAR* argv[])
94. {
95. Graph gr;
96. Vertex a("A");
97. Vertex b("B");
98. Vertex c("C");
99. Vertex d("D");
100. Vertex e("E");
101. Vertex f("F");
102. Vertex g("G");
104. gr.appendVertex(a);
105. gr.appendVertex(b);
106. gr.appendVertex(c);
107. gr.appendVertex(d);
108. gr.appendVertex(e);
109. gr.appendVertex(f);
110. gr.appendVertex(g);
112. gr.appendEdge(a,b,7);
113. gr.appendEdge(a,d,5);
114. gr.appendEdge(b,c,8);
115. gr.appendEdge(b,d,9);
116. gr.appendEdge(b,e,7);
117. gr.appendEdge(c,e,5);
118. gr.appendEdge(d,e,15);
119. gr.appendEdge(d,f,6);
120. gr.appendEdge(e,f,8);
121. gr.appendEdge(e,g,9);
122. gr.appendEdge(f,g,11);
123. gr.minimumSpanningKruskal();
124. system("pause");
125. return 0;
126. }