[数据结构]图krusakl算法实现

---

Kruskal算法

我们要在连通图中去找生成树
连通图：在无向图中，若从顶点v1到顶点v2有路径，则称顶点v1与顶点v2是连通的。如果图中恣意一对顶点都是连通的，则称此图为连通图。
生成树：一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边。也就是用最少的边（n-1条边）连通起来。
最小生成树：构成生成树的这些边加起来权值最小，也就是最小的成本让这N个顶点连通，最小生成树不唯一。
连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从此中删去任何一条边，生成树就不在连通；反之，在此中引入任何一条新边，都会形成一条回路。
若连通图由n个顶点构成，则其生成树必含n个顶点和n-1条边。因此构造最小生成树的准则有三条：

• 只能利用图中的权值最小的边来构造最小生成树
  
• 只能利用恰恰n-1条边来连接图中的n个顶点
  
• 选用的n-1条边不能构成回路
  

构造最小生成树的方法：Kruskal算法和Prim算法。这两个算法都接纳了逐步求解的贪婪策略。
贪婪算法：是指在问题求解时，总是做出当前看起来最好的选择。也就是说贪婪算法做出的不是团体最优的的选择，而是某种意义上的局部最优解。贪婪算法不是对全部的问题都能得到团体最优解。
Kruskal算法和Prim算法求出来的肯定是最优解吗？——不肯定

因此要选出最小的边，然后举行连接
在这里判定是否成环的关键是并查集
代码实现：

1. W Kruskal(Self& minTree)
2. {
3.         minTree._vertexs = _vertexs;
4.         minTree._indexMap = _indexMap;
5.         minTree._matrix.resize(_vertexs.size());
6.         for (auto& e : minTree._matrix)
7.         {
8.                 e.resize(_vertexs.size(), MAX_W);
9.         }
12.         // 先根据边的权值进行排序
13.         priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
14.         for (size_t i = 0; i < _vertexs.size(); ++i)
15.         {
16.                 for (size_t j = 0; j < _vertexs.size(); ++j)
17.                 {
18.                         if (i < j && _matrix[i][j] != MAX_W)
19.                         {
20.                                 // pq.push(_matrix[i][j]); 不是这样
21.                                 pq.push(Edge(i, j, _matrix[i][j]));
22.                         }
23.                 }
24.         }
25.         W total = W();
26.         size_t i = 1; // 最初有一个顶点
27.         // 从最小的边开始进行选择（贪心）
28.         UnionFindSet ufs(_vertexs.size());
29.         while (i < _vertexs.size() && !pq.empty())
30.         {
31.                 Edge min = pq.top();
32.                 pq.pop();
34.                 // 判断是否会构成一个回路，不会则添加到最小生成树中
35.                 if (ufs.FindRoot(min._srci) != ufs.FindRoot(min._dsti))
36.                 {
37.                         cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] << ":" << _matrix[min._srci][min._dsti] << endl;
38.                         minTree._AddEdge(min._srci, min._dsti, min._w);
39.                         total += min._w;
40.                         ufs.Union(min._srci, min._dsti);
41.                         ++i;
42.                 }
43.         }
44.         if (i == _vertexs.size())
45.         {
46.                 return total;
47.         }
48.         else
49.         {
50.                 return W();
51.         }
52. }

复制代码

完整代码：

1. namespace matrix // 领接矩阵存储
2. {
3.         template <class V, class W, W MAX_W = INT_MAX, bool Direction = false> // Vertex, Weight, Direction表示有向图还是无向图
4.         class Graph
5.         {
6.                 typedef Graph<V, W, MAX_W, Direction> Self; // 表示子图
7.         public:
8.                 Graph()
9.                 {}
11.                 Graph(const V* vertex, size_t n)
12.                 {
13.                         _vertexs.reserve(n);
14.                         for (size_t i = 0; i < n; ++i)
15.                         {
16.                                 _vertexs.push_back(vertex[i]);
17.                                 _indexMap[vertex[i]] = i; // map<V, int>second存的是对应的编号
18.                         }
20.                         _matrix.resize(n);
21.                         for (int i = 0; i < n; ++i)
22.                         {
23.                                 _matrix[i].resize(n, MAX_W);
24.                         }
25.                 }
26.                
27.                 size_t GetVertexIndex(const V& v)
28.                 {
29.                         auto ret = _indexMap.find(v);
30.                         if (ret != _indexMap.end())
31.                         {
32.                                 return ret->second;
33.                         }
34.                         else
35.                         {
36.                                 assert(false);
37.                                 return -1;
38.                         }
39.                 }
41.                 void AddEdge(const V& src, const V& dst, const W& w)
42.                 {
43.                         size_t srci = GetVertexIndex(src);
44.                         size_t dsti = GetVertexIndex(dst);
45.                         _AddEdge(srci, dsti, w);
46.                 }
47.                
48.                 void _AddEdge(size_t srci, size_t dsti, const W& w)
49.                 {
50.                         _matrix[srci][dsti] = w;
51.                         if (Direction == false)
52.                         {
53.                                 _matrix[dsti][srci] = w;
54.                         }
55.                 }
57.                 void Print()
58.                 {
59.                         // 顶点
60.                         for (size_t i = 0; i < _vertexs.size(); ++i)
61.                         {
62.                                 cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
63.                         }
64.                         cout << endl;
66.                         // 矩阵
67.                         // 横下标
68.                         cout << "  ";
69.                         for (size_t i = 0; i < _vertexs.size(); ++i)
70.                         {
71.                                 //cout << i << " ";
72.                                 printf("%4d", i);
73.                         }
74.                         cout << endl;
76.                         for (size_t i = 0; i < _matrix.size(); ++i)
77.                         {
78.                                 cout << i << " "; // 竖下标
79.                                 for (size_t j = 0; j < _matrix[i].size(); ++j)
80.                                 {
81.                                         //cout << _matrix[i][j] << " ";
82.                                         if (_matrix[i][j] == MAX_W)
83.                                         {
84.                                                 //cout << "* ";
85.                                                 printf("%4c", '*');
86.                                         }
87.                                         else
88.                                         {
89.                                                 //cout << _matrix[i][j] << " ";
90.                                                 printf("%4d", _matrix[i][j]);
91.                                         }
92.                                 }
93.                                 cout << endl;
94.                         }
95.                         cout << endl;
96.                 }
98.                 void BFS(const V& src)
99.                 {
100.                         size_t srci = GetVertexIndex(src);
102.                         // 队列和标记数组
103.                         queue<int> q;
104.                         vector<bool> visited(_vertexs.size(), false); // 标记数组
105.                         int levelSize = 1; // 保证一层 一层的打印
106.                         q.push(srci);
107.                         visited[srci] = true;
109.                         size_t n = _vertexs.size();
110.                         while (!q.empty())
111.                         {
112.                                 for (int i = 0; i < levelSize; ++i)
113.                                 {
114.                                         int front = q.front();
115.                                         q.pop();
116.                                         cout << front << ":" << _vertexs[front] << " ";
117.                                         // 把front顶点的邻接顶点入队列
118.                                         for (size_t i = 0; i < n; ++i)
119.                                         {
120.                                                 if (_matrix[front][i] != MAX_W) // 不是无穷大就是相连的
121.                                                 {
122.                                                         if (visited[i] == false)
123.                                                         {
124.                                                                 q.push(i);
125.                                                                 visited[i] = true;
126.                                                         }
127.                                                 }
128.                                         }
129.                                 }
130.                                 cout << endl;
131.                                 levelSize = q.size(); // 下一层的数据个数
132.                         }
133.                         cout << endl;
134.                 }
136.                 void _DFS(size_t srci, vector<bool> visited)
137.                 {
138.                         cout << srci << ":" << _vertexs[srci] << endl;
139.                         visited[srci] = true;
140.                         // 找srci相邻的没有访问过的点，深度遍历
141.                         for (size_t i = 0; i < _vertexs.size(); ++i)
142.                         {
143.                                 if (_matrix[srci][i] != MAX_W && visited[i] = false)
144.                                 {
145.                                         _DFS(i, visited);
146.                                 }
147.                         }
148.                 }
150.                 void DFS(const V& src)
151.                 {
152.                         size_t srci = GetVertexIndex(src);
153.                         vector<bool> visited(_vertexs.size(), false);
154.                         _DFS(srci, visited);
155.                 }
157.                 struct Edge
158.                 {
159.                         size_t _srci;
160.                         size_t _dsti;
161.                         W _w;
163.                         Edge(size_t srci, size_t dsti, const W& w)
164.                                 : _srci(srci)
165.                                 , _dsti(dsti)
166.                                 , _w(w)
167.                         {}
169.                         bool operator>(const Edge& e) const
170.                         {
171.                                 return _w > e._w;
172.                         }
173.                 };
175.                 W Kruskal(Self& minTree)
176.                 {
177.                         minTree._vertexs = _vertexs;
178.                         minTree._indexMap = _indexMap;
179.                         minTree._matrix.resize(_vertexs.size());
180.                         for (auto& e : minTree._matrix)
181.                         {
182.                                 e.resize(_vertexs.size(), MAX_W);
183.                         }
186.                         // 先根据边的权值进行排序
187.                         priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
188.                         for (size_t i = 0; i < _vertexs.size(); ++i)
189.                         {
190.                                 for (size_t j = 0; j < _vertexs.size(); ++j)
191.                                 {
192.                                         if (i < j && _matrix[i][j] != MAX_W)
193.                                         {
194.                                                 // pq.push(_matrix[i][j]); 不是这样
195.                                                 pq.push(Edge(i, j, _matrix[i][j]));
196.                                         }
197.                                 }
198.                         }
199.                         W total = W();
200.                         size_t i = 1; // 最初有一个顶点
201.                         // 从最小的边开始进行选择（贪心）
202.                         UnionFindSet ufs(_vertexs.size());
203.                         while (i < _vertexs.size() && !pq.empty())
204.                         {
205.                                 Edge min = pq.top();
206.                                 pq.pop();
208.                                 // 判断是否会构成一个回路，不会则添加到最小生成树中
209.                                 if (ufs.FindRoot(min._srci) != ufs.FindRoot(min._dsti))
210.                                 {
211.                                         cout << _vertexs[min._srci] << "-" << _vertexs[min._dsti] << ":" << _matrix[min._srci][min._dsti] << endl;
212.                                         minTree._AddEdge(min._srci, min._dsti, min._w);
213.                                         total += min._w;
214.                                         ufs.Union(min._srci, min._dsti);
215.                                         ++i;
216.                                 }
217.                         }
218.                         if (i == _vertexs.size())
219.                         {
220.                                 return total;
221.                         }
222.                         else
223.                         {
224.                                 return W();
225.                         }
226.                 }
228.         private:
229.                 vector<V> _vertexs; // 顶点集合
230.                 map<V, int> _indexMap; // 顶点映射下标
231.                 vector<vector<W>> _matrix;// 存储边的关系
232.         };
234.         void TestGraph()
235.         {
236.                 Graph<char, int, INT_MAX, true> g("0123", 4);
237.                 g.AddEdge('0', '1', 1);
238.                 g.AddEdge('0', '3', 4);
239.                 g.AddEdge('1', '3', 2);
240.                 g.AddEdge('1', '2', 9);
241.                 g.AddEdge('2', '3', 8);
242.                 g.AddEdge('2', '1', 5);
243.                 g.AddEdge('2', '0', 3);
244.                 g.AddEdge('3', '2', 6);
245.                 g.Print();
246.         }
248.         void TestBDFS()
249.         {
250.                 string a[] = { "张三", "李四", "王五", "赵六", "周七" };
251.                 Graph<string, int> g1(a, sizeof(a) / sizeof(string));
252.                 g1.AddEdge("张三", "李四", 100);
253.                 g1.AddEdge("张三", "王五", 200);
254.                 g1.AddEdge("王五", "赵六", 30);
255.                 g1.AddEdge("王五", "周七", 30);
256.                 g1.Print();
258.                 g1.BFS("张三");
259.         }
261.         void TestGraphMinTree()
262.         {
263.                 const char* str = "abcdefghi";
264.                 Graph<char, int> g(str, strlen(str));
265.                 g.AddEdge('a', 'b', 4);
266.                 g.AddEdge('a', 'h', 8);
267.                 //g.AddEdge('a', 'h', 9);
268.                 g.AddEdge('b', 'c', 8);
269.                 g.AddEdge('b', 'h', 11);
270.                 g.AddEdge('c', 'i', 2);
271.                 g.AddEdge('c', 'f', 4);
272.                 g.AddEdge('c', 'd', 7);
273.                 g.AddEdge('d', 'f', 14);
274.                 g.AddEdge('d', 'e', 9);
275.                 g.AddEdge('e', 'f', 10);
276.                 g.AddEdge('f', 'g', 2);
277.                 g.AddEdge('g', 'h', 1);
278.                 g.AddEdge('g', 'i', 6);
279.                 g.AddEdge('h', 'i', 7);
281.                 Graph<char, int> kminTree;
282.                 cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
283.                 //kminTree.Print();
285.                 /*Graph<char, int> pminTree;
286.                 cout << "Prim:" << g.Prim(pminTree, 'a') << endl;
287.                 pminTree.Print();*/
288.         }
289. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。