请用C++写一个最小生成树算法
时间: 2024-06-11 20:11:18 浏览: 15
以下是基于Prim算法的最小生成树算法实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define VERTICES 6 // 顶点数
#define INF INT_MAX // 无穷大
int graph[VERTICES][VERTICES] = { // 邻接矩阵表示的图
{0, 4, INF, INF, INF, INF},
{4, 0, 8, INF, INF, INF},
{INF, 8, 0, 7, INF, 4},
{INF, INF, 7, 0, 9, 14},
{INF, INF, INF, 9, 0, 10},
{INF, INF, 4, 14, 10, 0}
};
int prim(int graph[][VERTICES]) {
int parent[VERTICES]; // 存储最小生成树的父节点
int key[VERTICES]; // 存储顶点到最小生成树的最小权值
int visited[VERTICES]; // 标记顶点是否已经加入最小生成树
for (int i = 0; i < VERTICES; i++) {
key[i] = INF; // 初始化为无穷大
visited[i] = 0; // 初始化为未访问
}
key[0] = 0; // 从第一个顶点开始构建最小生成树
parent[0] = -1; // 第一个顶点没有父节点
for (int i = 0; i < VERTICES - 1; i++) {
// 从还未加入最小生成树的顶点中,找到key值最小的顶点
int min_key = INF, min_index;
for (int j = 0; j < VERTICES; j++) {
if (!visited[j] && key[j] < min_key) {
min_key = key[j];
min_index = j;
}
}
visited[min_index] = 1; // 将顶点加入最小生成树
// 更新min_index的邻居顶点的key值和parent
for (int j = 0; j < VERTICES; j++) {
if (graph[min_index][j] && !visited[j] && graph[min_index][j] < key[j]) {
parent[j] = min_index;
key[j] = graph[min_index][j];
}
}
}
// 输出最小生成树
printf("Edge \tWeight\n");
for (int i = 1; i < VERTICES; i++) {
printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]);
}
return 0;
}
int main() {
prim(graph);
return 0;
}
```
其中,邻接矩阵`graph`表示的图如下所示:
```
4 8
(0)---(1)---(2)
| / | \ |
| / | \|
|/ | \|
(5) 14 (3)
\ | /
\ | /
\ | /
\ | /
(4)
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)