电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

最小生成树Prim算法和单源最短路径Dijkstra算法VIP免费

最小生成树Prim算法和单源最短路径Dijkstra算法_第1页
1/6
最小生成树Prim算法和单源最短路径Dijkstra算法_第2页
2/6
最小生成树Prim算法和单源最短路径Dijkstra算法_第3页
3/6
最小生成树Prim算法和单源最短路径Dijkstra算法问题:1.(最小生成树)给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,即求最小生成树。2.(单源最短路径)给定一个权值都为正数的无向连通图和一个源点,确定它到其它点的最短距离。之所以将这两个问题放在一起,是因为Prim算法与Dijkstra算法的思路和程序都非常相似,都是有贪心策略。1.解法(Prim算法):思路:设连通网络N={V,E},U表示已加入到生成树的顶点集合。在初始化阶段,任取一个顶点,用其关联边的权值作为初始的V-U顶点集合的数据。在每一步中,先在V-U顶点集合中选择距离U中任意点“最近”的顶点v,再把v加入到U中,最后看看在新的V-U顶点集合中,是否有哪个顶点距离v比距离U中其它点更近,若有则更新V-U顶点集合中的数据。U的元素个数为V-1,所以共要进行V-1步。总的时间复杂度为Time=O(V)*T_EXTRACT-MIN+O(E)*T_DECREASE-KEY若用数组作为顶点权值的数据结构,T_EXTRACT-MIN用时O(V),T_DECREASE-KEY用时O(1),总共用时O(V^2)若用最小堆作为顶点权值的数据结构,T_EXTRACT-MIN用时O(lgV),T_DECREASE-KEY用时O(lgV),总共用时O((V+E)*lgV)若用斐波那契堆作为顶点权值的数据结构,T_EXTRACT-MIN平均用时O(lgV),T_DECREASE-KEY平均用时O(1),总共用时O(E+V*lgV)下面的代码使用数组作为顶点权值的数据结构:[cpp]viewplaincopy1.#include2.#include3.usingnamespacestd;4.5.#defineMAXN10016.#defineINF10000007.8.intlowcost[MAXN];//距离U中顶点的最小权值9.boolvisited[MAXN];//若为true表示已加入到集合U中10.intmst[MAXN];//距离U中哪个顶点最短11.intgraph[MAXN][MAXN];//用矩阵表示图上各边权值12.13.voidPrim(intn)14.{15.inti,j;16.memset(visited,0,n*sizeof(bool));17.visited[0]=true;18.mst[0]=-1;19.for(i=1;igraph[minid][j])39.{40.lowcost[j]=graph[minid][j];41.mst[j]=minid;42.}43.}44.}45.46.intmain()47.{48.intn,m,i,j;49.cin>>n>>m;50.for(i=0;i2.#include3.4.usingnamespacestd;5.6.#defineMAXN10017.#defineINF10000008.9.intlowcost[MAXN];//距离源点u的最短距离10...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

最小生成树Prim算法和单源最短路径Dijkstra算法

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部