最小生成树prim和kruskal算法
时间: 2023-11-12 22:07:31 浏览: 64
Prim算法和Kruskal算法都是用于求解最小生成树的经典算法。
Prim算法的基本思想是从一个点开始,每次选择一个与当前生成树距离最近的点加入生成树中,直到所有点都被加入生成树为止。具体实现时,可以使用一个优先队列来维护当前生成树与未加入生成树的点之间的距离,每次选择距离最小的点加入生成树中。
Kruskal算法的基本思想是从边开始,每次选择一条权值最小且不会形成环的边加入生成树中,直到生成树中包含所有点为止。具体实现时,可以使用并查集来判断是否形成环。
下面是Prim算法和Kruskal算法的C语言代码实现:
Prim算法:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTICES 1000
int graph[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES];
int dist[MAX_VERTICES];
int prim(int n) {
int i, j, u, min_dist, min_index, sum = 0;
for (i = 0; i < n; i++) {
visited[i] = 0;
dist[i] = INT_MAX;
}
dist[0] = 0;
for (i = 0; i < n; i++) {
min_dist = INT_MAX;
for (j = 0; j < n; j++) {
if (!visited[j] && dist[j] < min_dist) {
min_dist = dist[j];
min_index = j;
}
}
u = min_index;
visited[u] = 1;
sum += dist[u];
for (j = 0; j < n; j++) {
if (!visited[j] && graph[u][j] < dist[j]) {
dist[j] = graph[u][j];
}
}
}
return sum;
}
int main() {
int n, m, i, j, u, v, w;
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
graph[i][j] = INT_MAX;
}
}
for (i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &w);
graph[u][v] = graph[v][u] = w;
}
printf("%d\n", prim(n));
return 0;
}
```
Kruskal算法:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTICES 1000
#define MAX_EDGES 1000000
struct edge {
int u, v, w;
};
int parent[MAX_VERTICES];
struct edge edges[MAX_EDGES];
int cmp(const void *a, const void *b) {
return ((struct edge *)a)->w - ((struct edge *)b)->w;
}
int find(int x) {
if (parent[x] == x) {
return x;
}
return parent[x] = find(parent[x]);
}
void union_set(int x, int y) {
parent[find(x)] = find(y);
}
int kruskal(int n, int m) {
int i, sum = 0;
for (i = 0; i < n; i++) {
parent[i] = i;
}
qsort(edges, m, sizeof(struct edge), cmp);
for (i = 0; i < m; i++) {
if (find(edges[i].u) != find(edges[i].v)) {
union_set(edges[i].u, edges[i].v);
sum += edges[i].w;
}
}
return sum;
}
int main() {
int n, m, i;
scanf("%d%d", &n, &m);
for (i = 0; i < m; i++) {
scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);
}
printf("%d\n", kruskal(n, m));
return 0;
}
```