prim算法c语言代码

Prim算法，也称为最小生成树算法，通常用于求解带权重的无向图中最小生成树的问题。以下是使用C语言的一个基本版本，它采用邻接矩阵来表示图：

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

#define V 9 // 图的顶点数

// 定义邻接矩阵
int graph[V][V] = {
    {0, 2, 0, 6, 0, 0, 2, 0, 7},
    {2, 0, 3, 8, 5, 4, 0, 6, 0},
    {0, 3, 0, 0, 0, 0, 4, 0, 0},
    {6, 8, 0, 0, 7, 0, 0, 4, 0},
    {0, 5, 0, 7, 0, 9, 0, 14, 0},
    {0, 4, 0, 0, 9, 0, 10, 0, 0},
    {2, 0, 4, 0, 0, 10, 0, 9, 10},
    {0, 6, 0, 4, 14, 0, 9, 0, 0},
    {7, 0, 0, 0, 0, 0, 10, 0, 0}
};

// 边优先搜索实现Prim算法
void primMST(int src) {
    int parent[V]; // 存储最短路径的前驱节点
    int dist[V];   // 存储到每个节点的最短距离
    bool visited[V] = {false}; // 标记节点是否已访问过

    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
    }
    dist[src] = 0;

    while (!isFullSet(visited)) {
        int u = findMinDistance(dist, visited); // 找到未访问且距离最小的节点
        visited[u] = true;

        for (int v = 0; v < V; v++) {
            if (!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                parent[v] = u;
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    printf("Edge \tWeight\n");
    for (int i = 1; i < V; i++) {
        printf("%d - %d \t%d\n", parent[i], i, graph[parent[i]][i]);
    }
}

// 辅助函数：检查集合是否已满
bool isFullSet(bool visited[]) {
    for (int i = 0; i < V; i++) {
        if (!visited[i])
            return false;
    }
    return true;
}

// 辅助函数：找到距离最小的未访问节点
int findMinDistance(int dist[], bool visited[]) {
    int minDist = INT_MAX, minIndex = -1;
    for (int v = 0; v < V; v++) {
        if (!visited[v] && dist[v] <= minDist)
            minDist = dist[v], minIndex = v;
    }
    return minIndex;
}

// 主程序
int main() {
    primMST(0);
    return 0;
}

这个C语言代码实现了Prim算法的基本步骤，从源节点开始寻找最小生成树。请注意，这只是一个简化版的示例，实际应用中可能需要处理更复杂的情况，比如动态添加或删除边、使用优先队列等。