c++中如何实现Prim算法_c++ Prim算法实现方法-C++-PHP中文网

c++中如何实现Prim算法_c++ Prim算法实现方法

裘德小鎮的故事

发布： 2025-10-11 13:47:01

原创

195人浏览过

Prim算法用于求解无向加权图的最小生成树，从一个顶点出发，每次选择权重最小的边扩展生成树。使用邻接矩阵适合稠密图，通过lowcost数组和visited数组维护最短距离与访问状态；邻接表结合优先队列适合稀疏图，利用最小堆高效选取最小边。代码实现需初始化起点，循环更新未访问顶点的最短距离，最终累加总权重。注意判断图的连通性，避免不连通情况下的错误结果。

c++中如何实现prim算法_c++ prim算法实现方法

Prim算法用于求解无向加权图的最小生成树（MST），核心思想是从一个起始顶点出发，每次选择与当前生成树相连且权重最小的边，逐步扩展直到包含所有顶点。C++中可以通过邻接矩阵或邻接表结合优先队列来高效实现。

使用邻接矩阵和数组实现（适合稠密图）

当图的边较多时，使用邻接矩阵存储更直观。通过维护一个lowcost数组记录各顶点到当前生成树的最短距离，以及一个visited数组标记是否已加入生成树。

关键步骤：

初始化：从顶点0开始，lowcost[i] = graph[0][i]
循环n-1次，每次找出lowcost中最小且未访问的顶点u
将u加入生成树，累加该边权值
用u更新其他顶点到生成树的最短距离

使用邻接表和优先队列（适合稀疏图）

对于边数较少的图，邻接表+优先队列（最小堆）效率更高。C++中可用priority_queue实现堆结构，自动维护最小边。

立即学习“C++免费学习笔记（深入）”；

法语写作助手

法语助手旗下的AI智能写作平台，支持语法、拼写自动纠错，一键改写、润色你的法语作文。

查看详情

实现要点：

定义边结构体：包含目标顶点和权重
使用vector<vector<pair<int, int>>>存储邻接表
优先队列保存{weight, vertex}，按权重从小到大排序
从任意起点开始，将相邻边加入队列
取出最小边，若终点未访问，则加入生成树并扩展新边

代码示例（邻接矩阵版）

以下是一个基于邻接矩阵的Prim算法实现，假设图是连通的：

#include <iostream>
#include <climits>
using namespace std;

const int MAXN = 100;
int graph[MAXN][MAXN];
bool visited[MAXN];
int lowcost[MAXN];

int prim(int n) {
    fill(lowcost, lowcost + n, INT_MAX);
    fill(visited, visited + n, false);
    
    lowcost[0] = 0;
    int totalWeight = 0;

    for (int i = 0; i < n; i++) {
        int u = -1, minVal = INT_MAX;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && lowcost[j] < minVal) {
                minVal = lowcost[j];
                u = j;
            }
        }

        if (u == -1) break;
        visited[u] = true;
        totalWeight += lowcost[u];

        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] > 0 && graph[u][v] < lowcost[v]) {
                lowcost[v] = graph[u][v];
            }
        }
    }
    return totalWeight;
}

登录后复制