c语言实现普里姆算法求最小生成树

普里姆（Prim）算法是一种用于求解最小生成树的贪心算法。下面是使用C语言实现普里姆算法的示例代码：

#include <stdio.h>
#include <stdbool.h>

#define INF 0x3f3f3f3f
#define MAX_N 100

int n; // 点的数量
int m[MAX_N][MAX_N]; // 图的邻接矩阵
int dis[MAX_N]; // 到集合S的最短距离
bool vis[MAX_N]; // 是否已经加入集合S

void prim()
{
    // 初始化
    for (int i = 0; i < n; i++)
    {
        dis[i] = INF;
        vis[i] = false;
    }
    dis[0] = 0; // 从第一个点开始构建最小生成树

    // 构建最小生成树
    for (int i = 0; i < n; i++)
    {
        int u = -1, min_dis = INF;
        for (int j = 0; j < n; j++)
        {
            if (!vis[j] && dis[j] < min_dis)
            {
                u = j;
                min_dis = dis[j];
            }
        }
        if (u == -1) break; // 无法继续扩展最小生成树

        vis[u] = true;
        for (int v = 0; v < n; v++)
        {
            if (!vis[v] && m[u][v] < dis[v])
            {
                dis[v] = m[u][v];
            }
        }
    }
}

int main()
{
    scanf("%d", &n);

    // 读入图的邻接矩阵
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &m[i][j]);
        }
    }

    prim(); // 求解最小生成树

    // 输出最小生成树的边权之和
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += dis[i];
    }
    printf("%d\n", sum);

    return 0;
}

上述代码中，`m`是图的邻接矩阵，`dis`是到集合S的最短距离，`vis`表示是否已经加入集合S。`prim`函数首先进行初始化，然后从第一个点开始构建最小生成树。每次找到距离集合S最近的点u，将其加入集合S，并更新其相邻的点v到集合S的最短距离。最后输出最小生成树的边权之和即可。