本文共 2745 字，大约阅读时间需要 9 分钟。
Prim算法是一种求最小生成树（MST）的高效方法，其核心思想与Dijkstra算法中的松弛操作相似。Prim算法通过逐步松弛边权，最终构建连接所有节点的最小权重树。
Prim算法选择一个起始点（通常随机选取或固定为节点1），然后依次松弛与该松弛点相连的节点。具体步骤如下：
Prim算法的贪心机制在于每次选择距离当前松弛点最近的节点，更新其最短边。这种机制确保了每次松弛操作都选择了当前可用最短边，从而逐步构建MST。
以下是Prim算法在邻接矩阵和邻接表两种数据结构下的实现示例。
#include#include #include #include using namespace std;typedef int insert;const int INF = 0x3f3f3f3f;const int N = 5000 + 100;insert edges[N][N], dis[N], vis[N];insert n, m, x, y, z;long long sum;void value() { memset(edges, INF, sizeof(edges)); memset(dis, INF, sizeof(dis)); for (int i = 1; i <= m; ++i) { cin >> x >> y >> z; if (edges[x][y] > z || edges[y][x] > z) { edges[x][y] = z; edges[y][x] = z; } } dis[1] = 0;}void prim() { for (int k = 1; k <= n; ++k) { insert minn = INF, pos; for (int i = 1; i <= n; ++i) { if (!vis[i] && dis[i] < minn) { minn = dis[i]; pos = i; } } vis[pos] = true; for (int i = 0; i < n; ++i) { if (!vis[i] && dis[i] > edges[pos][i]) { dis[i] = edges[pos][i]; } } }}int main() { cin >> n >> m; value(); prim(); for (int i = 1; i <= n; ++i) { sum += dis[i]; } cout << "最小生成树的总权值"; for (int i = 1; i <= n; ++i) { cout << " " << dis[i]; } cout << endl;}
#include#include #include #include #include using namespace std;typedef int insert;const int INF = 0x3f3f3f3f;const int N = 2e5 + 200;insert n, m, x, y, z, dis[N], sum, startpoint;bool vis[N];vector vt[N];struct Node { int to, w;};void initial_value() { memset(dis, INF, sizeof(dis)); for (int i = 1; i <= m; ++i) { cin >> x >> y >> z; Node node; node.to = y; node.w = z; vt[x].push_back(node); node.to = x; vt[y].push_back(node); } dis[startpoint] = 0;}void prim() { for (int k = 1; k <= n; ++k) { insert minn = INF, pos; for (int i = 1; i <= n; ++i) { if (!vis[i] && dis[i] < minn) { minn = dis[i]; pos = i; } } vis[pos] = true; for (auto& neighbor : vt[pos]) { if (!vis[neighbor.to] && dis[neighbor.to] > neighbor.w) { dis[neighbor.to] = neighbor.w; } } }}int main() { cin >> n >> m >> startpoint; initial_value(); prim(); sum = 0; for (int i = 1; i <= n; ++i) { sum += dis[i]; } for (int i = 1; i <= n; ++i) { cout << "--" << dis[i] << " "; } cout << endl;}
Prim算法通过松弛操作和贪心机制高效求解MST，适用于稀疏图。其核心在于每次选择当前最近的未访问节点，逐步扩展MST。代码实现采用邻接矩阵或邻接表，根据实际需求选择合适的数据结构。
转载地址：http://gmxfk.baihongyu.com/