| 數(shù)據(jù)結(jié)構(gòu)C++ | 您所在的位置：網(wǎng)站首頁(yè) › 屬虎的男生和屬什么的相配 › 數(shù)據(jù)結(jié)構(gòu)C++ |
|
數(shù)據(jù)結(jié)構(gòu)C++——關(guān)鍵路徑
文章目錄
數(shù)據(jù)結(jié)構(gòu)C++——關(guān)鍵路徑一、前言二、關(guān)鍵路徑的概念三、關(guān)鍵路徑的實(shí)現(xiàn)①關(guān)鍵路徑的實(shí)現(xiàn)原理②關(guān)鍵路徑的代碼實(shí)現(xiàn)③測(cè)試的全部代碼
四、總結(jié)
一、前言
理解關(guān)鍵路徑需要掌握拓?fù)渑判蚝袜徑颖淼南嚓P(guān)知識(shí)，由于此部分筆者在之前的文章中已經(jīng)介紹過(guò)，此處不再過(guò)多贅述，對(duì)此部分知識(shí)還不熟練的讀者，歡迎移步此文章，共同學(xué)習(xí)！： 數(shù)據(jù)結(jié)構(gòu)C++——拓?fù)渑判?數(shù)據(jù)結(jié)構(gòu)C++——圖的鄰接矩陣和鄰接表 二、關(guān)鍵路徑的概念（1）AOE-網(wǎng):與AOV-網(wǎng)相對(duì)應(yīng)的是AOE-網(wǎng) , 即以邊表示活動(dòng)的網(wǎng)。AOE-網(wǎng)是一個(gè)帶權(quán)的有向無(wú)環(huán)圖，其中，頂點(diǎn)表示事件，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)的時(shí)間。 （2）源點(diǎn)和匯點(diǎn)：由于整個(gè)工程中只有一個(gè)開(kāi)始點(diǎn)和一個(gè)完成點(diǎn)，故在正常的情況（無(wú)環(huán)）下，網(wǎng)中只有一個(gè)入度為零的點(diǎn)，稱作源點(diǎn)，也只有一個(gè)出度為零的點(diǎn)，稱作匯點(diǎn)。 （3）關(guān)鍵路徑和關(guān)鍵活動(dòng)：要估算整項(xiàng)工程完成的最短時(shí)間， 就是要找一條從源點(diǎn)到 匯點(diǎn)的帶權(quán)路徑長(zhǎng)度最長(zhǎng)的路徑，稱為關(guān)鍵路徑。關(guān)鍵路徑上的活動(dòng)叫做關(guān)鍵活動(dòng)，這些活動(dòng)是影響工程進(jìn)度的關(guān)鍵， 它們的提前或拖延將使整個(gè)工程提前或拖延。 三、關(guān)鍵路徑的實(shí)現(xiàn) ①關(guān)鍵路徑的實(shí)現(xiàn)原理關(guān)鍵路徑算法的實(shí)現(xiàn)需要引入兩個(gè)輔助數(shù)組ve[i]和vl[i]，分別用來(lái)記錄事件vi的最早發(fā)生時(shí)間和記錄事件vi的最遲發(fā)生時(shí)間。遍歷整個(gè)topo數(shù)組，計(jì)算出其中存放的頂點(diǎn)（事件）最早發(fā)生時(shí)間，按逆拓?fù)湫蛄星蟪雒總€(gè)事件的最遲發(fā)生時(shí)間。求出每個(gè)邊（活動(dòng)）的最早開(kāi)始時(shí)間和最晚開(kāi)始時(shí)間，邊（活動(dòng)）最早開(kāi)始時(shí)間和最晚開(kāi)始時(shí)間相等的邊（活動(dòng)）即為關(guān)鍵活動(dòng)。由關(guān)鍵活動(dòng)形成的由源點(diǎn)到匯點(diǎn)的每一條路徑就是關(guān)鍵路徑。 ②關(guān)鍵路徑的代碼實(shí)現(xiàn)關(guān)鍵路徑的代碼實(shí)現(xiàn) 關(guān)鍵路徑算法思路： 1：給每個(gè)時(shí)間的最早發(fā)生時(shí)間置初值為0 2：取得拓?fù)湫蛄兄械捻旤c(diǎn)，并遍歷該頂點(diǎn)的所有鄰接點(diǎn)，更新鄰接點(diǎn)（事件）發(fā)生的最早時(shí)間 3：取得逆拓?fù)湫蛄兄械捻旤c(diǎn)，遍歷該頂點(diǎn)的所有鄰接點(diǎn)，更新鄰接點(diǎn)（事件）發(fā)生的最遲時(shí)間 4：遍歷頂點(diǎn)表，輸出最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間相等的某邊（活動(dòng)）所依附的兩個(gè)頂點(diǎn)輸出 /*---------關(guān)鍵路徑算法---------*/ Status CriticalPath(ALGraph& G) { //G為鄰接表存儲(chǔ)的有向圖，輸出G的各項(xiàng)關(guān)鍵活動(dòng) if (!TopologicalSort(G, topo)) return ERROR; //調(diào)用拓?fù)渑判蛩惴ǎ雇負(fù)湫蛄斜４嬖趖opo中，若調(diào)用失敗，則存在有向環(huán)，返回ERROR int n = G.vexnum;//n為頂點(diǎn)個(gè)數(shù) for (int i = 0; i int j = p->adjvex;//j為鄰接頂點(diǎn)的序號(hào) if (ve[j] weight)//更新頂點(diǎn)j的最早發(fā)生時(shí)間ve[j] ve[j] = ve[k] + p->weight; p = p->nextarc;//p指向k的下一個(gè)鄰接頂點(diǎn) } } for (int i = 0; i = 0; i--) { int k = topo[i];//取得拓?fù)湫蛄兄械捻旤c(diǎn)序號(hào)k ArcNode* p = new ArcNode; p = G.vertices[k].firstarc;//p指向k的第一個(gè)鄰接頂點(diǎn) while (p != NULL) {//根據(jù)k的鄰接點(diǎn)，更新k的最遲發(fā)生時(shí)間 int j = p->adjvex;//j為鄰接頂點(diǎn)的序號(hào) if (vl[k] > vl[j] - p->weight)//更新頂點(diǎn)k的最遲發(fā)生時(shí)間vl[k] vl[k] = vl[j] - p->weight; p = p->nextarc;//p指向k的下一個(gè)鄰接頂點(diǎn) } } /*-----------判斷每一個(gè)活動(dòng)是否為關(guān)鍵活動(dòng)--------------*/ for (int i = 0; i int j = p->adjvex;//j為鄰接頂點(diǎn)的序號(hào) int e = ve[i];//計(jì)算活動(dòng)的最早開(kāi)始時(shí)間 int l = vl[j] - p->weight;//計(jì)算活動(dòng)的最遲開(kāi)始時(shí)間 if (e == l) cout int adjvex; OtherInfo weight; struct ArcNode* nextarc; }ArcNode; typedef struct VNode { VerTexType data; ArcNode* firstarc; }VNode,AdjList[MVNum]; typedef struct { int vexnum, arcnum; AdjList vertices; }ALGraph; /*--------拓?fù)渑判蜉o助數(shù)組的存儲(chǔ)結(jié)構(gòu)--------*/ int indegree[MVNum];//存放各頂點(diǎn)入度 int topo[MVNum];//記錄拓?fù)湫蛄械捻旤c(diǎn)編號(hào) /*-------關(guān)鍵路徑算法的兩個(gè)輔助數(shù)組---------*/ int ve[MVNum];//事件vi的最早發(fā)生時(shí)間 int vl[MVNum];//事件vi的最遲發(fā)生時(shí)間 Status InitStack(SqStack& S) { S.base = new SElemType[MaxInt]; if (!S.base) return ERROR; S = S.base; S.stacksize = MaxInt; return OK; } Status StackEmpty(SqStack S) { if (S == S.base) return OK; return ERROR; } Status Push(SqStack& S, SElemType e) { if (S - S.base == S.stacksize) return ERROR; *S = e; S++; return OK; } Status Pop(SqStack& S, SElemType& e) { if (S.base == S) return ERROR; S--; e = *S; return OK; } int LocateVex(ALGraph G, VerTexType v) { for (int i = 0; i cin >> G.vexnum >> G.arcnum; for (int i = 0; i VerTexType v1, v2; int w=0; cin >> v1 >> v2 >> w; int i = LocateVex(G, v1); int j = LocateVex(G, v2); ArcNode* p1 = new ArcNode; p1->adjvex = j; p1->weight = w; p1->nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc = p1; } } void FindInDegree(ALGraph G, int indegree[]) { for (int i = 0; i ArcNode* p = new ArcNode;//定義指向各個(gè)邊結(jié)點(diǎn)的指針 p = G.vertices[j].firstarc; while (p) {//當(dāng)p未指到單個(gè)鏈表的末尾時(shí)繼續(xù)循環(huán) if (p->adjvex == i)//當(dāng)某邊結(jié)點(diǎn)鄰接點(diǎn)域等于i時(shí)，計(jì)數(shù)變量++ cnt++; p = p->nextarc;//指針不斷向后指 } indegree[i] = cnt;//將計(jì)數(shù)結(jié)果保留在indegree數(shù)組中 } } } /*----------拓?fù)渑判蛩惴?--------------*/ Status TopologicalSort(ALGraph G, int topo[]) { //有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu) //若G無(wú)回路，則生成G的一個(gè)拓?fù)渑判騮opo[]并返回OK，否則ERROR FindInDegree(G, indegree);//求出各結(jié)點(diǎn)的入度存入數(shù)組indegree中 SqStack S; InitStack(S);//初始化棧 for (int i = 0; i int i = 0; Pop(S, i);//將棧頂頂點(diǎn)vi出棧 topo[m] = i;//將vi保存在拓?fù)湫蛄袛?shù)組topo中 ++m;//對(duì)輸出頂點(diǎn)計(jì)數(shù) ArcNode* p = new ArcNode; p = G.vertices[i].firstarc;//p指向vi的第一個(gè)鄰接點(diǎn) while (p != NULL) { int k = p->adjvex;//vk為vi的鄰接點(diǎn) --indegree[k];//vi的每個(gè)鄰接點(diǎn)的入度減一 if (indegree[k] == 0) Push(S, k);//若入度減為0，則入棧 p = p->nextarc;//p指向頂點(diǎn)vi下一個(gè)鄰接結(jié)點(diǎn) } } if (m int k = topo[i];//取得拓?fù)湫蛄兄械捻旤c(diǎn)序號(hào)k ArcNode* p = new ArcNode; p = G.vertices[k].firstarc;//p指向k的第一個(gè)鄰接頂點(diǎn) while (p != NULL) { int j = p->adjvex;//j為鄰接頂點(diǎn)的序號(hào) if (ve[j] weight)//更新頂點(diǎn)j的最早發(fā)生時(shí)間ve[j] ve[j] = ve[k] + p->weight; p = p->nextarc;//p指向k的下一個(gè)鄰接頂點(diǎn) } } for (int i = 0; i = 0; i--) { int k = topo[i];//取得拓?fù)湫蛄兄械捻旤c(diǎn)序號(hào)k ArcNode* p = new ArcNode; p = G.vertices[k].firstarc;//p指向k的第一個(gè)鄰接頂點(diǎn) while (p != NULL) {//根據(jù)k的鄰接點(diǎn)，更新k的最遲發(fā)生時(shí)間 int j = p->adjvex;//j為鄰接頂點(diǎn)的序號(hào) if (vl[k] > vl[j] - p->weight)//更新頂點(diǎn)k的最遲發(fā)生時(shí)間vl[k] vl[k] = vl[j] - p->weight; p = p->nextarc;//p指向k的下一個(gè)鄰接頂點(diǎn) } } /*-----------判斷每一個(gè)活動(dòng)是否為關(guān)鍵活動(dòng)--------------*/ for (int i = 0; i int j = p->adjvex;//j為鄰接頂點(diǎn)的序號(hào) int e = ve[i];//計(jì)算活動(dòng)的最早開(kāi)始時(shí)間 int l = vl[j] - p->weight;//計(jì)算活動(dòng)的最遲開(kāi)始時(shí)間 if (e == l) cout |
| CopyRight 2018-2019 實(shí)驗(yàn)室設(shè)備網(wǎng) 版權(quán)所有 |