最小生成树 ╰+攻爆jí腚メ 2021-12-05 01:29 271阅读 0赞 ### 最小生成树 ### * prim算法 * * 测试输入 * 输出 * Kruskal算法 * * 测试输出 # prim算法 # #include<bits/stdc++.h> using namespace std; const int maxn = 1e2; const int INF = 1<<30;//表示无穷大,两个顶点不存在边 int g[maxn][maxn];//利用邻接矩阵表示有权图 int n;//表示顶点个数,从1开始编号 struct edge{ int v;//边的一个顶点,另一个顶点用数组的索引表示 int w;//边的权重 }; void init(){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++)g[i][j]=INF; } }//对图进行初始化 void prim(int v=1){ //从v开始构造生成树 bool reach[maxn]={ false};//为true时代表在最小生成树点集中 edge e[maxn]; for(int i=1;i<=n;i++){ e[i].v=v; e[i].w=g[v][i]; }//对边进行初始化 reach[v]=true;//加入最小生成树点集 while(true){ int Min=INF,index=-1; for(int i=1;i<=n;i++)if(!reach[i]&&Min>e[i].w)Min=e[i].w,index=i;//寻找待加入最小生成树点集的顶点 if(index==-1)return ;//顶点已全部加入最小生成树点集中,退出 cout<<e[index].v<<"-->"<<index<<endl; reach[index]=true;//加入最小生成树点集 for(int i=1;i<=n;i++){ if(!reach[i]&&g[index][i]<e[i].w){ e[i].w=g[index][i]; e[i].v=index; } }//修改 } } int main(){ int m; int a,b,c; scanf("%d%d",&n,&m); init(); for(int i=0;i<m;i++){ scanf("%d%d%d",&a,&b,&c); g[a][b]=g[b][a]=c; } prim(1); } ## 测试输入 ## 7 9 1 2 28 1 6 10 2 3 16 2 7 14 3 4 12 4 5 22 4 7 18 5 6 25 5 7 24 ## 输出 ## 1-->6 6-->5 5-->4 4-->3 3-->2 2-->7 # Kruskal算法 # #include<bits/stdc++.h> using namespace std; const int maxn = 1e2; const int INF = 1<<30;//表示无穷大,两个顶点不存在边 int g[maxn][maxn];//利用邻接矩阵表示有权图 int n;//表示顶点个数,从1开始编号 int f[maxn]; struct edge{ int v1,v2;//边的一个顶点,另一个顶点用数组的索引表示 int w;//边的权重 bool operator<(const edge& a) const { return w > a.w; // 重定义比较函数,使用小根堆 } edge(int a,int b,int c):v1(a),v2(b),w(c){ } }; void init(){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++)g[i][j]=INF; } }//对图进行初始化 int find(int x){ return x==f[x]?x:f[x]=find(f[x]); }//查找共同祖先 void kruskal(int v=1){ //从v开始构造生成树 for(int i=1;i<=n;i++)f[i]=i;//初始化并查集 priority_queue<edge>p;//构造优先级队列 for(int i=2;i<=n;i++){ for(int j=1;j<i;j++){ int w = g[i][j]; if(w!=INF)p.push(edge(i,j,w));//依次把每条边加入优先队列 } } while(!p.empty()){ edge e =p.top(); p.pop(); int xx=find(e.v1),yy=find(e.v2); if(xx==yy)continue;//该两个顶点在一个集合 cout<<e.v1<<"-->"<<e.v2<<endl; f[xx]=yy;//把两个集合合并 } } int main(){ int m; int a,b,c; scanf("%d%d",&n,&m); init(); for(int i=0;i<m;i++){ scanf("%d%d%d",&a,&b,&c); g[a][b]=g[b][a]=c; } kruskal(1); } ## 测试输出 ## 6-->1 4-->3 7-->2 3-->2 5-->4 6-->5
相关 最小生成树 最小生成树定义: 在一给定的无向图 G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边(即![(u, v)\\in E][u_ v_in E]),而 末蓝、/ 2022年09月20日 15:18/ 0 赞/ 155 阅读
相关 生成树相关问题(最小生成树变形,次小生成树,最小度限度生成树,极差最小生成树) 生成树相关问题(最小生成树变形,次小生成树,最小度限度生成树,极差最小生成树) 视频:[https://www.bilibili.com/video/BV1G64y187ke Bertha 。/ 2022年09月12日 05:52/ 0 赞/ 159 阅读
相关 最小生成树 一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。 最小生成树在n个顶点的情形下,有n-1条边。生成树是对连 忘是亡心i/ 2022年08月03日 05:28/ 0 赞/ 169 阅读
相关 最小生成树 有n个城市,m条道路,现在输入n到m的道路的长度,用最少的边将图连接,输出让图连接的最小值 这道题我研究了好长时间才把答案看明白,现在给大家分享一下 具体代码如下 爱被打了一巴掌/ 2022年05月30日 08:56/ 0 赞/ 137 阅读
相关 最小生成树 设G = (V,E)是无向连通带权图,即一个网络。E中的每一条边(v,w)的权为c\[v\]\[w\]。如果G的子图G’是一棵包含G的所有顶点的树,则称G’为G的生成树。生成 红太狼/ 2022年05月24日 11:41/ 0 赞/ 224 阅读
相关 最小生成树 问题提出: 要在n个城市间建立通信联络网。顶点:表示城市,权:城市间通信线路的花费代价。希望此通信网花费代价最小。 问题分析: 答案只能从生成树中找,因为要做到任何 雨点打透心脏的1/2处/ 2022年03月18日 12:28/ 0 赞/ 235 阅读
相关 最小生成树 kruskal算法基本思路:先对边按权重从小到大排序,先选取权重最小的一条边,如果该边的两个节点均为不同的分量,则加入到最小生成树,否则计算下一条边,直到遍历完所有的边。 p ゝ一纸荒年。/ 2022年02月25日 14:20/ 0 赞/ 227 阅读
相关 最小生成树 最小生成树 什么是最小生成树 给定一张无向带权图G=(V,E,W),从中挑选出|V|-1条边,使得V中任意两点都有直接或者间接的路径 显然,最后得到的子 浅浅的花香味﹌/ 2021年12月22日 01:57/ 0 赞/ 267 阅读
相关 最小生成树 最小生成树 prim算法 测试输入 输出 Kruskal算法 测试输出 prim算法 include<b ╰+攻爆jí腚メ/ 2021年12月05日 01:29/ 0 赞/ 272 阅读
相关 最小生成树 Jungle Roads [http://poj.org/problem?id=1251][http_poj.org_problem_id_1251] Descrip 逃离我推掉我的手/ 2021年11月29日 22:28/ 0 赞/ 373 阅读
还没有评论,来说两句吧...