|
（四）图的基本应用 最小生成树 普里姆算法 【释】普里姆应用的是集合论的思想将元素分为两个集合U和V从中寻找最优解 void MiniSpanTree_PRIM（Mgraph GVertextype u）{ //用普里姆算法从第U个顶点出发构造网G的最小生成树T输出T的各条边 //记录从顶点集U到VU的代价最小的边的数组定义 struct{ vertexType adjvex; VRType lovcost; }closedge[MAX_VERTEX_NUM]; k=LocateVex（Gu）; for（j=;j=Gvexnum;++j）//数组初始化 if（j!=k）closedge[j]={uGarcs[k][j]adj};//{adjvexlowcost} closedge[k]lowcost=;//初始u={u} for（i=;i<Gvexnum;++i）{ k=mininum（closedge）; //此时closedge[k]lowcost=MIN{closedge[vi]lowcost printf（closedge[k]adjvexGvexs[k]）; closedge[k]lowcost= for（j=;j<Gvexnum;++j） if（Garcs[k][j]adj<closedge[j]lowcost） closedge[j]={Gvexs[k]Garcs[k][j]adj}; } }//MiniSpanTree 克鲁斯卡尔 【释】权值由小到大依次添边若构成环则捨弃 返回《数据结构》考研复习精编 [] [] [] [] [] [] [] [] [] [] |
