以无向网表示n个城市之间的通信网络计划，其中顶点表示城市，边上的权表示工程造价。请设计程序求出该通信网络总工程造价最低的建设方案。程序实现：/*求最小生成树的prim算法描述*/ /*输入网数据*/ printf("输入顶点数和边数："); scanf("%d%d",&n,&e); printf("输入 ON %d 边的起点，终点和权值：",k); scanf("%d%d%d",&i,&j,&w); /*输出最小生成树*/ printf("\n"); printf("最小生成树第%d 分支的两个顶点及权值：%3d%3d%3d\n",j,tree[j].fromvex,tree[j].endvex,tree[j].weight);

以下是使用 Prim 算法求解最小生成树的程序实现：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_VERTICES 100
#define INF INT_MAX

typedef struct {
    int fromvex; // 起点
    int endvex; // 终点
    int weight; // 权值
} Edge;

void prim(int n, int e, int graph[][MAX_VERTICES], Edge tree[]) {
    int visited[MAX_VERTICES] = {0}; // 标记顶点是否被访问
    int min_weight[MAX_VERTICES]; // 记录当前生成树到每个顶点的最小权值
    int i, j, min, u, v;

    // 初始化
    for (i = 1; i <= n; i++) {
        min_weight[i] = INF;
    }

    // 从第一个顶点开始构建生成树
    min_weight[1] = 0;
    visited[1] = 1;

    // 构建 n-1 条边
    for (i = 1; i < n; i++) {
        min = INF;

        // 找到当前生成树和其余顶点之间的最小边
        for (j = 1; j <= n; j++) {
            if (visited[j]) {
                for (v = 1; v <= n; v++) {
                    if (!visited[v] && graph[j][v] < min_weight[v]) {
                        min_weight[v] = graph[j][v];
                    }
                    if (!visited[v] && min > min_weight[v]) {
                        min = min_weight[v];
                        u = j;
                        v = v;
                    }
                }
            }
        }

        // 将最小边添加到生成树中
        tree[i].fromvex = u;
        tree[i].endvex = v;
        tree[i].weight = min;
        visited[v] = 1;
    }
}

int main() {
    int n, e, i, j, w, graph[MAX_VERTICES][MAX_VERTICES];
    Edge tree[MAX_VERTICES];

    // 输入网数据
    printf("输入顶点数和边数：");
    scanf("%d%d", &n, &e);

    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            graph[i][j] = INF;
        }
    }

    for (i = 1; i <= e; i++) {
        printf("输入第%d边的起点，终点和权值：", i);
        scanf("%d%d%d", &j, &w, &w);
        graph[j][w] = w;
        graph[w][j] = w;
    }

    // 输出最小生成树
    prim(n, e, graph, tree);

    printf("\n");
    for (i = 1; i < n; i++) {
        printf("最小生成树第%d分支的两个顶点及权值：%3d%3d%3d\n", i, tree[i].fromvex, tree[i].endvex, tree[i].weight);
    }

    return 0;
}

该程序使用了邻接矩阵来表示图，时间复杂度为 $O(n^2)$，其中 $n$ 表示图的顶点数。