主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
Prim
最后更新于 2025-08-28 16:28:06
作者
yyycj
分类
算法·理论
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
Prim 也是一种求生成树的算法，它与 Dijkstra 的写法基本相同，只是将更新距离从求和变成了取最小值，并且答案为每次最小距离的和，以及多了一些判断。 代码： ```cpp 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 替代。
正在渲染内容...
点赞
0
收藏
0
