Kruskal算法C++实现
Kruskal算法C++实现
Kruskal算法
Kruskal算法是一种按权值的递增次序选择合适的边构造最小生成树的办法，初始化，生成一个包含图中所有顶点且没有边的森林，从图中的边选取最小代价边加入森林，若成环则舍弃，否则使森林的连通分量减少1，直到生成森林变为生成树，只含一个连通分量和|V| - 1条边
借助优先队列（最小堆）选取最小代价边，每次调整时间复杂度O(lg|E|)，选取|V|-1条边，最多考虑|E|条边，故算法时间复杂度为O(|E|lg|E|)
void Graph::kruskal() {for (int i = 0; i < vextexNumber - 1; ) {//借助最小堆选取最小代价边int rootU = findRoot(edges.top().u);int rootV = findRoot(edges.top().v);if (rootU != rootV) {//若不在一个连通分量中，则合并findSet[rootU] = rootV;//合并连通分量weight += edges.top().weight;//累积权值i++;//选取n-1条边，当且仅当选取到边才使i自增，直到i == |V| - 1//使循环在选取|V|-1条边后退出}edges.pop();}
}
并查集
借助并查集，迅速判断边连接的两个顶点是否在一个连通分量中，若在同一个连通分量中，则舍弃边，因为在同一个连通分量中，即在同根节点的树中，树增加一条边即会形成回路，若不在同一连通分量中，将边加入生成树中，将两个连通分量合并。
int findRoot(int x) {return findSet[x] == x ? x : findSet[x] = findRoot(findSet[x]);
}
实现代码
/*
author : eclipse
email : eclipsecs@qq.com
time : Mon Jun 08 22:42:13 2020
*/
#include <bits/stdc++.h>
using namespace std;struct Edge {int u;int v;int weight;bool operator < (const Edge& x) const{return weight > x.weight;}
};class Graph {
private:int weight;int vextexNumber;vector<int> findSet;priority_queue<Edge> edges;int findRoot(int x);
public:Graph(int vextexNumber, vector<Edge> v);void kruskal();int minimumWeight();
};Graph::Graph(int vextexNumber, vector<Edge> v) {weight = 0;findSet.resize(vextexNumber);this->vextexNumber = vextexNumber;for (int i = 0; i < v.size(); i++) {edges.push(v[i]);findSet[i] = i;}
}void Graph::kruskal() {for (int i = 0; i < vextexNumber - 1; ) {int rootU = findRoot(edges.top().u);int rootV = findRoot(edges.top().v);if (rootU != rootV) {findSet[rootU] = rootV;weight += edges.top().weight;i++;}edges.pop();}
}int Graph::minimumWeight() {return weight;
}int Graph::findRoot(int x) {return findSet[x] == x ? x : findSet[x] = findRoot(findSet[x]);
}int main(int argc, char const *argv[]) {vector<Edge> edges;int vextexNumber, N;scanf("%d%d", &vextexNumber, &N);for (int i = 0; i < N; i++) {int u, v, w;scanf("%d%d%d", &u, &v, &w);edges.push_back((Edge){u, v, w});}Graph *graph = new Graph(vextexNumber, edges);graph->kruskal();printf("%d", graph->minimumWeight());return 0;
}测试数据
5 7
0 1 4
0 2 5
0 3 1
2 3 6
1 2 3
1 3 2
1 4 10
输出数据
16
鸣谢
《算法竞赛入门经典训练指南》
最后
- 由于博主水平有限，不免有疏漏之处，欢迎读者随时批评指正，以免造成不必要的误解！
Kruskal算法C++实现
Kruskal算法C++实现
Kruskal算法
Kruskal算法是一种按权值的递增次序选择合适的边构造最小生成树的办法，初始化，生成一个包含图中所有顶点且没有边的森林，从图中的边选取最小代价边加入森林，若成环则舍弃，否则使森林的连通分量减少1，直到生成森林变为生成树，只含一个连通分量和|V| - 1条边
借助优先队列（最小堆）选取最小代价边，每次调整时间复杂度O(lg|E|)，选取|V|-1条边，最多考虑|E|条边，故算法时间复杂度为O(|E|lg|E|)
void Graph::kruskal() {for (int i = 0; i < vextexNumber - 1; ) {//借助最小堆选取最小代价边int rootU = findRoot(edges.top().u);int rootV = findRoot(edges.top().v);if (rootU != rootV) {//若不在一个连通分量中，则合并findSet[rootU] = rootV;//合并连通分量weight += edges.top().weight;//累积权值i++;//选取n-1条边，当且仅当选取到边才使i自增，直到i == |V| - 1//使循环在选取|V|-1条边后退出}edges.pop();}
}
并查集
借助并查集，迅速判断边连接的两个顶点是否在一个连通分量中，若在同一个连通分量中，则舍弃边，因为在同一个连通分量中，即在同根节点的树中，树增加一条边即会形成回路，若不在同一连通分量中，将边加入生成树中，将两个连通分量合并。
int findRoot(int x) {return findSet[x] == x ? x : findSet[x] = findRoot(findSet[x]);
}
实现代码
/*
author : eclipse
email : eclipsecs@qq.com
time : Mon Jun 08 22:42:13 2020
*/
#include <bits/stdc++.h>
using namespace std;struct Edge {int u;int v;int weight;bool operator < (const Edge& x) const{return weight > x.weight;}
};class Graph {
private:int weight;int vextexNumber;vector<int> findSet;priority_queue<Edge> edges;int findRoot(int x);
public:Graph(int vextexNumber, vector<Edge> v);void kruskal();int minimumWeight();
};Graph::Graph(int vextexNumber, vector<Edge> v) {weight = 0;findSet.resize(vextexNumber);this->vextexNumber = vextexNumber;for (int i = 0; i < v.size(); i++) {edges.push(v[i]);findSet[i] = i;}
}void Graph::kruskal() {for (int i = 0; i < vextexNumber - 1; ) {int rootU = findRoot(edges.top().u);int rootV = findRoot(edges.top().v);if (rootU != rootV) {findSet[rootU] = rootV;weight += edges.top().weight;i++;}edges.pop();}
}int Graph::minimumWeight() {return weight;
}int Graph::findRoot(int x) {return findSet[x] == x ? x : findSet[x] = findRoot(findSet[x]);
}int main(int argc, char const *argv[]) {vector<Edge> edges;int vextexNumber, N;scanf("%d%d", &vextexNumber, &N);for (int i = 0; i < N; i++) {int u, v, w;scanf("%d%d%d", &u, &v, &w);edges.push_back((Edge){u, v, w});}Graph *graph = new Graph(vextexNumber, edges);graph->kruskal();printf("%d", graph->minimumWeight());return 0;
}测试数据
5 7
0 1 4
0 2 5
0 3 1
2 3 6
1 2 3
1 3 2
1 4 10
输出数据
16
鸣谢
《算法竞赛入门经典训练指南》
最后
- 由于博主水平有限，不免有疏漏之处，欢迎读者随时批评指正，以免造成不必要的误解！
发布评论