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

最小生成树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]?view plaincopy #include?iostream?? #include?algorithm?? using?namespace?std;?? ?? #define?MAXN?1001?? #define?INF??1000000?? ?? int?lowcost[MAXN];??//?距离U中顶点的最小权值?? bool?visited[MAXN];?//?若为true表示已加入到集合U中?? int?mst[MAXN];??????//?距离U中哪个顶点最短?? int?graph[MAXN][MAXN];??//?用矩阵表示图上各边权值?? ?? void?Prim(int?n)?? {?? ????int?i,?j;?? ????memset(visited,?0,?n*sizeof(bool));?? ????visited[0]?=?true;?? ????mst[0]?=?-1;?? ????for?(i=1;?in;?i++)?? ????{?? ????????lowcost[i]?=?graph[0][i];?? ????????mst[i]?=?0;?? ????}?? ????for?(i=1;?i=n-1;?i++)?? ????{?? ????????//?取V-U中的最小权值T_EXTRACT-MIN?O(V)?? ????????int?min=INF,?minid;?? ????????for?(j=1;?jn;?j++)?? ????????????//?用visited数组确定V-U?? ????????????if?(!visited[j]??lowcost[j]??min)?? ????????????{?? ????????????????min?=?lowcost[j];?? ????????????????minid?=?j;?? ????????????}?? ????????visited[minid]?=?true;?? ????????//?减小V-U中的权值T_DECREASE-KEY?O(1)?? ????????for?(j=1;?jn;?j++)?? ????????????if?(!visited[j]??lowcost[j]??graph[minid][j])?? ????????????{?? ????????????????lowcost[j]?=?graph[minid][j];?? ????????????????mst[j]?=?minid;?? ????????????}?? ????}?? }?? ?? int?main()?? {?? ????int?n,?m,?i,?j;?? ????cin??n??m;?? ????for?(i=0;?in;?i++)?? ????????for?(j=0;?jn;?j++)?? ????????????graph[i][j]?=?INF;?? ????for?(i=0;?im;?i++)?? ?