017-Prim算法-贪心-《算法设计技巧与分析》M.H.A学习笔记
发布时间：2020-12-13 21:09:45 所属栏目：PHP教程 来源：网络整理
导读：基本思路： 定义结点集合U,V (U表示已选择加入MST的结点集合,V表示未选) 1.任选1个结点加入U 2.选择1条边权最小的边，他的两个结点分别属于U,V，并把属于V的那个结点加入U 3.重复履行2直到V空 伪代码： C 代码： int g[mnx][mnx];int n,m;int d[mnx];// 朴素
基本思路：定义结点集合U,V (U表示已选择加入MST的结点集合,V表示未选) 1. 任选1个结点加入U 2. 选择1条边权最小的边，他的两个结点分别属于U,V，并把属于V的那个结点加入U 3. 重复履行2直到V空
伪代码：
C++代码：int g[mnx][mnx];
int n,m;
int d[mnx];
// 朴素 prim,复杂度O(|V|^2) |V|:点数， |E|:边数
int prim() {
memset(d,0x3f,sizeof d); //初始化
int ret = d[1] = 0; // 先把d[1]弄成0
for(int i = 1; i <= n; ++i) {
int u = ⑴;
for(int j = 1; j <= n; ++j) //找到d[u]最小的1个u
if((u == ⑴ || d[u] > d[j]) && d[j] != ⑴)
u = j;
ret += d[u];
d[u] = ⑴;
for(int j = 1; j <= n; ++j) // 更新和u邻接的节点的d[j]值
d[j] = min(d[j],g[u][j]);
}
return ret;
}
算法分析：主要耗费在查找边权最小的边，这1步的2重循环耗费Θ(n2)，所以算法的时间复杂度为Θ(n2)。
堆优化改进：我们用小顶堆来完成查找最小边，和Dijkstra算法1样，算法共进行了n⑴次插入、n⑴次删除、m-n+1次Siftup运算。总的时间复杂度为O（mlogn）。
伪代码：
C++代码：int fst[mnx],nxt[mxe],cost[mxe],to[mxe],e;
void init() {
memset(fst,⑴,sizeof fst);
e = 0;
}
void add(int u,int v,int c) {
to[e] = v,nxt[e] = fst[u],cost[e] = c,fst[u] = e++;
}
struct node {
int u,dis;
node(int u,int dis):u(u),dis(dis) {}
bool operator < (const node &b) const {
return dis > b.dis;
}
};
//堆优化， 复杂度O(|E|log|V|),稠密图时比较慢
int primHeap() {
memset(d,sizeof d);
d[1] = 0;
priority_queue<node> q;
q.push(node(1,0)); // 先选定第1个节点
int ret = 0;
while(!q.empty()) {
int u = q.top().u;
int dd = q.top().dis;
q.pop();
if(d[u] != dd) continue; // 如果是被更新之前的值的话就不取， continue掉
ret += dd;
d[u] = ⑴;
for(int j = fst[u]; ~j; j = nxt[j]) {
int v = to[j],c = cost[j]; // 更新
if(d[v] > c && d[v] != ⑴) {
d[v] = c;
q.push(node(v,c));
}
}
}
return ret;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
相关内容