编写prim算法求解最小生成树问题C语言

Prim's算法是一种用于寻找有向图或无向图中带权连接所有顶点的边集合，使其形成的子图恰好包含图中的所有节点，且总权重最小的算法，也称为普里姆生成树算法。在C语言中编写Prim's算法，一般会采用邻接矩阵或邻接表数据结构，以下是一个简单的步骤概述：

1. **初始化**：选择一个起始点作为初始顶点，将其加入到当前生成树中，并记录其邻接权重。

2. **构建贪心选择**：对于每个未加入当前生成树的顶点，计算它与已知生成树中顶点之间的最小权重边。选择这个最小边，并将另一个端点添加到生成树中，更新其邻接权重。

3. **重复**：继续上述过程直到所有的顶点都被添加到生成树中，或者无法找到可以添加的新顶点。

4. **结束**：返回生成的最小生成树及其总权重。

以下是C语言的一个简单示例，这里假设使用邻接矩阵表示图：

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

#define V 9 // 图的顶点数

int min(int a, int b) {
    return a < b ? a : b;
}

// 边的优先级队列（最小堆）
typedef struct Node {
    int data;
    int vertex; // 边对应的顶点
} Node;

int prim(int graph[V][V], int src) {
    int visited[V] = {0}; // 记录是否访问过的顶点
    int parent[V]; // 父亲节点数组
    int dist[V] = {INT_MAX}, minDistance = INT_MAX; // 最小距离和当前最小值

    for (int i = 0; i < V; i++) {
        if (graph[src][i] != INT_MAX && dist[i] > graph[src][i]) {
            dist[i] = graph[src][i];
            parent[i] = src;
        }
    }

    int u = -1; // 当前遍历的顶点
    while (u != -1) {
        u = -1;
        for (int v = 0; v < V; v++) {
            if (!visited[v] && dist[v] < minDistance && graph[u][v] != INT_MAX) {
                if (dist[u] + graph[u][v] < dist[v]) {
                    minDistance = dist[u] + graph[u][v];
                    u = v;
                }
            }
        }
        visited[u] = 1;
    }

    printf("生成树的最小权重: %d\n", minDistance);

    // 输出路径
    printf("路径:\n");
    int curr = u;
    while (curr != -1) {
        printf("%d ", curr);
        curr = parent[curr];
    }
    printf("\n");

    return minDistance;
}

int main() {
    // 初始化图（这里的例子仅适用于小型图，实际应用需处理大型数据结构）
    int graph[V][V] = {
        {0, 4, 0, 0, 0, 0, 0, 8, 0},
        {4, 0, 8, 0, 0, 0, 0, 11, 0},
        {0, 8, 0, 7, 0, 4, 0, 0, 2},
        {0, 0, 7, 0, 9, 14, 0, 0, 0},
        {0, 0, 0, 9, 0, 10, 0, 0, 0},
        {0, 0, 4, 14, 10, 0, 2, 0, 0},
        {0, 0, 0, 0, 0, 2, 0, 1, 6},
        {8, 11, 0, 0, 0, 0, 1, 0, 7},
        {0, 0, 2, 0, 0, 0, 6, 7, 0}
    };

    prim(graph, 0); // 从源节点0开始
    return 0;
}