记录 Prim 算法：从原理到实现(**普里姆算法**)

一、什么是 Prim 算法？

Prim 算法是一种用于求解最小生成树（Minimum Spanning Tree, MST） 的贪心算法。所谓最小生成树，就是在一个连通的带权无向图中，找出一个包含所有顶点、仅用 n-1 条边（n 为顶点数）连接，且所有边的总权值最小的子图。

简单说，它的核心目标是：用最少的 “成本”（边的总权值）把所有顶点 “串” 起来，且保证串起来的结构没有环。

二、算法思想与步骤

三、代码实现

#include <stdio.h>
#include <limits.h>  // 用于INT_MAX表示无穷大

#define MAX_VERTEX_NUM 100  // 最大顶点数
typedef char VertexType;    // 顶点数据类型（如字符）
typedef int EdgeType;       // 边权重类型（整数）

// 图的邻接矩阵存储结构
typedef struct {
    VertexType vexs[MAX_VERTEX_NUM];  // 顶点表
    EdgeType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 邻接矩阵（边权重）
    int vexnum, arcnum;  // 顶点数、边数
} MGraph;

// 初始化图（根据实际需求填充顶点和边，示例中简化）
void InitGraph(MGraph* G) {
    // 此处仅为示例：假设有3个顶点，边权重如下
    G->vexnum = 3;
    G->arcnum = 3;
    // 顶点数据（A,B,C）
    G->vexs[0] = 'A';
    G->vexs[1] = 'B';
    G->vexs[2] = 'C';
    // 邻接矩阵初始化（INF表示无边）
    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j < G->vexnum; j++) {
            G->arcs[i][j] = INT_MAX;  // 初始化为无穷大
        }
    }
    // 填充边（无向图，对称）
    G->arcs[0][1] = G->arcs[1][0] = 6;  // A-B权重6
    G->arcs[0][2] = G->arcs[2][0] = 1;  // A-C权重1
    G->arcs[1][2] = G->arcs[2][1] = 5;  // B-C权重5
}

// Prim算法：从第0个顶点开始构建最小生成树
void Prim(MGraph G) {
    int lowcost[MAX_VERTEX_NUM];  // 存储当前生成树到各顶点的最小边权
    int adjvex[MAX_VERTEX_NUM];   // 存储最小边对应的生成树中的顶点
    int i, j, k, min;

    // 初始化：从顶点0开始
    for (i = 0; i < G.vexnum; i++) {
        lowcost[i] = G.arcs[0][i];  // 初始边权为顶点0到各顶点的权重
        adjvex[i] = 0;              // 所有最小边暂时对应顶点0
    }
    lowcost[0] = 0;  // 顶点0加入生成树（标记为已加入，边权设为0）

    // 构建生成树（共需vexnum-1条边）
    for (i = 1; i < G.vexnum; i++) {
        // 1. 找未加入生成树中，lowcost最小的顶点k
        min = INT_MAX;
        for (j = 0; j < G.vexnum; j++) {
            if (lowcost[j] != 0 && lowcost[j] < min) {  // 未加入且边权更小
                min = lowcost[j];
                k = j;  // 记录顶点k
            }
        }

        // 2. 输出选中的边（adjvex[k] -> k）及权重
        printf("边：%c-%c，权重：%d\n",
            G.vexs[adjvex[k]], G.vexs[k], lowcost[k]);

        // 3. 将顶点k加入生成树（标记lowcost[k]为0）
        lowcost[k] = 0;

        // 4. 更新lowcost和adjvex：以k为中介，更新未加入顶点的最小边权
        for (j = 0; j < G.vexnum; j++) {
            // 若顶点j未加入，且k到j的边权 < 当前lowcost[j]
            if (lowcost[j] != 0 && G.arcs[k][j] < lowcost[j]) {
                lowcost[j] = G.arcs[k][j];  // 更新最小边权
                adjvex[j] = k;              // 更新对应生成树顶点为k
            }
        }
    }
}

int main() {
    MGraph G;
    InitGraph(&G);
    printf("最小生成树的边为：\n");
    Prim(G);
    return 0;
}

四、时空复杂度分析

时间复杂度

• 邻接矩阵存储：O(n²)

  解释：外层循环 n-1 次（选 n-1 条边），每次内层循环两次（一次找最小权值，一次更新数组），每次内层循环都是 O (n)，总操作次数约为 2n²，忽略常数后为 O (n²)。

• 邻接表存储：基础实现仍是 O (n²)；若用堆优化找最小权值的过程，可降至 O (e log n)（e 为边数）。

空间复杂度

• O(n)
  解释：主要开销是两个辅助数组 lowcost和 adjvex，各占用 n 个空间，与顶点数线性相关。