数据结构 Prim及单源最短路径

1、用普里姆算法从顶点U出发构造网G的最小生成树为实现此算法需附设一个辅助数组closedge,用以记录从U到V-U具有最小代价的边。 对每个顶点viEV-U ,在辅助数组中存在一个相应分量closedgei-l,它包括两个域:lowcost 和 adj vex olowcost域：存储最小代价的边上的权值，即：closedgei-l.lowcost=nihi(cost(u, vi )|uEUcost(u,vi)表示边(u,vi)上的权值。若某顶点加入到U中，则此时置lowcost域为0,表示该 顶点并入U中。adjvex域：存储依附于该边在U中的顶点。显然，每加入一个顶点到U中,closedge

2、数组 就会发生相应的变化。用普里姆算法从顶点U出发构造网G的最小生成树stmct Closedge( vertextype adjvex; U 集中的顶点int lowcost; / 边的权值 closedgeMAX.VERTEX.NUM;void MiniSpanTiee_P(mgraph Q vertextype u)( int k = Locate(&G；u );若图G中存在顶点u,则返回u在图中的存储位置for (iiitj=O; jG.vexiium; +j)辅助数组初始化】f(j!=k) closedgej.adjvex=u;closedge!j.lowcost=GarcskIj;

3、closedgek.lowcost = 0;/ 初始，U=ufor (mt i=l; iHG.vexskH, ”；/输出生成树上一条边closedgefk .lowcost=0; 第 k 顶点并入 U 集for (j=0; jG.vexiium; +j)修改其它顶点的最小边if (G.arcsk j closedge j . lowcost)( clo sedge j . adj vex= Gvexsk;closedgej.lowcost=G.aicskj;)/if) /for /MiniSpaiiTree_P查找最小未被访问的边mt niuumum(mgraph G, Closedge cl

4、osedge n) ( int k;fbr(int i=0; iG. vexiium;i-H-)if(closedgei.lowcost!=0) k=i; break; fbr( ;iG.vexnum:i+)if(closedgei. lowcost! =0&closedgei.lowcostclosedgek.lowcost) k=i；return k;uit distn; /disti存放顶点i的当前最短路径长度charpathnn+1 ; /pathi+存放顶点i的当前最短路径。bool flagn; 表示当前最短路径是否己经被选择void ShortestPath.DJS(mgraph

5、 g, mt vO)( mtchar tail2;fbr (i =0; ig.vexiium; i+) ( flagi=false;disti=g.aicsOi;pathi0=v0+H;pathil=g.vexsi;pathW;fbr(mt t=l; tg.vexiium; t+)/求vO到其余n-1个顶点的最短路径 ( niiii=MAX;fbr (1=0; ig.vexiium; i+)if (disti inm&flagi=false) k = i: nuii=disti; flagk=tine;fbr (i =0; ig.vexiium; i+)if (distk+g.arcskidi

6、sti) disti=distk+ g.arcski; strcpy(pathi,pathk);tailO=i+a;taill=，()； sticat(pathijail); )for (i =0; ig.vexiium; i+) coutpathiH Mdistiendl;拓扑排序：操作方法：(1)选取一个没有前驱的顶点，输出它，并从AOV中网中删除此顶点以及所有以它 为尾的孤。(2)重复(1)直至输出所有结点统计有向图邻接表各顶点的入度void uiit_iiidegree(ALGraph G)fbr(i=O:iGvexiium;i+)mdegreei=O;fbr(i=O; iadjvex

7、+; p=p-nextarc;/fbr /imciiidegree取入度为零的点vmt getzerodegree (ALGrapg G) ( fbr(i=O;iadj vex;elsereturn-!;5 . NextAdjmt NextAdj (ALGrapg G .int v int w)(p=G vertices v .firs taic;while(p & p-adjvex! =w)p=p-nextaic;f(p)return p-nextarc-adjvex;elsereturn-!;6.算法实现m=0:Hut_mdegree(G);vr=getzerodegree(G)wliile(v!=-l)(