用C语言实现以无向网表示n个城市之间的通信网络计划,其中顶点表示城市,边上的权表示工程造价。请设计程序求出该通信网络总工程造价最低的建设方案
时间: 2024-02-05 18:12:41 浏览: 74
在n个城市建设通信网络,只需架设n-1条线路即可。设计算法,求出如果以最低的经济代价建设这个通信网络。
以下是使用Prim算法实现无向图最小生成树的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_N 100 // 最大城市数
#define INF INT_MAX // 无穷大
int n; // 城市数
int G[MAX_N][MAX_N]; // 通信网络的邻接矩阵
int dist[MAX_N]; // 最小生成树到每个点的距离
int visited[MAX_N]; // 是否已经加入最小生成树的标记
int total_cost = 0; // 最小生成树的总造价
void prim(int start) {
// 初始化
for (int i = 0; i < n; i++) {
dist[i] = INF;
visited[i] = 0;
}
dist[start] = 0;
// 循环 n 次,每次加入一个新的点
for (int i = 0; i < n; i++) {
// 找到距离最近的未加入最小生成树的点
int min_dist = INF;
int min_index = -1;
for (int j = 0; j < n; j++) {
if (!visited[j] && dist[j] < min_dist) {
min_dist = dist[j];
min_index = j;
}
}
// 将该点加入最小生成树,并更新其他点到最小生成树的距离
visited[min_index] = 1;
total_cost += dist[min_index];
for (int j = 0; j < n; j++) {
if (!visited[j] && G[min_index][j] < dist[j]) {
dist[j] = G[min_index][j];
}
}
}
}
int main() {
// 读入数据
printf("请输入城市数 n:\n");
scanf("%d", &n);
printf("请输入通信网络的邻接矩阵 G:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &G[i][j]);
}
}
// 求解最小生成树
prim(0);
// 输出结果
printf("最小生成树的总造价为:%d\n", total_cost);
return 0;
}
```
该程序先读入城市数和邻接矩阵,然后使用Prim算法求解最小生成树,并输出最小生成树的总造价。其中,`prim()`函数实现了Prim算法的核心部分,每次找到距离最近的未加入最小生成树的点,并将该点加入最小生成树,同时更新其他点到最小生成树的距离。
阅读全文