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

一、什么是 Prim 算法？

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

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

二、算法思想与步骤

Prim 算法的核心是 “从顶点出发，逐步扩张生成树” 的贪心策略：先选定一个起始顶点作为初始生成树，然后每次从 “生成树外部的顶点” 中，选择一条与生成树连接的权值最小的边，将该外部顶点纳入生成树中；重复此过程，直到所有顶点都被纳入生成树（此时恰好选择了 n-1 条边，满足无环且连通的最小生成树条件）。

核心思想拆解

贪心本质：每次决策只关注 “当前最优”—— 即当前能连接生成树与外部顶点的所有边中，选权值最小的那条，无需考虑后续步骤，最终能导出全局最优的最小生成树。
数据依赖：算法需通过两个辅助数组记录关键信息（对应代码中的 lowcost 和 adjvex）：
- lowcost[]：存储 “生成树到每个外部顶点的最小边权”（若顶点已在生成树中，值为 0，作为标记）。
- adjvex[]：存储 “与外部顶点构成最小边的生成树内顶点”（即记录这条最小边在生成树中的另一端）。

三、代码实现

#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 个空间，与顶点数线性相关。

五、核心算法分析

先明确前提：代码对应的图

顶点：A (0)、B (1)、C (2)（括号里是数组索引）

边权：A-B=6，A-C=1，B-C=5（邻接矩阵 G.arcs 里的值）

逐段拆解代码（结合具体数值）

1. 变量定义

int lowcost[MAX_VERTEX_NUM];  // 存“已连通区域”到各顶点的最小权值（0表示已连通）
int adjvex[MAX_VERTEX_NUM];   // 存“各顶点”通过哪个已连通顶点连接（记录连接点）
int i, j, k, min;

对咱们的图来说，只用 lowcost[0]、lowcost[1]、lowcost[2]（对应 A、B、C），其他 97 个位置不用管。

2. 初始化（从 A (0) 开始）

for (i = 0; i < G.vexnum; i++) {  // G.vexnum=3（3个顶点）
    lowcost[i] = G.arcs[0][i];    // 初始权值 = A到各顶点的直接权值
    adjvex[i] = 0;                // 初始连接点都是A(0)
}
lowcost[0] = 0;  // 标记A已加入连通区域

循环执行后：

lowcost[0] = G.arcs[0][0] = INT_MAX → 但马上被 lowcost[0] = 0 覆盖（A 已连通）

lowcost[1] = G.arcs[0][1] = 6（A 到 B 的权值）

lowcost[2] = G.arcs[0][2] = 1（A 到 C 的权值）

adjvex[0] = 0，adjvex[1] = 0，adjvex[2] = 0（B、C 暂时都通过 A 连接）
此时 lowcost 状态：[0, 6, 1]（A 已连通，B 的最小权值 6，C 的最小权值 1）

3. 构建生成树（需要 3-1=2 条边，循环 2 次）

for (i = 1; i < G.vexnum; i++) {  // i=1和i=2（两次循环）

第一次循环（i=1，选第一条边）

// 1. 找“未连通”且权值最小的顶点k
min = INT_MAX;  // 初始设为无穷大
for (j = 0; j < G.vexnum; j++) {
    if (lowcost[j] != 0 && lowcost[j] < min) {  // 未连通（≠0）且权值更小
        min = lowcost[j];
        k = j;
    }
}

遍历 j=0,1,2：
- j=0：lowcost[0]=0（已连通，跳过）
- j=1：lowcost[1]=6 ≠0，6 < INT_MAX → min=6，k=1
- j=2：lowcost[2]=1 ≠0，1 < 6 → min=1，k=2
  结果：k=2（选 C 顶点）

// 2. 输出边：连接点是adjvex[k]（A），新顶点是k（C）
printf("边：%c-%c，权重：%d\n", G.vexs[0], G.vexs[2], 1);  // 输出 A-C，权重1

// 3. 标记C已连通
lowcost[2] = 0;  // 此时 lowcost 状态：[0, 6, 0]

// 4. 更新未连通顶点（只有B(1)）的最小权值
for (j = 0; j < G.vexnum; j++) {
    if (lowcost[j] != 0 && G.arcs[k][j] < lowcost[j]) {  // k=2（C）
        lowcost[j] = G.arcs[k][j];
        adjvex[j] = k;
    }
}

遍历 j=0,1,2：
- j=0：lowcost[0]=0（已连通，跳过）
- j=1：lowcost[1]=6 ≠0，且 G.arcs[2][1]=5 < 6 → 更新：
  lowcost[1] = 5，adjvex[1] = 2（B 现在通过 C 连接更便宜）
- j=2：lowcost[2]=0（已连通，跳过）
  结果：lowcost 变为 [0, 5, 0]，adjvex[1]=2

第二次循环（i=2，选第二条边）

// 1. 找“未连通”且权值最小的顶点k
min = INT_MAX;
for (j = 0; j < G.vexnum; j++) {
    if (lowcost[j] != 0 && lowcost[j] < min) {
        min = lowcost[j];
        k = j;
    }
}

遍历 j=0,1,2：
- j=0 和 j=2：lowcost 为 0（已连通）
- j=1：lowcost[1]=5 ≠0 → min=5，k=1（选 B 顶点）

// 2. 输出边：连接点是adjvex[k]=2（C），新顶点是k=1（B）
printf("边：%c-%c，权重：%d\n", G.vexs[2], G.vexs[1], 5);  // 输出 C-B，权重5

// 3. 标记B已连通
lowcost[1] = 0;  // 此时 lowcost 状态：[0, 0, 0]（所有顶点已连通）

// 4. 更新未连通顶点（已没有，循环无意义）

循环结束

此时 3 个顶点都已连通，输出两条边，完成最小生成树。

目录CONTENT

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