用C语言写出最小生成树

最小生成树是一个图的一种生成树，它的所有边权值之和最小。下面是使用 Prim 算法和邻接矩阵实现最小生成树的 C 代码：

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

// 定义无限大，用于初始化距离数组
#define INF INT_MAX

// 定义图的最大节点数
#define MAX_NODES 100

// 定义图的邻接矩阵
int graph[MAX_NODES][MAX_NODES];

// 定义节点数和边数
int numNodes, numEdges;

// Prim 算法实现最小生成树
void primMST() {
    // 定义节点是否被访问过的数组和距离数组
    int visited[MAX_NODES] = {0};
    int distance[MAX_NODES];

    // 初始化距离数组，除起点外均为无限大
    for (int i = 0; i < numNodes; i++) {
        distance[i] = INF;
    }
    distance[0] = 0;

    // 计算最小生成树的总权值
    int totalWeight = 0;

    // 遍历所有节点
    for (int i = 0; i < numNodes - 1; i++) {
        // 找到未访问过的节点中距离最小的节点
        int minDistance = INF;
        int minIndex = -1;
        for (int j = 0; j < numNodes; j++) {
            if (!visited[j] && distance[j] < minDistance) {
                minDistance = distance[j];
                minIndex = j;
            }
        }

        // 将该节点标记为已访问
        visited[minIndex] = 1;

        // 将该节点与其他未访问过的节点的距离更新到距离数组中
        for (int j = 0; j < numNodes; j++) {
            if (!visited[j] && graph[minIndex][j] < distance[j]) {
                distance[j] = graph[minIndex][j];
            }
        }

        // 将该节点与其父节点的边的权值累加到总权值中
        totalWeight += minDistance;
    }

    // 输出最小生成树的总权值
    printf("Total weight of MST: %d\n", totalWeight);
}

int main() {
    // 读取节点数和边数
    scanf("%d%d", &numNodes, &numEdges);

    // 初始化邻接矩阵
    for (int i = 0; i < numNodes; i++) {
        for (int j = 0; j < numNodes; j++) {
            graph[i][j] = INF;
        }
    }

    // 读取边的信息，并将其存储在邻接矩阵中
    for (int i = 0; i < numEdges; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        graph[u][v] = graph[v][u] = w;
    }

    // 计算最小生成树
    primMST();

    return 0;
}

这里使用了 Prim 算法，它的时间复杂度为 O(n^2)。如果使用堆优化后的 Prim 算法或者 Kruskal 算法，时间复杂度可以降为 O(mlogn)。