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

第四部分 圖[9]

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

    拓撲排序算法——偽代碼
  棧S初始化累加器count初始化
  掃描頂點表將沒有前驅的頂點壓棧
  當棧S非空時循環
    vj=退出棧頂元素輸出vj累加器加
    將頂點vj的各個鄰接點的入度減
    將新的入度為的頂點入棧
  if(count<vertexNum)輸出有回路信息
  
  關鍵路徑
  
  關鍵路徑在AOE網中從始點到終點具有最大路徑長度(該路徑上的各個活動所持續的時間之和)的路徑稱為關鍵路徑
  
  關鍵活動關鍵路徑上的活動稱為關鍵活動
  
  ()事件的最早發生時間ve[k]
  ve[k]是指從始點開始到頂點vk的最大路徑長度這個長度決定了所有從頂點vk發出的活動能夠開工的最早時間
  
  ()事件的最遲發生時間vl[k]
  vl[k]是指在不推遲整個工期的前提下事件vk允許的最晚發生時間
  
  ()活動的最早開始時間e[i]
  若活動ai是由弧<vkvj>表示則活動ai的最早開始時間應等於事件vk的最早發生時間因此
  e[i]=ve[k]
  
  ()活動的最晚開始時間l[i]
  活動ai的最晚開始時間是指在不推遲整個工期的前提下ai必須開始的最晚時間
  若ai由弧<vkvj>表示則ai的最晚開始時間要保證事件vj的最遲發生時間不拖後因此
  l[i]=vl[j]len<vkvj>

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

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


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

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