数据结构

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。 以下是数据结构中关于普里姆算法的操作（编程风格参考严蔚敏版数据结构）。

特别说明！！！！！ 在Closedge中，起点是通过节点VerTexType类型变量表示，而终点是通过下标int类型变量来表示。 adjvex就是某条边的起点，lowcost就是两点之间权值（距离）,closedge[i]里的i是终点的下标。 理解好这个很重要，如果这个理解不好，那就不知道Prim里close辅助数组是怎么用的了。

如何算出上图里的最小生成树呢？ 老样子先弄出邻接矩阵：

初始化辅助数组close。这一步目的是让起点直连其它的节点（就是说假设起点到其它全部节点的距离是最短的）。画出来是这样的： 此时的close记录的就是从A到其它全部节点的距离的集合。 开始第一轮循环：在close这些边里选出最短的边，AC的值最小，记录起点为A终点为C（不必做更新操作，因为这条边本就在close里）。然后以AC同时和BEFD比较距离（权值大小）。比如：A到B的距离为为6，C到B的距离是5，close里本来是A到B的边变成C到B，然后close变成如下情况：

然后AC和E比较，和F比较、和D比较，CE'A','B','C','D','E','F'}; ArcType arcs[MVNum][MVNum]; int vexnum = 6,arcnum = 10; }AMGraph; typedef struct{ VerTexType adjvex;//最小边在顶点集U的顶点 ArcType lowcost;//最小边上的权值 }Closedge[MVNum]; //其实说白了就是adjvex就是某条边的起点，lowcost就是权值（距离）,closedge[i]的i是终点。 //理解好这个很重要。 status CreateUDN(AMGraph &G){//创建无向图 for(int i=0;i if(i==j){ G.arcs[i][j] = 0; }else G.arcs[i][j] = MaxInt;//初始状态全部节点之间相互不可达 } } G.arcs[0][1]=6;G.arcs[0][2]=1;G.arcs[0][3]=5; G.arcs[1][2]=5;G.arcs[1][4]=3; G.arcs[2][3]=5;G.arcs[2][4]=6;G.arcs[2][5]=4; G.arcs[3][5]=2; G.arcs[4][5]=6; for(int i=0;i if(G.arcs[i][j]!=MaxInt){ G.arcs[j][i] = G.arcs[i][j]; } } }//矩阵对称 return OK; } void ShowGraph(AMGraph G){ cout cout cout int i; for(i=0;i return i; } } return ERROR; } int Min(Closedge close,AMGraph G){ int min = MaxInt; int mini; for(int i=0;i//不等于0是指不和自身比较，没意义 min = close[i].lowcost; mini = i; } } // cout if(vi!=i){ close[i].adjvex=v; close[i].lowcost=G.arcs[vi][i];//初始化辅助数组close,让起点直连其它节点（就是假设起点到全部点的距离都是最短） }else{ close[i].lowcost = 0;//0表示自身或该边已被选取。 } } for(int i=1;i//更新close表 if(G.arcs[k][j]G.vexs[k],G.arcs[k][j]};//最短距离从start到j点距离修改成end到j点的距离 //等价于这样写 // close[i].adjvex=G.vexs[k]; // close[i].lowcost=G.arcs[k][j]; }//if }//for } } int main(){ AMGraph G; CreateUDN(G); ShowGraph(G); Prim(G,'A'); return 0; } 关于时间复杂度和空间复杂度

设顶点数n，边数e。邻接矩阵:O(n^2) 邻接表:O(elogn)

敬请批评指正。