深度剖析Prim算法

OESBO • 2025-01-20 14:10 • 编程

一、基础概念

Prim算法是一种用于求解最小生成树的算法。所谓最小生成树，就是一颗包含图上所有节点，且边权值之和最小的连通子图。

对于一张无向图G = (V, E)，其中V为节点集合，E为边集合，任意两个节点之间存在一条边。Prim算法运行于这样的图上，它以任意一个节点为起点开始，不断从当前连通子图中寻找且斜率最小的边，加入新的节点，最终生成最小生成树。

二、Prim算法原理

1. 数据结构

为了方便Prim算法的实现，我们需要准备两个数据结构——

1）dist：记录每个节点与当前最小生成树的最小边权值。初始化为无穷大（除起点外）

2）used：记录每个节点是否已经纳入最小生成树的集合当中，初始化为false。

2. 寻找最小边

在无向连通图中，每个节点有多个可选的连边。对于Prim算法的核心思路，我们可以通过找到当前连通子图能够到达的节点中，边权值最小的那一条边，来实现新节点加入最小生成树。

// 对于每个节点i，记录它和最小生成树联系最近的边
int min_edge[N];

void prim(int st){
    // 将st标记为已经访问的节点
    used[st] = true;
    // 初始化dist数组
    for(int i = 0; i < n; i++){
        dist[i] = i == st ? 0 : INF;
        min_edge[i] = st;
    }
    while(true){
        int v = -1;
        // 在未访问过的节点中选择最小的dist保存在v中
        for(int u = 0; u < n; u++){
            if(!used[u] && (v == -1 || dist[u] < dist[v])){
                v = u;
            }
        }
        if(v == -1) break;
        used[v] = true;
        // 更新最小生成树，利用min_edge数组记录
        for(int u = 0; u  cost[v][u]){
                dist[u] = cost[v][u];
                min_edge[u] = v;
            }
        }
    }
}

3. Prim算法实现

结合上述两步内容，我们就可以实现完整的Prim算法。需要注意的一些问题包括：

1）Prim算法非常依赖于数据结构，因此开发者需要清楚地了解数据结构的特点、优缺点，并合理运用。

2）Prim算法的时间复杂度为O（n2），因此在处理复杂的大数据集时，需要注意优化算法实现。

// Prim算法的完整实现
const int MAXN = 1010;
int cost[MAXN][MAXN]; // 图上两节点之间的边权值
int dist[MAXN];
bool used[MAXN];

int n;

void prim(){
    for(int i = 0; i < n; i++){
        dist[i] = INF;
        used[i] = false;
    }
    dist[0] = 0; //起始点从0开始
    int res = 0;
    while(true){
        int v = -1;
        // 从当前不在最小生成树集合中节点中找到dist最小的节点
        for(int u = 0; u < n; u++){
            if(!used[u] && (v == -1 || dist[u] < dist[v])){
                v = u;
            }
        }
        if(v == -1) break;
        used[v] = true;
        res += dist[v];
        // 根据最小节点和其它点的边权值更新dist
        for(int u = 0; u < n; u++){
            if(used[u]) continue;
            dist[u] = min(dist[u], cost[v][u]);
        }
    }
}

三、总结

Prim算法是一种十分常用而且实用的最小生成树算法，它的关键在于通过不断加入当前最小的边，建立一个连通的最小生成树。虽然算法的时间复杂度为O（n2），但在普通场景下的效率较高。如果遇到复杂的问题，开发者需要合理运用数据结构或者其他优化手段来提升算法的效率。

原创文章，作者：OESBO，如若转载，请注明出处：https://www.506064.com/n/331583.html