C语言实现Prim算法生成最小生成树

云舒

发布时间：2026-10-14 | 4人浏览过

原创

本文介绍如何使用C/C++语言实现Prim算法来求解无向图的最小生成树。通过邻接矩阵存储权重数据，利用两个数组分别记录当前未加入生成树节点到树中各点的最短距离及对应起点，逐步扩展生成树直至覆盖所有节点。

算法原理概述

Prim算法是构造最小生成树的经典贪心算法。其核心思想是从任意一个顶点开始，将该顶点加入生成树，然后寻找与该顶点集合相邻且权值最小的边，将对应的另一个顶点也加入生成树。重复此过程，直到所有顶点都包含在生成树中为止。

准备条件与数据结构

为了实现该算法，我们需要定义常量来确定最大节点数量和无穷大值（表示无边），并使用二维数组作为邻接矩阵来存储图的连接关系和边权值。

#include 
using namespace std;

#define MAX 100       // 最大节点数
#define MAXCOST 100000 // 无穷大，表示两点间无边

在全局或函数内部声明图的结构：

int graph[MAX][MAX];

第1步：初始化距离与起点记录

假设从节点0开始构建生成树。我们需要两个辅助数组：

lowcost[i]：记录以i为终点的边在当前生成树中的最小权值。若lowcost[i]=0，表示节点i已加入生成树。
mst[i]：记录与节点i相连且在生成树中的那个起点的索引。

操作如下：

遍历所有非起始节点（1至n-1）。
将lowcost[i]初始化为节点0到节点i的直接距离graph[0][i]。
将mst[i]标记为0，表示当前最短边的起点默认为0号节点。
将lowcost[0]设为0，表示0号节点已进入生成树。

第2步：迭代选取最小边并更新

由于n个节点的生成树需要n-1条边，因此进行n-1次循环。每次循环执行以下逻辑：

寻找最小权值边：
在尚未加入生成树的节点（即lowcost[j] != 0）中，找到权值最小的边。记录下该最小权值min和对应的节点索引minid。
输出与累加：
打印这条新加入的边信息：起点mst[minid]+1（代码中调整为人类可读的1-based索引）、终点minid+1以及权值min。同时将min累加到总和sum中。
标记节点加入：
将lowcost[minid]设为0，正式将节点minid加入生成树。
更新距离表：
以新加入的节点minid为跳板，检查它到其他所有未加入节点j的距离。如果graph[minid][j]小于当前的lowcost[j]，则更新lowcost[j]为该新更小权值，并更新mst[j]为minid。

完整源代码实现

以下是包含主函数输入逻辑的完整C/C++代码。注意原代码使用了古老的iostream.h和非标准的void main，现代编译环境建议使用标准C++写法。

#include 
#include 

using namespace std;

#define MAX 100
#define MAXCOST 100000

int graph[MAX][MAX];

// Prim算法核心函数
int Prim(int n) {
    int lowcost[MAX]; // 记录最小权值
    int mst[MAX];     // 记录对应的起点
    int i, j, min, minid, sum = 0;

    // 1. 初始化：从节点0开始
    for (i = 1; i < n; i++) {
        lowcost[i] = graph[0][i];
        mst[i] = 0;
    }
    lowcost[0] = 0; // 标记节点0已加入

    // 2. 迭代处理剩下的 n-1 个节点
    for (i = 1; i < n; i++) {
        min = MAXCOST;
        minid = 0;

        // 找到未加入集合中权值最小的边
        for (j = 1; j < n; j++) {
            if (lowcost[j] < min && lowcost[j] != 0) {
                min = lowcost[j];
                minid = j;
            }
        }

        // 输出生成树的边信息
        cout << "生成树边的起点、终点及权值分别为："
             << mst[minid] + 1 << " " 
             << minid + 1 << " " 
             << min << endl;
        
        sum += min;
        lowcost[minid] = 0; // 标记minid已加入

        // 更新其他节点到生成树的最小距离
        for (j = 1; j < n; j++) {
            if (graph[minid][j] < lowcost[j]) {
                lowcost[j] = graph[minid][j];
                mst[j] = minid;
            }
        }
    }
    return sum;
}

int main() {
    int i, j, m, n_val, cost;

    // 获取节点数
    cout << "请输入该图结点个数：";
    cin >> m;

    // 输入邻接矩阵
    for (i = 0; i < m; i++) {
        for (j = i + 1; j < m; j++) {
            cout << "请输入结点" << i + 1 << "到结点" << j + 1 << "边的权值，若无边则输入MAXCOST(100000):";
            cin >> n_val;
            graph[i][j] = n_val;
            graph[j][i] = n_val; // 无向图对称
        }
        graph[i][i] = MAXCOST; // 自环设为无穷大
    }

    // 计算并输出结果
    cost = Prim(m);
    cout << "最小生成树的权值为：" << cost << endl;

    return 0;
}