FC07-Prim算法：求无向图的最小生成树

代码实现

// Prim算法：求无向图的最小生成树
// 参数：G - 图的邻接矩阵表示，v - 起始顶点
void prim(MGraph G, int v) {
    // visit数组：标记顶点是否已加入最小生成树
    int visit[maxsize] = {0};

    // lowcost数组：存储各顶点到当前生成树的最小边权值
    int lowcost[G.numver];

    // parent数组：存储最小生成树中各顶点的父节点
    int parent[G.numver];

    // 初始化lowcost和parent数组
    for (int i = 0; i < G.numver; i++) {
        lowcost[i] = INT16_MAX;  // 初始时所有顶点到生成树的距离设为无穷大
        parent[i] = -1;          // 初始时所有顶点的父节点设为-1（表示无父节点）
    }

    // 起始顶点到生成树的距离设为0
    lowcost[v] = 0;

    // 循环G.numver-1次，每次选择一个顶点加入生成树
    for (int i = 0; i < G.numver - 1; i++) {
        // 步骤1：在未加入生成树的顶点中找到距离最小的顶点
        int pos, min_val = INT16_MAX;
        for (int j = 0; j < G.numver; j++) {
            if (lowcost[j] < min_val && visit[j] == 0) {
                pos = j;           // 记录距离最小的顶点位置
                min_val = lowcost[j]; // 记录最小距离值
            }
        }

        // 将找到的顶点加入最小生成树
        visit[pos] = 1;

        // 步骤2：更新其他顶点到生成树的最小距离
        for (int j = 0; j < G.numver; j++) {
            // 如果顶点j未加入生成树 且 通过顶点pos到j的距离更小
            if (lowcost[j] > G.Edge[pos][j] && !visit[j]) {
                lowcost[j] = G.Edge[pos][j]; // 更新最小距离
                parent[j] = pos;             // 更新父节点
            }
        }
    }

    // 输出最小生成树的边和权重
    for (int i = 0; i < G.numver; i++) {
        printf("%d_%d:%d ", i, parent[i], lowcost[i]);
    }
}

---

代码逻辑解析

1. Prim算法基本思想

• 从任意一个顶点开始构建最小生成树
• 每次选择一个距离当前生成树最近的顶点加入生成树
• 重复此过程直到所有顶点都加入生成树

2. 关键数据结构

• visit数组：标记顶点是否已加入最小生成树
• lowcost数组：记录各顶点到当前生成树的最小边权值
• parent数组：记录最小生成树中各顶点的父节点（用于构建树结构）

3. 算法步骤详解

步骤1：初始化

// 初始化所有顶点到生成树的距离为无穷大
for (int i = 0; i < G.numver; i++) {
    lowcost[i] = INT16_MAX;
    parent[i] = -1;
}
lowcost[v] = 0; // 起始顶点距离设为0

步骤2：主循环（执行n-1次）

for (int i = 0; i < G.numver - 1; i++) {
    // 选择距离最小的顶点
    // 更新其他顶点的距离
}

步骤3：选择最近顶点

int pos, min_val = INT16_MAX;
for (int j = 0; j < G.numver; j++) {
    if (lowcost[j] < min_val && visit[j] == 0) {
        pos = j;
        min_val = lowcost[j];
    }
}
visit[pos] = 1; // 加入生成树

步骤4：更新距离

for (int j = 0; j < G.numver; j++) {
    if (lowcost[j] > G.Edge[pos][j] && !visit[j]) {
        lowcost[j] = G.Edge[pos][j];
        parent[j] = pos;
    }
}

---

时间复杂度分析

1. 外层循环

• 执行 G.numver - 1 次，即 O(V) 次

2. 内层循环

• 找最小顶点：O(V) 时间
• 更新距离：O(V) 时间

3. 总体时间复杂度

• O(V) × [O(V) + O(V)] = O(V²)
• 其中 V 是顶点数

4. 优化可能性

• 使用优先队列（最小堆）可以优化到 O((V + E) log V)
• 使用斐波那契堆可以优化到 O(E + V log V)

---

空间复杂度分析

1. 额外数组空间

• visit[]：O(V)
• lowcost[]：O(V)
• parent[]：O(V)

2. 局部变量

• 常量级别的额外空间

3. 总体空间复杂度

O(V)，其中 V 是顶点数

---

较难理解部分的说明

1. lowcost数组的含义

// lowcost[i] 的含义：
// 顶点 i 到当前已构建的最小生成树的最短距离
// 即：从已加入生成树的顶点到顶点 i 的所有边中权值最小的那条边的权值

// 举例：
// lowcost[3] = 5 表示：从生成树中的某个顶点到顶点3的最短边权值为5

2. 图解说明

假设无向图如下：

    1
  / | \
2   |   4
  \ | /
    3
边权值：1-2=2, 1-3=3, 1-4=1, 2-3=4, 3-4=5

邻接矩阵表示：

    0  1  2  3
0   0  2  3  1  (顶点1到各顶点的距离)
1   2  0  4  ∞  (顶点2到各顶点的距离)
2   3  4  0  5  (顶点3到各顶点的距离)
3   1  ∞  5  0  (顶点4到各顶点的距离)

Prim算法执行过程（从顶点0开始）：

初始状态：
visit = [0,0,0,0]
lowcost = [0,2,3,1]
parent = [-1,-1,-1,-1]

第1轮：选择顶点3(min=1)
visit = [1,0,0,1]
lowcost = [0,2,3,1]
parent = [-1,0,0,0]

第2轮：选择顶点1(min=2)  
visit = [1,1,0,1]
lowcost = [0,2,3,1]
parent = [-1,0,0,0]

第3轮：选择顶点2(min=3)
visit = [1,1,1,1]
lowcost = [0,2,3,1]
parent = [-1,0,0,0]

最终最小生成树边：0-3(权值1), 0-1(权值2), 0-2(权值3) 总权值：1 + 2 + 3 = 6

---

延伸知识点

1. Kruskal算法对比

// Kruskal算法（基于边的贪心策略）
void kruskal(MGraph G) {
    // 1. 将所有边按权值排序
    // 2. 按权值从小到大选择边
    // 3. 如果选择的边不会形成环，则加入生成树
    // 4. 重复直到选择n-1条边
}

特性	Prim算法	Kruskal算法
基本思想	基于顶点	基于边
时间复杂度	O(V²)	O(E log E)
适用场景	稠密图	稀疏图
空间复杂度	O(V)	O(E)

2. 优化版本 - 使用优先队列

// 使用最小堆优化的Prim算法
void primOptimized(MGraph G, int v) {
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    vector<bool> inMST(G.numver, false);
    vector<int> key(G.numver, INT_MAX);
    vector<int> parent(G.numver, -1);

    key[v] = 0;
    pq.push({0, v});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (inMST[u]) continue;
        inMST[u] = true;

        for (int i = 0; i < G.numver; i++) {
            if (G.Edge[u][i] && !inMST[i] && G.Edge[u][i] < key[i]) {
                key[i] = G.Edge[u][i];
                parent[i] = u;
                pq.push({key[i], i});
            }
        }
    }
}

3. 实际应用场景

• 网络设计：通信网络、电力网络的最小成本设计
• 道路规划：城市道路系统建设的最小成本方案
• 电路设计：电子电路板的最小布线方案
• 聚类分析：数据挖掘中的层次聚类算法
• 图像分割：计算机视觉中的图像分割算法

4. 最小生成树的性质

// 验证是否为最小生成树
bool isMST(MGraph G, int parent[]) {
    int edgeCount = 0;
    int totalWeight = 0;

    // 统计边数和总权值
    for (int i = 0; i < G.numver; i++) {
        if (parent[i] != -1) {
            edgeCount++;
            totalWeight += G.Edge[i][parent[i]];
        }
    }

    // 最小生成树应有n-1条边
    return (edgeCount == G.numver - 1);
}

5. 相关算法扩展

// 次小生成树算法
int secondMST(MGraph G) {
    // 1. 先求最小生成树
    // 2. 对每条MST中的边，暂时删除
    // 3. 重新求MST，记录最小值
    // 4. 恢复删除的边
}

// 最小生成树计数
int countMST(MGraph G) {
    // 使用矩阵树定理或Kirchhoff定理
    // 基于图的拉普拉斯矩阵的代数余子式
}

Prim算法体现了贪心策略在图论中的经典应用，通过局部最优选择达到全局最优解，是计算机科学中重要的图算法之一。