首页 25考研 在职考研 0元畅学 26考研

新东方在线 > 考研 > 计算机 > 考研计算机资料 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

计算机考研：数据结构常用算法精析(7)

2013-12-11 14:39:50来源：新东方在线编辑

　　两种求最小生成树的算法(Prim和Kruskal)

　　Prim算法中有双重循环，外层是求n-1条边内层是在closedge[v].lowcost 中求最小值和并列的求得当前加入点对closedge[]的影响。所以他的时间复杂度是O( )，它与途中边的数目没有关系，所以比较适合用在边比较稠密的图中。(顶点数相同，不管边数，都相同)

　　Kruskal和他相对应，他的时间复杂度为O(eloge)，与图中的结点数目无关，至于边的个数有关。所以适合用在稀疏图中。(边数一定，不管顶点数，复杂度都相同)

　　求最小生成树的普里姆(Prim)算法中边上的权不可以为负，

　　typedef struct {

　　VertexType adjvex;

　　VRType lowcost;

　　}closedge[MAX_VERTEX_NUM];

　　假设cost(u,w)表示边(u,w)上的权值，则对于集合 V-U 中每个顶点 w，

　　closedge[LocateVex(G, w)].lowcost = Min{cost(u,w)|u∈U}

　　void MiniSpanTree_PRIM( MGraph G, VertexType u,SqList& MSTree)

　　{

　　// G 为数组存储表示的连通网，按普里姆算法从顶点 u 出发构

　　k = LocateVex ( G, u );

　　for ( j=0; j

　　if (j!=k) closedge[j] = { u, G.arcs[k][j].adj };//{adjvex,lowcost}

　　closedge[k].lowcost = 0; 　　　 // 初始状态，U={u}

　　for (i=1; i

　　{　 k = minimum(closedge);　　　　// 求出T的下一个结点(图中第k顶点)

　　// 此时closedge[k].lowcost =

　　// Min{ closedge[vi].lowcost | closedge[vi].lowcost>0, vi∈V-U }

　　printf(closedge[k].adkvex, G.vexs[k]); //输出生成编

　　closedge[k].lowcost = 0; 　　　// 第 k 顶点并入U集

　　for (j=0; j

　　if (G.arcs[k][j].adj < closedge[j].lowcost) //新顶点并入U后重新选最小边

　　closedge[j] = { G.vexs[k], G.arcs[k][j].adj };

　　} // for

　　} // MiniSpanTree

考研公开课小程序

本文关键字: 计算机 考研 数据结构

上一页 1 2 3 4 5 6 7 8 下一页

考研英语核心词汇营

背词+听课+练习+督学，学习得礼盒

更多资料

添加班主任领资料

添加考研班主任
免费领取考研历年真题等复习干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.添加班主任，可领取学习资料。
更多>>
更多内容
25考研 在职研 AI择校 去测评 领资料

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】，识别上方二维码；
2.点击【关注公众号】，获取资料大礼包。

考研资料大礼包

历年考研真题及答案解析下载

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10