Prim

yyycj · 2025-08-04 17:01:39 · 算法·理论

Prim 也是一种求生成树的算法，它与 Dijkstra 的写法基本相同，只是将更新距离从求和变成了取最小值，并且答案为每次最小距离的和，以及多了一些判断。

代码：

int prim(int n, int s) {
    memset(dis, INT_INF, sizeof dis);
    dis[s] = 0;
    int res = 0;
    for (int i = 1; i <= n; i++) {
        int u = -1;
        for (int j = 1; j <= n; j++) {
            if (vis[j]) continue;
            if (u == -1 || dis[u] > dis[j]) u = j;
        }
        vis[u] = true;
        if (i != 1 && dis[u] == INT_INF) return -1;
        if (i != 1) res += dis[u];
        for (node j : vec[u]) dis[j.p] = min(dis[j.p], j.w);
    }
    return res;
}

Prim 写法为 O(N^{2}) 级别，但实际上还有 O(M \log M) 的堆优化版本，但可以由常数更小的 Kruskal 替代。