使用C语言编写普里姆算法, TreeEage结构体定义如下, typedef struct{ int v1; 最小生成树的边的起始点。int v2; 最小生成树的边的终点。int weight; 边的权值 }MinSpanTreeEage。从序号为0的点开始,函数传入一个带权图G,求最小生成树,求得的最小牛成树存入closeVertex[]数组。
时间: 2024-02-24 12:55:50 浏览: 70
好的,这是一个经典的最小生成树问题。下面是使用C语言编写普里姆算法的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTICES 100
#define INF INT_MAX
typedef struct {
int v1;
int v2;
int weight;
} MinSpanTreeEdge;
void prim(int n, int G[][MAX_VERTICES], MinSpanTreeEdge closeVertex[]) {
int visited[MAX_VERTICES] = {0};
visited[0] = 1;
int count = 0;
while (count < n - 1) {
int minWeight = INF, minV1 = -1, minV2 = -1;
for (int i = 0; i < n; i++) {
if (visited[i]) {
for (int j = 0; j < n; j++) {
if (!visited[j] && G[i][j] < minWeight) {
minWeight = G[i][j];
minV1 = i;
minV2 = j;
}
}
}
}
if (minV1 != -1 && minV2 != -1) {
closeVertex[count].v1 = minV1;
closeVertex[count].v2 = minV2;
closeVertex[count].weight = minWeight;
count++;
visited[minV2] = 1;
}
}
}
int main() {
int n, G[MAX_VERTICES][MAX_VERTICES];
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &G[i][j]);
if (G[i][j] == 0) {
G[i][j] = INF;
}
}
}
MinSpanTreeEdge closeVertex[MAX_VERTICES];
prim(n, G, closeVertex);
int totalWeight = 0;
for (int i = 0; i < n - 1; i++) {
printf("(%d, %d) %d\n", closeVertex[i].v1, closeVertex[i].v2, closeVertex[i].weight);
totalWeight += closeVertex[i].weight;
}
printf("Total weight: %d\n", totalWeight);
return 0;
}
```
其中,`G`是一个`n`个顶点的带权图的邻接矩阵表示,`closeVertex`存放求得的最小生成树的边。在`prim`函数中,我们先初始化`visited`数组,将序号为0的点标记为已访问,然后不断从已访问的点中找到与未访问的点中权值最小的边,将其加入最小生成树中。最后输出最小生成树的边及其权值之和。
阅读全文