数据结构 — 图 之 MST(最小生成树 — prim算法 )
发布日期:2021-06-30 19:49:31
浏览次数:2
分类:技术文章
本文共 1185 字,大约阅读时间需要 3 分钟。
【描述】:
采用邻接矩阵方式储存图,创建图,生成最小生成树。
【输入】:
7 9 0 1 2 3 4 5 6 0 1 28 0 5 10 1 2 16 1 6 14 2 3 12 3 4 22 3 6 18 4 5 25 4 6 24
【输出】:
0,5权值: 10 | 5,4权值: 25 | 4,3权值: 22 | 3,2权值: 12 | 2,1权值: 16 | 1,6权值: 14 |
/*7 90 1 2 3 4 5 60 1 280 5 101 2 161 6 142 3 123 4 223 6 184 5 254 6 24*/#includeusing namespace std;/*宏定义*/#define INFINITY 65535#define MAX_NUM 100#define EleType int#define EdgeType int/*图的结构体*/typedef struct { EleType vertex[MAX_NUM]; //顶点表 EdgeType arc[MAX_NUM][MAX_NUM]; //邻接矩阵 int VertexNum; //顶点数 int ArcNum; //边数}GraphType,*GraphPointer;//声明图GraphType graph;/*邻接矩阵的创建*/void CreateGraph(){ int w; //权值 int n,k; //输入顶点数和边数 cin>>graph.VertexNum>>graph.ArcNum; //输入所有顶点 for(int i = 0; i >graph.vertex[i]; } //初始化邻接矩阵 for(int j = 0; j >n>>k>>w; graph.arc[n][k] = w; //无向图邻接矩阵对称原则 graph.arc[k][n] = w; } }/*prim*/void prim(){ int n,min; //n是当前最小值的下标(根据lowcost数组得出 ) int adjver[MAX_NUM]; //所有vertex 与 已经加入到MST中,可以和其组成min距离的顶点相连 int lowcost[MAX_NUM]; //所有vertex 与 MST的最小距离(权值) adjver[0] = 0; //相连 lowcost[0] = 0; //更新权值 //将第一顶点v0加入到MST中的第一轮更新 for(int i = 1; i
转载地址:https://lipenglin.blog.csdn.net/article/details/50002513 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年04月30日 19时36分23秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
ACM 2013 长沙区域赛 Alice's Print Service (二分 思维)
2019-04-30
ACM 2013 长沙区域赛 Collision (几何)
2019-04-30
CodeForces - 1064A Make a triangle! (简单模拟)
2019-04-30
51Nod - 1183 编辑距离 (dp)
2019-04-30
ACM 2014 鞍山区域赛 E - Hatsune Miku (dp)
2019-04-30
反向传播&梯度下降 的直观理解程序(numpy)
2019-04-30
ACM 2017 南宁区域赛 Rake it in(对抗搜索)
2019-04-30
CodeForces - 931B World Cup (思维 模拟)
2019-04-30
CodeForces - 996D Suit and Tie (暴力)
2019-04-30
ACM 2017 香港区域赛 E - Base Station Sites(二分)
2019-04-30
ACM 2018 青岛区域赛 J-Books (模拟)
2019-04-30
ACM 2016 沈阳区域赛 E - Counting Cliques (dfs)
2019-04-30
ACM 2017 北京区域赛 J-Pangu and Stones(区间dp)
2019-04-30
HDU - 5643 King's Game (约瑟夫环变式)
2019-04-30
UVA - 1452 Jump (约瑟夫环变式)
2021-07-03
POJ - 3517 And Then There Was One (约瑟夫环变式)
2021-07-03
HDU - 2068 RPG的错排 (错排+组合数)
2021-07-03
CodeForces 591C Median Smoothing(思维 模拟)
2021-07-03
SupreNFT——多元融合的NFT超级平台 撬动NFT万亿蓝海市场
2021-07-03