C语言最小生成树Prim完整代码

Prim算法是一种用于求解带权重有向图中最小生成树的经典算法。以下是C语言实现Prim算法的基本步骤及一个简单的示例：

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

#define V 9 // 假设我们有一个包含V顶点的图

// 定义邻接矩阵表示图
int graph[V][V];

// 边集合结构体，用于存储边的信息
typedef struct {
    int src; // 源节点
    int dest; // 目标节点
    int weight; // 权重
} Edge;

// 边的比较函数，用于优先队列操作
bool compareEdges(Edge e1, Edge e2) {
    return (e1.weight < e2.weight);
}

// 判断是否已经访问过的标记数组
bool marked[V];

// 最小生成树的核心 Prim 算法
void primMST() {
    // 初始化所有节点为未访问状态
    for(int i = 0; i < V; ++i)
        marked[i] = false;
    
    // 设置第一棵边（通常选择源点到任意节点的最轻边）
    Edge firstEdge;
    firstEdge.src = 0;
    firstEdge.dest = -1;
    firstEdge.weight = INT_MAX;
    Edge minEdge = firstEdge;

    // 构建优先队列并添加第一棵边
    priority_queue<Edge, Edge[], bool (*)(Edge, Edge)> pq(compareEdges);
    pq.push(firstEdge);

    while(!pq.empty()) {
        // 弹出当前最小权值边
        Edge currEdge = pq.top();
        pq.pop();

        // 如果目标节点已访问过，则跳过
        if(currEdge.dest != -1 && marked[currEdge.dest])
            continue;

        // 标记该节点为已访问
        marked[currEdge.dest] = true;

        // 更新最小生成树
        if(currEdge.weight < minEdge.weight) {
            minEdge = currEdge;
            printf("(%d, %d) cost: %d\n", currEdge.src, currEdge.dest, currEdge.weight);
        }

        // 添加邻居边到优先队列
        for(int i = 0; i < V; ++i) {
            if(graph[currEdge.dest][i] != INT_MAX && !marked[i]) {
                Edge newEdge = {currEdge.dest, i, graph[currEdge.dest][i]};
                pq.push(newEdge);
            }
        }
    }
}

int main() {
    // 初始化邻接矩阵（这里仅作为示例，你需要替换为实际的边信息）
    // 例如，graph[i][j]代表从节点i到节点j的边的权重
    // ...

    primMST();
    return 0;
}

这个代码示例展示了如何用Prim算法找到一个无向图的最小生成树。注意，这只是一个基本版本，实际应用中可能需要处理更复杂的情况，如图的动态变化、数据结构的选择等。