给我写一个基于C++的生成树
时间: 2024-06-10 09:10:22 浏览: 7
这里提供一个基于C语言的最小生成树算法——Prim算法的实现。
Prim算法是一种贪心算法,它从一个点开始,每次选择离该点最近的未访问过的点加入到生成树中,直到所有点都被访问过。
以下是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAXV 1000
typedef struct {
int v, w;
} Edge;
Edge graph[MAXV][MAXV]; // 邻接矩阵表示图
int n; // 图中的节点数
int prim() {
int i, j, min, minindex, sum = 0;
int d[MAXV], visited[MAXV];
// 初始化
for (i = 0; i < n; i++) {
visited[i] = 0;
d[i] = INT_MAX;
}
d[0] = 0; // 从第一个点开始
for (i = 0; i < n; i++) {
min = INT_MAX;
// 找到距离最小的节点
for (j = 0; j < n; j++) {
if (!visited[j] && d[j] < min) {
min = d[j];
minindex = j;
}
}
visited[minindex] = 1;
sum += min;
// 更新距离
for (j = 0; j < n; j++) {
if (!visited[j] && graph[minindex][j].w < d[j]) {
d[j] = graph[minindex][j].w;
}
}
}
return sum;
}
int main() {
int i, j, m;
scanf("%d%d", &n, &m);
// 初始化邻接矩阵
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
graph[i][j].v = i;
graph[i][j].w = INT_MAX;
}
}
// 读入边
for (i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
graph[u][v].w = w;
graph[v][u].w = w;
}
int ans = prim();
printf("%d\n", ans);
return 0;
}
```
输入格式为:
```
节点数 边数
u1 v1 w1
u2 v2 w2
...
um vm wm
```
其中 `u` 和 `v` 表示边的两个端点,`w` 表示边的权重。
输出为最小生成树的权值和。
注意:
- 如果两个节点之间没有边,则它们之间的距离应该设置为一个很大的值,这里使用了 `INT_MAX`;
- 这里使用了邻接矩阵表示图,如果使用邻接表的话,可以将 `graph` 数组改为一个链表数组。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)