熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

第四部分 圖[6]

2013-11-15 15:21:42  來源: 數據結構 

    (四)圖的基本應用
  
  最小生成樹
  
   普裡姆算法
  【釋】普裡姆應用的是集合論的思想將元素分為兩個集合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
  • 上一篇文章:

  • 下一篇文章:
  • 推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.