關(guān)鍵路徑算法課程設(shè)計(編輯修改稿)
2024-11-12 08:01 本頁面
【文章內(nèi)容簡介】 報告 三 詳細設(shè)計 9 點出發(fā)，令事件的最早發(fā)生時間為 0，按拓撲有序求其余各頂點時間的最早發(fā)生時間 ve[k]； (代碼如下 ) If (ve[t] + pinfo ve[k]) ve[k] = ve[t] + pinfo。 // ve[k] k(終點 ) 頂點事件 最早 能發(fā)生的時間 ve[] 初始為 0 接著從終點出發(fā)，令事件最遲發(fā)生時間等于其最早發(fā)生時間，按你你逆拓撲排序求其余各頂 點事件最遲發(fā)生時間 vl[k]；最后根據(jù)各頂點事件的 ve 和 vl 值，求所有活動最早開始時間 ee 和最遲開始時間 el。如果某活動滿足條件 ee＝ el，則為關(guān)鍵活動。 (代碼如下 ) if( vl[k] dut vl[t] ) { vl[t] = vl[k] dut。 } // vl[t] t(始點 ) 頂點事件 最遲發(fā)生時間 for(int j=1。 j=Gvexnum。 j++) { p=Gvertices[j].firstarc。 while(p) { i++。 int k = padjvex。 ee[i] = ve[j]。 el[i] = vl[k]pinfo。 printf(| %3c | %3c | %6d | %6d | %3d |,Gvertices[j].data, Gvertices[k].data, ee[i], el[i], el[i]ee[i])。 if(el[i]==ee[i]) { printf( 此弧為關(guān)鍵活動 )。 } p=pnextarc。 } } 湖南工學(xué)院課程設(shè)計報告 三 詳細設(shè)計 10 同時，為計算各頂點事件的 ve 值是在拓撲排序的過程中進行的，因此需一個 棧 來記錄拓撲排序，如果頂點的入度為 0，則該頂點 入棧。 int t = ()； ()。 (t)。 count++。 // 度為 0 的結(jié)點出棧 S 入棧 T 棧 T 保存 拓撲序列 cout關(guān)鍵路徑所需時間為： ve[Gvexnum]。 主程序建立 該部分主要是對 所建立的函數(shù)的調(diào)用。 包括 ： 建立圖的函數(shù) CreateGraph( )； 計算關(guān)鍵路徑的函數(shù) CriticalPath ( )； 最后程序結(jié)束。 這樣安排可以增強程序的可讀性，是程序便于理解，也便于日后的對程序的維護和修改等操作。 四 實 驗結(jié)果 按照要求輸入一組關(guān)于 無循環(huán)有向帯權(quán)圖所有信息 。 如： 6 1 2 3 4 5 6 8 1 2 30 1 3 20 2 4 20 2 5 30 3 4 40 3 6 30 4 6 20 5 6 10 湖南工學(xué)院課程設(shè)計報告 三 詳細設(shè)計 11 依次執(zhí)行程序每一步，最后結(jié)束該程序 。 程序運行如下圖 ： 湖南工學(xué)院課程設(shè)計報告 五 程序設(shè)計心得 12 五 程序設(shè)計心得 通過這次求關(guān)鍵路徑，我對圖的鄰接表有了深刻的了解。以前都是用鄰接矩陣的，感覺鄰接矩陣直觀 簡便，而這次關(guān)鍵路徑的有關(guān)算法，書上都是使用鄰接表的，我試著熟悉它，發(fā)現(xiàn)也挺好用的，許多操作用鄰接表更方便。 書上沒有鄰接表的構(gòu)圖代碼，拓撲排序，關(guān)鍵路徑的都是偽代碼，我不得不去查資料，思索，自己編寫完整可執(zhí)行的代碼，這個過程很艱辛，也很愉快。拓撲排序時我想辦法弄出了不同拓撲排序的總數(shù)，卻怎么也無法打印出所有的拓撲序列。在關(guān)鍵路徑求頂點事件最遲的發(fā)生時間時，錯把各個頂點的最早發(fā)生時間賦給了它，所以輸出的結(jié)果怎么都不對， 我在這個地方糾結(jié)的好久。 知識只有在使用的時候才會遠遠感覺不夠用，我深深體會到了這句話。這次的程序設(shè)計對我的幫助很大，雖然真正自己寫的代碼并不多，許多都是書上的代碼經(jīng)過補充改寫的，但畢竟我都把這整個過程走了一遍，熟悉了圖的各種操作，各種算法我都認真看懂了，思考了。我能感覺到自己的進步，每次編寫出一個程序，在電腦上運行出來時，都會有一種莫名的成就感，很享受這種感覺，我會繼續(xù)努力的。 計科 1203 王勛峰 湖南工學(xué)院課程設(shè)計報告 五 程序設(shè)計心得 13 六 參考文獻 [1] 嚴(yán)蔚敏 編 。 數(shù)據(jù)結(jié)構(gòu)（ C 語言版） 。 北京 : 清華 大學(xué)出版社， [2] 譚浩強著 。 C 語言程序設(shè)計（第二版） 。 北京 : 清華大出版社， [3] 武愛平編。 C 語言程序設(shè)計。長春：吉林大學(xué)出版社出版， 湖南工學(xué)院課程設(shè)計報告 附 錄 14 七 附錄（程序清單） 程序可運行 include iostream using namespace std。 include stack typedef char VertexType。 typedef int VRType。 typedef int InforType。 define MAX_VERTEX_NUM 50 // 最大頂點數(shù) int indegree[MAX_VERTEX_NUM]。 // 存放節(jié)點入度數(shù)組 int ve[MAX_VERTEX_NUM],vl[MAX_VERTEX_NUM]。 // 頂點事件 最早發(fā)生時間 和最遲發(fā)生時間數(shù)組，全局變量 初始為 0 int ee[MAX_VERTEX_NUM],el[MAX_VERTEX_NUM]。 // 弧活動 最早發(fā)生時間 和最遲發(fā)生時間數(shù)組 stackint S。 // 存放 入度為 0 的結(jié)點 stackint T。 // 存放 頂點的拓撲序列 /***********************************************************/ typedef struct ArcNode // 結(jié)點 結(jié)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1