使用贪心算法解决最小生成树问题C语言
时间: 2023-08-02 14:16:14 浏览: 71
最小生成树问题可以使用贪心算法来解决,其中Prim算法和Kruskal算法是两种常见的贪心算法。
下面以Prim算法为例,给出C语言的实现:
```c
#include <stdio.h>
#include <stdbool.h>
#define INFINITY 1000000
int n; // 顶点数
int graph[100][100]; // 图的邻接矩阵
int lowcost[100]; // 存储当前点到已选点集的最小边权值
bool visited[100]; // 标记点是否已被选中
// Prim算法求最小生成树
void Prim(int v0)
{
int i, j, k;
int min, sum = 0;
// 初始化
for (i = 0; i < n; i++) {
lowcost[i] = graph[v0][i];
visited[i] = false;
}
visited[v0] = true;
// 每次找到一个未被选中的点集中到已选点集最小边
for (i = 1; i < n; i++) {
min = INFINITY;
k = v0;
for (j = 0; j < n; j++) {
if (!visited[j] && lowcost[j] < min) {
min = lowcost[j];
k = j;
}
}
visited[k] = true;
sum += min;
for (j = 0; j < n; j++) {
if (!visited[j] && graph[k][j] < lowcost[j]) {
lowcost[j] = graph[k][j];
}
}
}
printf("The weight of the minimum spanning tree is: %d\n", sum);
}
int main()
{
int i, j, v0;
// 输入图的顶点数和邻接矩阵
printf("Please input the number of vertices: ");
scanf("%d", &n);
printf("Please input the adjacency matrix: \n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
// 输入起始点
printf("Please input the starting vertex: ");
scanf("%d", &v0);
// 求最小生成树
Prim(v0);
return 0;
}
```
以上代码使用了邻接矩阵来表示图,时间复杂度为O(n^2)。如果使用邻接表来表示图,则时间复杂度可以优化到O(nlogn)。