c++最小生成树的 Prim算法 Kruskal算法
时间: 2023-11-10 12:22:08 浏览: 52
Prim算法和Kruskal算法都是用来解决最小生成树问题的算法,它们的思路和实现都有所不同。
Prim算法的基本思路是从一个顶点开始,每次找到一个与当前生成树相连的权值最小的边所连接的顶点,并将该顶点加入到生成树中,直到所有的顶点都被加入到生成树中为止。
Kruskal算法则是按照边的权值从小到大的顺序来加入边,每次加入一条边之前,判断这条边所连接的两个顶点是否在同一个连通块中,如果不在,则将这条边加入到生成树中,直到生成树中有n-1条边为止。
两种算法都能够求出最小生成树,但是它们的实现方式和时间复杂度略有不同。Prim算法的时间复杂度为O(n^2),适用于稠密图;而Kruskal算法的时间复杂度为O(m log m),适用于稀疏图。
相关问题
请通过C++使用prim算法和kruskal算法编程实现最小生成树
以下是C++实现Prim算法和Kruskal算法求最小生成树的示例代码:
Prim算法:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
int n;
int g[MAXN][MAXN];
int d[MAXN];
bool vis[MAXN];
void prim(int s) {
memset(d, INF, sizeof(d));
memset(vis, false, sizeof(vis));
d[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(make_pair(d[s], s));
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (int v = 1; v <= n; v++) {
if (g[u][v] < INF && !vis[v] && g[u][v] < d[v]) {
d[v] = g[u][v];
pq.push(make_pair(d[v], v));
}
}
}
}
int main() {
int m;
cin >> n >> m;
memset(g, INF, sizeof(g));
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u][v] = g[v][u] = w;
}
prim(1);
int ans = 0;
for (int i = 1; i <= n; i++) {
if (d[i] == INF) {
cout << "No solution!" << endl;
return 0;
}
ans += d[i];
}
cout << ans << endl;
return 0;
}
```
Kruskal算法:
```c++
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 1005;
int n;
int fa[MAXN];
struct Edge {
int u, v, w;
bool operator<(const Edge& e) const {
return w < e.w;
}
} edges[MAXN * MAXN];
int find(int x) {
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
int kruskal() {
int ans = 0, cnt = 0;
sort(edges, edges + n * (n - 1) / 2);
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 0; i < n * (n - 1) / 2; i++) {
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
int fu = find(u), fv = find(v);
if (fu != fv) {
fa[fu] = fv;
ans += w;
cnt++;
if (cnt == n - 1) break;
}
}
return ans;
}
int main() {
int m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
edges[i] = { u, v, w };
}
cout << kruskal() << endl;
return 0;
}
```
c++分别用Prim算法和Kruskal算法编程实现一下连通无向图的最小生成树。
好的,下面分别给出使用 Prim 算法和 Kruskal 算法实现连通无向图的最小生成树的 C++ 代码实现。
首先,我们需要定义一个边的结构体,用于存储边的起点、终点和权重:
```c++
struct Edge {
int src, dest, weight;
};
```
接下来,我们分别实现 Prim 算法和 Kruskal 算法。
使用 Prim 算法实现最小生成树:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
// 定义边
struct Edge {
int src, dest, weight;
};
// 定义比较函数,用于优先队列
struct Compare {
bool operator()(Edge const& e1, Edge const& e2) {
return e1.weight > e2.weight;
}
};
// 定义 Prim 算法函数
void primMST(vector<vector<int>>& graph, int n) {
vector<int> key(n, INT_MAX);
vector<bool> mstSet(n, false);
priority_queue<Edge, vector<Edge>, Compare> pq;
key[0] = 0;
pq.push({0, 0, 0});
while (!pq.empty()) {
int u = pq.top().dest;
pq.pop();
if (mstSet[u]) continue;
mstSet[u] = true;
for (int v = 0; v < n; v++) {
if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
key[v] = graph[u][v];
pq.push({u, v, key[v]});
}
}
}
int sum = 0;
for (int i = 1; i < n; i++) {
sum += key[i];
}
cout << "Prim算法得到的最小生成树权值和为 " << sum << endl;
}
// 测试函数
int main() {
int n = 5;
vector<vector<int>> graph = {
{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0}
};
primMST(graph, n);
return 0;
}
```
使用 Kruskal 算法实现最小生成树:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 定义边
struct Edge {
int src, dest, weight;
};
// 定义比较函数,用于排序
bool compare(Edge const& e1, Edge const& e2) {
return e1.weight < e2.weight;
}
// 定义 Kruskal 算法函数
void kruskalMST(vector<Edge>& edges, int n) {
vector<Edge> result(n - 1);
sort(edges.begin(), edges.end(), compare);
vector<int> parent(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
int e = 0, i = 0;
while (e < n - 1) {
Edge next_edge = edges[i++];
int x = parent[next_edge.src];
int y = parent[next_edge.dest];
if (x != y) {
result[e++] = next_edge;
for (int j = 0; j < n; j++) {
if (parent[j] == y) {
parent[j] = x;
}
}
}
}
int sum = 0;
for (int i = 0; i < n - 1; i++) {
sum += result[i].weight;
}
cout << "Kruskal算法得到的最小生成树权值和为 " << sum << endl;
}
// 测试函数
int main() {
int n = 5;
vector<Edge> edges = {
{0, 1, 2},
{0, 3, 6},
{1, 2, 3},
{1, 3, 8},
{1, 4, 5},
{2, 4, 7},
{3, 4, 9}
};
kruskalMST(edges, n);
return 0;
}
```
以上代码中,我们分别实现了 Prim 算法和 Kruskal 算法。在 Prim 算法中,我们使用了一个优先队列来维护当前最小的边,同时使用了一个 `key` 数组来记录每个节点到当前生成树的最小边权值。在 Kruskal 算法中,我们使用了一个并查集来维护当前生成树。
在测试函数中,我们定义了一个无向图,然后分别调用了 Prim 算法和 Kruskal 算法来计算最小生成树的权值和,最终输出结果。
希望这个代码能够帮助到您!