最小生成树prim算法的代码c

Prim算法是一种用于求解无向加权图中最小生成树的贪心算法。下面是一个简单的C语言版本的Prim算法实现：

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

#define V 9 // 图的顶点数

int minDistance(int dist[], bool sptSet[])
{
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;

    return min_index;
}

void primMST(int graph[V][V], int src)
{
    int dist[V]; // 存储从src到其他顶点的距离
    bool sptSet[V]; // 标记数组，true表示顶点已加入最小生成树，false表示未加入

    // 初始化距离数组
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;

    // 设置源节点的距离为0
    dist[src] = 0;

    // 边集初始化为邻接矩阵的一个副本
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++)
            if (graph[i][j] != 0 && !sptSet[j])
                dist[j] = min(dist[j], graph[i][j]);
    }

    sptSet[src] = true;

    while (true) {
        int u = minDistance(dist, sptSet);
        
        if (u == V - 1) break; // 如果所有顶点都已加入，则结束

        printf("Adding edge %d -> %d with weight %d\n", src, u, dist[u]);

        // 更新与u相邻未加入的顶点的距离
        for (int v = 0; v < V; v++)
            if (!sptSet[v] && graph[u][v] != 0)
                dist[v] = min(dist[v], graph[u][v]);

        sptSet[u] = true; // 将u标记为已加入最小生成树
    }
}

int main()
{
    int graph[V][V] = { /* 图的邻接矩阵在这里 */ }; // 输入实际的图数据
    int src = 0; // 源顶点

    primMST(graph, src);

    return 0;
}

这个代码首先创建了一个二维数组`dist`来存储边的距离，并设置`sptSet`数组表示哪些顶点已经添加到了最小生成树中。接着，在主循环中不断寻找当前未加入树的最近顶点，并更新与之相连的未加入顶点的距离。当所有的顶点都加入后，算法结束。