zzoce 🧊
最小生成树

最小生成树

Fri Oct 04 2024
zzcoe
11 分钟
数据结构与算法 图论
1798 字

最小生成树 - OI Wiki (oi-wiki.org)

例题：P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

kruskal算法#

克鲁斯卡尔(Kruskal)算法是一种用于在加权图中寻找最小生成树的算法。它的工作原理是按照边的权重顺序（从小到大）检查每条边，如果加入这条边不会形成环（用[[并查集]]判断），则将其加入到最小生成树中，直到加入了足够的边为止（对于一个含有(n)个顶点的图，最小生成树将包含(n-1)条边）。

克鲁斯卡尔(Kruskal)算法的时间复杂度主要取决于两个部分：边的排序以及并查集操作。

  1. 边的排序：克鲁斯卡尔算法首先需要对图中的所有边按权重进行排序。对于包含(E)条边的图，这一步的时间复杂度是(O(E\log E))。

  2. 并查集操作：算法接下来对每条边执行并查集的查找和合并操作，以确定是否添加该边到最小生成树中。在最坏情况下，这些操作的时间复杂度为(O(E\log V))，其中(V)是顶点的数量。然而，使用路径压缩和按秩合并的优化后，并查集操作的平均时间复杂度可以接近(O(1))，因此整个并查集操作的时间复杂度可以认为是(O(E))。

综上所述，克鲁斯卡尔算法的总时间复杂度是(O(Elog⁡E+E)=O(Elog⁡E))(O(E\log E + E) = O(E\log E))。因为在大多数情况下，(E)远大于(V)(V)，并且对于稠密图来说，(E)(E)接近于(V2)(V^2)，所以排序的时间复杂度占主导。

优化方法#

  1. 更快的排序算法：尽管标准的排序算法（如快速排序、归并排序）的时间复杂度已经是(O(E\log E))，但在特定情况下可以考虑使用基数排序等线性时间复杂度的排序算法，特别是当边权重的范围较小且已知时。

  2. 并查集优化：虽然并查集操作的时间复杂度已经很低，但仍然可以通过两种主要技术进一步优化：

    • 路径压缩(Path Compression)：在执行查找操作时，将查找路径上的每个节点都直接连接到根节点，这样可以减少后续查找操作的深度。
    • 按秩合并(Union by Rank)：总是将较小的树连接到较大的树的根上，这样可以避免树变得过深，从而优化合并操作的时间复杂度。

  3. 减少不必要的操作：在实际实现中，可以通过维护一些额外的数据结构来避免对某些边进行不必要的操作。例如，如果已知某个顶点属于当前最小生成树的连通分量中，那么连接这个顶点和其他属于同一连通分量的顶点的边就不需要考虑。

通过这些优化，克鲁斯卡尔算法的性能可以在实际应用中得到显著提升，尤其是在处理大规模图数据时。

代码实现#

以下是实现克鲁斯卡尔算法的C++代码，包括并查集的实现来帮助检测环：

CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 边的定义
struct Edge {
//`src`和`dest`分别表示边的起点和终点。
//`weight`表示边的权重。
    int src, dest;
    int weight;
};

// 图的定义
struct Graph {
    int V, E; // 顶点数和边数
    vector<Edge> edges; // 边的集合

    // 添加边
    void addEdge(int src, int dest, int weight) {
        edges.push_back({src, dest, weight});
    }
};

// 并查集的节点
struct Subset {
    int parent;
    int rank;
    //- `parent`表示该节点的父节点。
	//`rank`表示树的高度（用于按秩合并）。
};

// 查找集合的根，并进行路径压缩
int find(vector<Subset>& subsets, int i) {
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
}

// 按秩合并两个集合
void Union(vector<Subset>& subsets, int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);
	//- 按秩合并：总是将较小的树合并到较大的树上。
	//如果两棵树的高度相同，则选择一棵作为根，并增加其`rank`。
    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
    else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

// 克鲁斯卡尔算法
void KruskalMST(Graph& graph) {
    int V = graph.V;
    vector<Edge> result; // 存储最小生成树的边
    int e = 0; // 结果数组的索引

    // 按边权重排序
    sort(graph.edges.begin(), graph.edges.end(), [](Edge a, Edge b) {
        return a.weight < b.weight;
    });

    vector<Subset> subsets(V);

    // 创建V个单元素集合
    for (int v = 0; v < V; ++v) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }

    int i = 0; // 用于边的索引
    while (e < V - 1 && i < graph.E) {
        Edge next_edge = graph.edges[i++];

        int x = find(subsets, next_edge.src);
        int y = find(subsets, next_edge.dest);

        if (x != y) {
            result.push_back(next_edge);
            Union(subsets, x, y);
            e++;
        }
    }

    // 打印构建的最小生成树
    cout << "Following are the edges in the constructed MST\n";
    for (auto& edge : result)
        cout << edge.src << " -- " << edge.dest << " == " << edge.weight << endl;
}

int main() {
    int V = 4;  // 顶点的数量
    int E = 5;  // 边的数量
    Graph graph = {V, E};

    // 添加边: src, dest, weight
    graph.addEdge(0, 1, 10);
    graph.addEdge(0, 2, 6);
    graph.addEdge(0, 3, 5);
    graph.addEdge(1, 3, 15);
    graph.addEdge(2, 3, 4);

    KruskalMST(graph);

    return 0;
}

这段代码首先定义了图的结构，包括顶点、边以及边的权重。然后，它使用并查集数据结构来维护集合的信息，这对于检测加入边时是否会形成环是必要的。在主函数中，我们创建了一个图的实例，添加了一些边，然后调用KruskalMST函数来找到最小生成树并打印结果。

prim算法#

该算法的基本思想是从一个结点开始，不断加点，每次要选择距离最小的一个结点，以及用新的边更新其他结点的距离。

使用[[STL#优先队列|优先队列]]的二叉堆优化的时间复杂度O((n+m)logn)

CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
const int maxn=2e5+5;
int n,m;

//链式前向星
int tot,head[maxn];
struct node {
	int v,w,next;
}edge[maxn<<1];
void Addedge(int u,int v,int w){
	edge[tot].v=v;
	edge[tot].w=w;
	edge[tot].next=head[u];
	head[u]=tot++;
}

//优先队列
struct s{
	int u,d;
};
bool operator <(const s &x,const s &y){
	return x.d>y.d;
}

priority_queue<s> q;
int dis[maxn];
bool vis[maxn];
int res=0,cnt=0;
void prim ()
{
	memset (dis,0x3f,sizeof (dis));
	dis[1]=0;
	q.push({1,0});
	while (!q.empty()){
		if (cnt>=m)break;//每个节点都出队一次则最小生成树找到了 
		int u=q.top().u,d=q.top().d;
		q.pop();
		if (vis[u]){//已经出过队了就跳过，因为他的权值不是最小的 
			continue;
		}
		//出队成功的就是最小生成树的节点。 
		vis[u]=true;
		cnt++;//出过队的不同的节点个数，最大是m个 
		res+=d;//把权值加起来 
		for (int i=head[u];~i;i=edge[i].next){
			//遍历u的后驱 
			int v=edge[i].v,w=edge[i].w;
			if (w<dis[v]){//还有可能从别的方向到达v所以要找到尽可能小的到v的边
				//维护达到后驱的最小权值 
				dis[v]=w;
				q.push({v,w});//尽管入队，使用优先队列优化
				//第一个出队的v节点的权值就是他的最小权值。 
			}
		}
	}
}
int main ()
{
	memset (head,-1,sizeof(head));
	cin>>m>>n;
	int u,v,w;
	for (int i=1;i<=n;i++){
		cin>>u>>v>>w;
		Addedge(u,v,w);
		Addedge(v,u,w);
	}
	prim();
	if (cnt==m){
		cout<<res<<endl;
	}else {
		cout<<"orz"<<endl;
	}
	return 0;
	
}