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

第四部分 圖[8]

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

    弗洛伊德算法
  void ShortestPath_FLOYD(Mgraph G PathMatrix &p[] distancMatrix &D){
  //用Floyd不著算法注有向網G中各對頂點V和W之間的最短路徑p[v][w]及其帶權
  //限長度d[v][w]若p[v][w][u]為TRUE則U是從V到W當前求得最短路徑上的頂點
  for(v=;v<Gvexnum;++v)
  for(w=;w<Gvexnum;++W){
  D[v][w]=Garcs[v][w];
  for(u=;u<Gvexnum;++u) p[v][w][u]=FALSE;
  if(d[v][w]<INFINITY){
  P[v][w][v]=TRUE; P[v][w][w]=TRUE;
  }//if
  }//for
  for(u=;u<Gvexnum;++u)
  for(v=;v<Gvexnum;++v)
  for(w=;w<Gvexnum;++w)
  if{D[w][u]+D[u][w]<D[v][w]}
  {D[v][w]=D[v][u]+D[u][w];
  for(i=;i<Gvexnum;++i)
  P[v][w][i]=P[v][w][i];
  }//if
  }//ShortestPath_FLOYD
  
  托普排序
  
  拓撲序列設G=(VE)是一個具有n個頂點的有向圖V中的頂點序列vvvn稱為一個拓撲序列當且僅當滿足下列條件若從頂點vi到vj有一條路徑則在頂點序列中頂點vi必在頂點vj之前
  
  拓撲排序對一個有向圖構造拓撲序列的過程稱為拓撲排序
  
  基本思想
  ()從AOV網中選擇一個沒有前驅的頂點並且輸出
  ()從AOV網中刪去該頂點並且刪去所有以該頂點為尾的弧
  ()重復上述兩步直到全部頂點都被輸出或AOV網中不存在沒有前驅的頂點

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

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


From:http://tw.wingwit.com/Article/program/sjjg/201311/23294.html
  • 上一篇文章:

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