HDU1233(基础最小生成树 prim和 kruskal)
发布日期:2021-06-29 21:41:14
浏览次数:3
分类:技术文章
本文共 1681 字,大约阅读时间需要 5 分钟。
题目链接:
prim算法:算法从任意一个顶点开始,每次选择一个与当前顶点集最近的一个顶点,并将两顶点之间的边加入到树中。Prim
算法在找当前最近顶点时使用到了贪婪算法。
代码实现:
#includeusing namespace std;const int maxn=105;const int INF=0x3f3f3f3f;//初始化无穷大int dis[maxn];//dis[i]//记录边权bool vis[maxn];//标记边int edge[maxn][maxn];void prim(int n){ for(int i=1;i<=n;i++) dis[i]=edge[1][i];//初始时候记录1到其他顶点距离 int ans=0; dis[1]=0; vis[1]=true;//将用过的点标记,避免重复访问 for(int i=2;i<=n;i++)//进行n-1次操作 { int u=INF; int pos;//记录最小权值的顶点的下标 for(int j=1;j<=n;j++)//在未加入点中,找到一个最小的权值 { if(!vis[j]&&u>dis[j]) { u=dis[j];//更新最小值 pos=j; } } if(u==INF) break;//图不是连通图 vis[pos]=true;//将加入点进行标记 ans+=u;//加边权 for(int j=1;j<=n;j++)//枚举所有点 {//在未加入点中找到与此点相连的权值最小的边 if(!vis[j]&&dis[j]>edge[pos][j]) { dis[j]=edge[pos][j];//更新权值 } } } printf("%d\n",ans);}int main(){ int n; while(scanf("%d",&n)&&n) { memset(vis,false,sizeof(vis)); int m=(n-1)*n/2; for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); edge[u][v]=edge[v][u]=w; } prim(n); } return 0;}
kruskal算法:
kruskal算法主要是加边,初始最小生成树边数为0,每迭代一次就选择一条满足条件的最小代价边,加入到最小生成树的边集合里。
1. 把图中的所有边按代价从小到大排序; 2. 把图中的n个顶点看成独立的n棵树组成的森林; 3. 按权值从小到大选择边,所选的边连接的两个顶点ui,viui,vi ,应属于两颗不同的树,则成为最小生成树的一条边,并将这两颗树合并作为一颗树。 4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。代码:
#includeusing namespace std;const int maxn=1e4+5;typedef long long LL;int father[maxn];struct node{ int u,v,val;//u-v之间边权为val}edge[maxn];bool cmp(node a,node b)//按照边权小到大排序{ return a.val
转载地址:https://dh-butterfly.blog.csdn.net/article/details/81414160 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年04月18日 11时54分43秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Linux创建进程的源码分析
2019-04-30
ubunut16.04的pip3出现问题,重新安装pip3
2019-04-30
how2heap-double free
2019-04-30
how2heap-fastbin_dup_consolidate
2019-04-30
orw_shellcode_模板
2019-04-30
[fmt+shellcode]string
2019-04-30
fmt在bss段(neepusec_easy_format)
2019-04-30
[double free] 9447 CTF : Search Engine
2019-04-30
python 函数式编程
2019-04-30
python编码
2019-04-30
scala maven plugin
2019-04-30
flink 1-个人理解
2019-04-30
redis cli
2019-04-30
redis api
2019-04-30
flink physical partition
2019-04-30
java 解析json
2019-04-30
java http请求
2019-04-30
tensorflow 数据格式
2019-04-30
tf rnn layer
2019-04-30