网站建设常用视频格式,素材图库,自己做网站seo,通州顺德网站建设注#xff1a;本文算法使用链式前向星数据结构实现。学习链接#xff1a;链式前向星-学习笔记 一、Prim算法 普通prim算法模板#xff1a; //用前向星录数据的时候记得把head初始化为-1
fill(dist,distLEN,MAX);
memset(vis,0,sizeof vis);
int ans0;
dist[1]0; //如…注本文算法使用链式前向星数据结构实现。学习链接链式前向星-学习笔记 一、Prim算法 普通prim算法模板 //用前向星录数据的时候记得把head初始化为-1
fill(dist,distLEN,MAX);
memset(vis,0,sizeof vis);
int ans0;
dist[1]0; //如果题目要求输出最小生成树就把题目要求的源点s的dist设为0
while(1){ //如果题目要求判断最小生成树是否能覆盖所有边这个循环条件应该是in;while(n--)循环n次。 int u-1,dMAX;for(i1;iN;i){if(!vis[i] dist[i]d){ui;ddist[i];}}if(u0) break; //如果题目要求判断最小生成树是否能覆盖所有边出现这样的情况说明不能覆盖所有边。 vis[u]1;ansdist[u];for(ihead[u];~i;imp[i].next){ //用前向星遍历u点所有的后继。i是各个后继点在mp的下标mp[to]是u的各个后继点 int tomp[i].to;if(!vis[to] mp[i].wdist[to]){//如果这个点没有被访问过、并且u-v的路径比点集S到v的路径要短则更新。 dist[to]mp[i].w;}}
}
O(%d\n,ans); 堆优化的prim算法 堆结构 struct cmp{bool operator () (int a,int b){return dist[a]dist[b];}
};
priority_queueint,vectorint,cmp pq; 算法代码 int ans0;
dist[1]0;
pq.push(1);
while(!pq.empty()){int upq.top();pq.pop();if(vis[u]) continue;vis[u]1;ansdist[u];for(ihead[u];~i;imp[i].next){int tomp[i].to;if(!vis[to] mp[i].wdist[to]){dist[to]mp[i].w;pq.push(to);}}
}
O(%d\n,ans); 二、Kruskal算法 1.建立边表数据结构 typedef struct edge{int u,v,w;edge(int u0,int v0,int w0):u(u),v(v),w(w){}bool operator (const edge obj) const{return wobj.w;}
}edge;
edge mp[LEN*LEN]; 2.编写并查集模板以下代码没有写合并的Union操作。这个操作在主代码执行的时候已经实现 int fa[LEN];
int init(){int i;FF(i,LEN) fa[i]i;
}
int findFa(int x){if(xfa[x]) return x;int rx;while(r!fa[r]){rfa[r];}int tx;while(x!fa[x]){tfa[x];fa[x]r;xt;}return r;
} 3.编写主代码 sort(mp,mpcnt);
FF(i,cnt){int fa_ufindFa(mp[i].u);int fa_vfindFa(mp[i].v);if(fa_u!fa_v){ansmp[i].w;fa[fa_u]fa_v;edge_cnt;if(edge_cntN-1) break;}
}
O(%d\n,ans); 注意 ①边表的范围要开大因为边的数目可能是顶点数目的平方准确说有向图边树EN*(N-1) ②Prim算法在录边的数据的时候因为是无向图一条边要录成两条。Kruskal就没有这种必要了。 ③各种初始化代码比如并查集的init() 要注意加上。 打个OJ测试一下吧 OJ链接还是畅通工程 AC代码 #include stdio.h
#include memory.h
#include math.h
#include string
#include vector
#include set
#include stack
#include queue
#include algorithm
#include map#define I scanf
#define OL puts
#define O printf
#define F(a,b,c) for(ab;ac;a)
#define FF(a,b) for(a0;ab;a)
#define FG(a,b) for(ab-1;a0;a--)
#define LEN 1010
#define MAX (130)-1
#define V vectorintusing namespace std;int N;
int fa[LEN];
int init(){int i;FF(i,LEN) fa[i]i;
}
int findFa(int x){if(xfa[x]) return x;int rx;while(r!fa[r]){rfa[r];}int tx;while(x!fa[x]){tfa[x];fa[x]r;xt;}return r;
}typedef struct edge{int u,v,w;edge(int u0,int v0,int w0):u(u),v(v),w(w){}bool operator (const edge obj) const{return wobj.w;}
}edge;
edge mp[LEN*LEN];
int cnt0;int main(){
// freopen(还是畅通工程.txt,r,stdin);int i,j,u,v,w;while(scanf(%d,N),N){init();cnt0;int ans0;int edge_cnt0;i(N*(N-1))/2;while(i--){I(%d%d%d,u,v,w);mp[cnt]edge(u,v,w);
// mp[cnt]edge(v,u,w);}sort(mp,mpcnt);FF(i,cnt){int fa_ufindFa(mp[i].u);int fa_vfindFa(mp[i].v);if(fa_u!fa_v){ansmp[i].w;fa[fa_u]fa_v;edge_cnt;if(edge_cntN-1) break;}}O(%d\n,ans);}return 0;
} View Code 转载于:https://www.cnblogs.com/TQCAI/p/8549353.html
