C# Kruskal 最小生成树 (MST) 算法（Kruskal’s Minimum Spanning Tree (MST) Algorithm）
对于加权、连通、无向图，最小生成树(MST) 或最小权重生成树是权重小于或等于其他所有生成树权重的生成树。
Kruskal算法简介：
在这里，我们将讨论Kruskal 算法来查找给定加权图的 MST。
在 Kruskal 算法中，按升序对给定图的所有边进行排序。然后，如果新添加的边不形成循环，它会继续在 MST 中添加新边和节点。它首先选择最小权重边，最后选择最大权重边。因此，我们可以说它在每一步中都做出局部最优选择以找到最优解。因此，这是一种贪婪算法。
如何使用 Kruskal 算法查找 MST？
以下是使用 Kruskal 算法查找 MST 的步骤：
1.按照权重的非递减顺序对所有边进行排序。
2.选择最小的边。检查它是否与目前形成的生成树形成一个循环。如果没有形成循环，则包括这条边。否则，丢弃它。
3.重复步骤#2，直到生成树中有 (V-1) 条边。
第 2 步使用并查集算法来检测循环。
因此，我们建议先阅读以下文章：
并查表算法 | 集合 1（检测图中的循环）
javascript 不相交集简介（并查集算法）：https://blog.csdn.net/hefeng_aspnet/article/details/142524938
C# 不相交集简介（并查集算法）：https://blog.csdn.net/hefeng_aspnet/article/details/142524824
python 不相交集简介（并查集算法）：https://blog.csdn.net/hefeng_aspnet/article/details/142524698
java 不相交集简介（并查集算法）：https://blog.csdn.net/hefeng_aspnet/article/details/142524698
c++ 不相交集简介（并查集算法）：https://blog.csdn.net/hefeng_aspnet/article/details/142523025
并查集算法 | 集合 2（按秩并集和路径压缩）
c语言 并查集算法中的按秩联合和路径压缩：https://blog.csdn.net/hefeng_aspnet/article/details/142526674
javascript 并查集算法中的按秩联合和路径压缩：https://blog.csdn.net/hefeng_aspnet/article/details/142526517
C# 并查集算法中的按秩联合和路径压缩：https://blog.csdn.net/hefeng_aspnet/article/details/142526449
python 并查集算法中的按秩联合和路径压缩：https://blog.csdn.net/hefeng_aspnet/article/details/142526387
java 并查集算法中的按秩联合和路径压缩：https://blog.csdn.net/hefeng_aspnet/article/details/142526336
c++ 并查集算法中的按秩联合和路径压缩：https://blog.csdn.net/hefeng_aspnet/article/details/142525945
Kruskal 寻找最小成本生成树的算法采用贪婪方法。贪婪选择是选择迄今为止构建的 MST 中不会引起循环的最小权重边。让我们通过一个例子来理解它：
插图：
下面是上述方法的说明：
输入图：
该图包含 9 个顶点和 14 条边。因此，形成的最小生成树将具有 (9 - 1) = 8 条边。
排序后：
| Weight | Source | Destination |
| 1 | 7 | 6 |
| 2 | 8 | 2 |
| 2 | 6 | 5 |
| 4 | 0 | 1 |
| 4 | 2 | 5 |
| 6 | 8 | 6 |
| 7 | 2 | 3 |
| 7 | 7 | 8 |
| 8 | 0 | 7 |
| 8 | 1 | 2 |
| 9 | 3 | 4 |
| 10 | 5 | 4 |
| 11 | 1 | 7 |
| 14 | 3 | 5 |
现在从排序的边列表中逐一选择所有边
步骤 1：选取边 7-6。未形成循环，将其包括在内。
步骤 2：拾取边 8-2。未形成循环，将其包括在内。
步骤 3：选取边 6-5。未形成循环，将其包括在内。
步骤 4：选取边 0-1。没有形成循环，将其包括在内。
步骤 5：选取边 2-5。未形成循环，将其包括在内。
步骤 6：选择边 8-6。由于包含此边会导致循环，因此将其丢弃。选择边 2-3：未形成循环，因此将其包括在内。
步骤 7：选择边 7-8。由于包含此边会导致循环，因此将其丢弃。选择边 0-7。未形成循环，因此将其包括在内。
步骤 8：选择边 1-2。由于包含此边会导致循环，因此将其丢弃。选择边 3-4。未形成循环，因此将其包括在内。
注意：由于MST中包含的边数等于（V-1），因此算法在此停止
下面是上述方法的实现：
// C# Code for the above approach
using System;
class Graph {
// A class to represent a graph edge
class Edge : IComparable<Edge> {
public int src, dest, weight;
// Comparator function used for sorting edges
// based on their weight
public int CompareTo(Edge compareEdge)
{
return this.weight - compareEdge.weight;
}
}
// A class to represent
// a subset for union-find
public class subset {
public int parent, rank;
};
// V-> no. of vertices & E->no.of edges
int V, E;
// Collection of all edges
Edge[] edge;
// Creates a graph with V vertices and E edges
Graph(int v, int e)
{
V = v;
E = e;
edge = new Edge[E];
for (int i = 0; i < e; ++i)
edge[i] = new Edge();
}
// A utility function to find set of an element i
// (uses path compression technique)
int find(subset[] subsets, int i)
{
// Find root and make root as
// parent of i (path compression)
if (subsets[i].parent != i)
subsets[i].parent
= find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// A function that does union of
// two sets of x and y (uses union by rank)
void Union(subset[] subsets, int x, int y)
{
int xroot = find(subsets, x);
int yroot = find(subsets, y);
// Attach smaller rank tree under root of
// high rank tree (Union by Rank)
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
// If ranks are same, then make one as root
// and increment its rank by one
else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
// The main function to construct MST
// using Kruskal's algorithm
void KruskalMST()
{
// This will store the
// resultant MST
Edge[] result = new Edge[V];
// An index variable, used for result[]
int e = 0;
// An index variable, used for sorted edges
int i = 0;
for (i = 0; i < V; ++i)
result[i] = new Edge();
// Sort all the edges in non-decreasing
// order of their weight. If we are not allowed
// to change the given graph, we can create
// a copy of array of edges
Array.Sort(edge);
// Allocate memory for creating V subsets
subset[] subsets = new subset[V];
for (i = 0; i < V; ++i)
subsets[i] = new subset();
// Create V subsets with single elements
for (int v = 0; v < V; ++v) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
i = 0;
// Number of edges to be taken is equal to V-1
while (e < V - 1) {
// Pick the smallest edge. And increment
// the index for next iteration
Edge next_edge = new Edge();
next_edge = edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
// If including this edge doesn't cause cycle,
// include it in result and increment the index
// of result for next edge
if (x != y) {
result[e++] = next_edge;
Union(subsets, x, y);
}
}
// Print the contents of result[] to display
// the built MST
Console.WriteLine("Following are the edges in "
+ "the constructed MST");
int minimumCost = 0;
for (i = 0; i < e; ++i) {
Console.WriteLine(result[i].src + " -- "
+ result[i].dest
+ " == " + result[i].weight);
minimumCost += result[i].weight;
}
Console.WriteLine("Minimum Cost Spanning Tree: "
+ minimumCost);
Console.ReadLine();
}
// Driver's Code
public static void Main(String[] args)
{
int V = 4;
int E = 5;
Graph graph = new Graph(V, E);
// add edge 0-1
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = 10;
// add edge 0-2
graph.edge[1].src = 0;
graph.edge[1].dest = 2;
graph.edge[1].weight = 6;
// add edge 0-3
graph.edge[2].src = 0;
graph.edge[2].dest = 3;
graph.edge[2].weight = 5;
// add edge 1-3
graph.edge[3].src = 1;
graph.edge[3].dest = 3;
graph.edge[3].weight = 15;
// add edge 2-3
graph.edge[4].src = 2;
graph.edge[4].dest = 3;
graph.edge[4].weight = 4;
// Function call
graph.KruskalMST();
}
}
// This code is contributed by Aakash Hasija
输出
以下是构建的 MST 中的边
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
最小成本生成树：19
时间复杂度： O（E * logE）或O（E * logV）
1.边的排序需要 O(E * logE) 时间。
2.排序后，我们遍历所有边并应用查找并集算法。查找和并集操作最多需要 O(logV) 时间。
3.因此总体复杂度为 O(E * logE + E * logV) 时间。
4.E 的值最多为 O(V 2 )，因此 O(logV) 和 O(logE) 相同。因此，总体时间复杂度为 O(E * logE) 或 O(E*logV)
辅助空间： O（V + E），其中 V 是图中顶点的数量，E 是边的数量。
原文地址：https://blog.csdn.net/hefeng_aspnet/article/details/142527411
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！