数据结构 — 图 之 MST(最小生成树 — prim算法 )
发布日期:2021-06-30 19:49:31
浏览次数:3
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月15日 11时11分35秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
HDOJ2049 不容易系列之(4)——考新郎
2019-04-30
CodeForces 248B - Chilly Willy - 找规律
2019-04-30
POJ-2418 Hardwood Species(Trie树)(map)
2019-04-30
HDU-4300 Clairewd’s message + 4333(扩展KMP)
2019-04-30
HDU 1592 Half of and a Half(高精度)
2019-04-30
POJ-3304 Segments(计算几何)
2019-04-30
UVA-11538 Chess Queen(数学)
2019-04-30
UVA-11401 Triangle Counting(数学优化)
2019-04-30
Codeforces Round #369 (Div. 2)
2019-04-30
UVA 11426 GCD - Extreme (II)(欧拉函数)
2019-04-30
HDU-2838 Cow Sorting(树状数组)
2019-04-30
POJ-2299 Ultra-QuickSort(树状数组)(离散化)
2019-04-30
基于SSM的兼职论坛系统的设计与实现
2019-04-30
基于java的图书管理系统的设计与实现
2019-04-30
基于java的SSM框架理财管理系统的设计与实现
2019-04-30
基于java的ssm框架就业信息管理系统的设计
2019-04-30
基于java的ssm框架的旅游网站设计与实现
2019-04-30
基于java的SSM框架的流浪猫救助网站的设计与实现
2019-04-30