第四部分 圖[6]

    （四）圖的基本應用
　　
　　最小生成樹
　　
　　 普裡姆算法
　　【釋】普裡姆應用的是集合論的思想將元素分為兩個集合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
　　
　　 克魯斯卡爾
　　【釋】權值由小到大依次添邊若構成環則捨棄

    返回《數據結構》考研復習精編

[]  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23292.html