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)

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

最短路径: 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

您的图呢?

百度一下很多的

/* 邻接矩阵存储图 测试数据 6 10 1 2 6 1 3 1 1 4 5 2 3 5 2 5 3 3 4 5 3 5 6 3 6 4 4 6 2 5 6 6 */ #include #include #define N 100 int p[N], key[N], tb[N][N]; void prim(int v, int n) { int i, j; int min; for (i = 1; i

自己按下面的先后过程画图即是生成过程;说明(i,j)是一条连接顶点i和j的一条边; 普利姆(Prim)算法:从顶点0开始构造 (0,1),(0,2),(1,2),(2,5),(5,4) 克鲁斯卡尔算法: (0,1),(0,2),(1,2),(4,5),(2,5)

#include #include #include #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 typedef int VRType; typedef int InfoType; typedef char VerTexType; typedef struct ArcCell { VRType adj; InfoType *info; }ArcCell, AdjMatrix[MAX_VERTE...

O(n^2), O(elog2e) 求这两个结果的过程任何一本比较全面的数据结构教科书上都有的

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