20拓?fù)渑判蚝完P(guān)鍵路徑(編輯修改稿)
2024-08-21 15:49 本頁面
【文章內(nèi)容簡介】 t v) {//如何確定 v for (v=0。 v。 ++v) visited[v] = FALSE。 // 訪問標(biāo)志數(shù)組初始化 InitStack(S)。//存放頂點，按照出 DFS的次序 for (v=0。 v。 ++v) { if (!visited[v]) DFST(G, v)。 // 對尚未訪問的頂點調(diào)用 DFS } while(!Empty(S)){//輸出拓?fù)渑判虻慕Y(jié)果 Pop(S, v)。 printf(“%d”, v)} } 拓?fù)渑判?方法 2 void DFST(Graph G, int v) { // 從頂點 v出發(fā)，深度優(yōu)先搜索遍歷連通圖 G visited[v] = TRUE。 for(w=FirstAdjVex(G, v)。 w=0。 w=NextAdjVex(G,v,w)) {if (!visited[w]) DFST(G, w)。} // 對 v的尚未訪問的鄰接頂點 w遞歸調(diào)用 DFST Push(S, v)。//頂點 v的 DFS函數(shù)執(zhí)行完畢 } // DFST 拓?fù)渑判?練習(xí) a c g b d h f e 寫出下圖的所有的拓?fù)湫蛄? 關(guān)鍵路徑 源點 匯點 事件 活動及其持續(xù)的時間 AOE網(wǎng) (Activity on Edge):邊表示活動網(wǎng)。 v8 v1 V2 V3 v4 v5 v6 v7 v9 a6=2 假設(shè)以 AOE網(wǎng)表示一個施工流圖，弧上的權(quán)值表示完成該項子工程所需的時間。 完成整個工程至少需要多少時間？ 哪些活動是影響工程進度的關(guān)鍵？ 關(guān)鍵路徑 AOE網(wǎng)是一個帶權(quán)的有向無環(huán)圖，可用來估算工程的完成時間。 ?路徑最長的路徑叫做關(guān)鍵路徑 ?影響工程進度的活動叫關(guān)鍵活動 ?關(guān)鍵路徑上的活動一定是關(guān)鍵活動 關(guān)鍵路徑 如何求關(guān)鍵路徑 ?用 e(i)和 l(i)分別表示活動 ai的最早開始時間和最遲開始時間 ?e(i)l(i)為活動 ai 的時間余量 ?e(i)=l(i)的活動是關(guān)鍵活動 如何求關(guān)鍵路徑 ve(i)： 表示事件 i的最早開始時間 vl(i)： 表示事件 i的最遲開始時間 已知 ve(1)=0， 計算其余頂點的 ve值要按照頂點拓?fù)渑判蚝蟮拇涡?進行 ve(j)=max(ve(i) + dut(i,j)) i,j∈ T,T是以 j為頭的弧的集合 v8 v1 V2 V3 v5 v7 v9 Vi到 Vj的最長路徑 如何求關(guān)鍵路徑 vl(n1)=ve(n1)，然后 按照頂點 逆拓?fù)渑判?后的次序求其余頂點的 vl vl(i)=min(vl(j) dut(i,j)) i,j∈ S,S是以 i為尾的弧的集合 v8 v1 V2 V3 v5 v7 v9 如何求關(guān)鍵路徑 用 e(i)和 l(i)分別表示活動 ai的最早開始間和最遲開始時間 顯然有： e(i)=ve(j) l(i)=vl(k)dut(j,k) j k ai 如何求關(guān)鍵路徑 v8 v1 V2 V3 v4 v5 v6 v7 v9 a6=2 v1 v2 v3 v4 v5 v6 v7 v8 v9 ve vl
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1