Kruskal算法用于查找连接加权图的最小生成树。该算法的主要目标是通过使用哪个来找到边的子集，可以遍历图的每个顶点。Kruskal算法遵循贪婪的方法，在每个阶段找到最佳解决方案，而不是专注于全局最优。
Kruskal算法如下。
第1步：创建一个森林，使每个图形都是一个单独的树。
第2步：创建包含图表所有边缘的优先级队列Q。
第3步：重复第4步和第5步，而Q不为空。
第4步：从Q中删除边
第5步：如果在步骤4中获得的边连接两个不同的树，则将其添加到森林中(用于将两个树组合成一个树)。
其他
丢弃边
第6步：结束
示例：
将Kruskal算法应用于如下图表。
解决方案：
边的权重如下：
| 边 | AE | AD | AC | AB | BC | CD | DE |
|---|---|---|---|---|---|---|---|
| 权重 | 5 | 10 | 7 | 1 | 3 | 4 | 2 |
根据权重对边进行排序。
| 边 | AB | DE | BC | CD | AE | AC | AD |
|---|---|---|---|---|---|---|---|
| 权重 | 1 | 2 | 3 | 4 | 5 | 7 | 10 |
开始构建树，将AB添加到MST;
将DE添加到MST;
将BC添加到MST;
下一步是添加AE，但不能添加它，因为它会导致循环。
要添加的下一个边是AC，但不能添加，因为它会导致循环。
要添加的下一个边是AD，但无法添加，因为它将包含一个循环。
因此，最终的MST是步骤4中所示的MST。
MST的成本 = 1 + 2 + 3 + 4 = 10。
使用C++实现上面算法，代码如下所示 -
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
const int MAX = 1e4 + 5;
int id[MAX], nodes, edges;
pair <long long, pair<int, int> > p[MAX];
void init()
{
for(int i = 0;i < MAX;++i)
id[i] = i;
}
int root(int x)
{
while(id[x] != x)
{
id[x] = id[id[x]];
x = id[x];
}
return x;
}
void union1(int x, int y)
{
int p = root(x);
int q = root(y);
id[p] = id[q];
}
long long kruskal(pair<long long, pair<int, int> > p[])
{
int x, y;
long long cost, minimumCost = 0;
for(int i = 0;i < edges;++i)
{
x = p[i].second.first;
y = p[i].second.second;
cost = p[i].first;
if(root(x) != root(y))
{
minimumCost += cost;
union1(x, y);
}
}
return minimumCost;
}
int main()
{
int x, y;
long long weight, cost, minimumCost;
init();
cout <<"Enter Nodes and edges";
cin >> nodes >> edges;
for(int i = 0;i < edges;++i)
{
cout<<"Enter the value of X, Y and edges";
cin >> x >> y >> weight;
p[i] = make_pair(weight, make_pair(x, y));
}
sort(p, p + edges);
minimumCost = kruskal(p);
cout <<"Minimum cost is "<< minimumCost << endl;
return 0;
}
执行上面示例代码，得到以下结果：
Enter Nodes and edges5
5
Enter the value of X, Y and edges5
4
3
Enter the value of X, Y and edges2
3
1
Enter the value of X, Y and edges1
2
3
Enter the value of X, Y and edges5
4
3
Enter the value of X, Y and edges23
3
4
Minimum cost is 11
