www.pryy.net > 用prim算法,求下图的最小生成树.假设A为起点

用prim算法,求下图的最小生成树.假设A为起点

1、(a, b) 2、(a, c) 如果ch是6就是如下过程 3、(c, d) 接下来bd不详,假设很大 4、(d, h) 5、(d, g) 6、(g, f) 7、(f, e)

//prim算法 #include using namespace std; #define MAXVEX 10 #define MAX 65000 typedef char VexType; typedef float AdjType; struct GraphMatrix { VexType vexs[MAXVEX]; //顶点信息 AdjType arcs[MAXVEX][MAXVEX]; //边信息 int n; //图...

不好意思吖按照图弄那两个中间数组太久了。。。实现方法也有不同。我跟您说说我学的通用实现方法吧! 点集合:A,代表已经扩展到的点。 边集合B:代表待考虑的边,一开始为空。 一开始从任意点出发,如0.此时集合A中只有点0。将和A相邻的所有边...

自己画一下,按我说的步骤(链接8条边和相应的顶点即可,一次一条): A--B A--G G--I I--E E--D D--C C--H I--F

最短路径: a->b:4 a->c:8 a->c->f:9 a->c->f->g:12 a->b->e:13 a->c->f->d:14 最小生成树生成次序: 1、a-b 2、a-c 3、c-f 4、f-g 5、f-d 6、d-e

不会画,和你文字描述好了,你自己画出来 第一步连AE 第二步连EG GC GF AD BD

您的图呢?

正在看 实在不懂 帮不了你 谢谢

你需要存一个图的必备变量 你需要一个数组 l[i] 记录第 i 个点所连的最小生成树边的边权 一个布尔数组 u[i] 记录第 i 个点是否已经作为起点拓展过 再有就是打擂台用的辅助变量了

1. 邻接矩阵 A B C D E F G H A 0 4 3 - - - - - B 4 0 5 5 9 - - - C 3 5 0 5 - - - 5 D - 5 5 0 7 6 5 4 E - 9 - 7 0 3 - - F - - - 6 3 0 2 - G - - - 5 - 2 0 6 H - - 5 4 - - 6 0 2.邻接表 A| B C B| A C D E C| A B D H D| B C E F G H E|...

网站地图

All rights reserved Powered by www.pryy.net

copyright ©right 2010-2021。
www.pryy.net内容来自网络,如有侵犯请联系客服。zhit325@qq.com