一、拓?fù)渑判?/span>

什么是拓?fù)渑判?#xff1f;簡(jiǎn)單的說(shuō)，由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，這個(gè)操作稱之為拓?fù)渑判颉?/p>

回顧離散數(shù)學(xué)中關(guān)于偏序和全序的定義：

若集合X上的關(guān)系R是自反的，反對(duì)稱的和傳遞的，則稱R是集合X上的偏序關(guān)系。

設(shè)R是集合X上的偏序，如果對(duì)每個(gè)x，y∈X必有xRy或yRx，則稱R是集合X上的全序關(guān)系。

直觀地看，偏序指集合中僅有部分成員之間可比較，而全序指集合中全體成員之間均可比較下圖所示的兩個(gè)有向圖，圖中弧(x,y)表示x≤y，則(a)表示偏序，(b)表示全序。若在(a)的有向圖上人為地加一個(gè)表示v2≤v3的弧(符號(hào)“≤”表示v2領(lǐng)先于v3)，則(a)表示的亦為全序，且這個(gè)全序稱為拓?fù)溆行?Topological Order)，而由偏序定義得到拓?fù)溆行虻牟僮鞅闶峭負(fù)渑判颉?/p>

如何進(jìn)行拓?fù)渑判?#xff1f;

? 一、從有向圖中選取一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)，并輸出之；
? 二、從有向圖中刪去此頂點(diǎn)以及所有以它為尾的弧；
? 重復(fù)上述兩步，直至圖空，或者圖不空但找不到無(wú)前驅(qū)的頂點(diǎn)為止。沒(méi)有前驅(qū) — 入度為零，刪除頂點(diǎn)及以它為尾的弧– 弧頭頂點(diǎn)的入度減1。

AOV-網(wǎng)及其拓?fù)溆行蛐蛄挟a(chǎn)生的過(guò)程
(a)AOV-網(wǎng)；(b)輸出v6之后；(c)輸出v1之后；(d)輸出v4之后；(e)輸出v3之后；(f)輸出v2之后

最后得到該有向圖的拓?fù)溆行蛐蛄袨?#xff1a;

v6- v1- v4- v3- v2- v5

?

代碼實(shí)現(xiàn)：

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_VERTEX_NUM 20 //圖的最大頂點(diǎn)數(shù) #define MAX 30 //棧的最大容量 enum BOOL {False,True}; typedef struct ArcNode {int adjvex; //該弧所指向的頂點(diǎn)的位置struct ArcNode *nextarc; //指向下一條弧的指針 } ArcNode; //弧結(jié)點(diǎn) typedef struct {int indegree[MAX_VERTEX_NUM]; //存放各頂點(diǎn)的入度ArcNode* AdjList[MAX_VERTEX_NUM]; //指向第一條依附該頂點(diǎn)的弧的指針int vexnum,arcnum; //圖的當(dāng)前頂點(diǎn)和弧數(shù) } Graph; typedef struct //定義堆棧結(jié)構(gòu) {int elem[MAX]; //棧區(qū)int top; //棧頂指針 } Stack; void CreateGraph ( Graph & ); //生成圖的鄰接表 BOOL TopologicalSort ( Graph ); //進(jìn)行拓?fù)渑判?void FindInDegree ( Graph& ); //求圖各頂點(diǎn)的入度 void Initial ( Stack & ); //初始化一個(gè)堆棧 BOOL Push ( Stack &,int ); //將一個(gè)元素入棧 BOOL Pop ( Stack&,int & ); //將一個(gè)元素出棧 BOOL StackEmpty ( Stack ); //判斷堆棧是否為空 void main() {Graph G; //采用鄰接表結(jié)構(gòu)的圖char j='y';BOOL temp;while ( j!='N'&&j!='n' ){CreateGraph ( G ); //生成鄰接表結(jié)構(gòu)的圖temp=TopologicalSort ( G ); //進(jìn)行拓?fù)渑判騣f ( temp==False ) printf ( "該圖有回路!\n" );//若返回為False,表明該圖存在有環(huán)路else printf ( "該圖沒(méi)有回路!\n" );printf ( "拓?fù)渑判蛲戤?#xff0c;繼續(xù)進(jìn)行嗎?(Y/N)" );scanf ( " %c",&j );} }void CreateGraph ( Graph &G ) {//構(gòu)造鄰接表結(jié)構(gòu)的圖Gint i;int start,end;ArcNode *s;printf ( "請(qǐng)輸入圖的頂點(diǎn)數(shù)和弧數(shù):" );scanf ( "%d,%d",&G.vexnum,&G.arcnum ); //輸入圖的頂點(diǎn)數(shù)和弧數(shù)for ( i=1; i<=G.vexnum; i++ ) G.AdjList[i]=NULL; //初始化指針數(shù)組printf ( "請(qǐng)輸入各弧, 格式：弧尾,弧頭\n" );for ( i=1; i<=G.arcnum; i++ ){scanf ( "%d,%d",&start,&end ); //輸入弧的起點(diǎn)和終點(diǎn)s= ( ArcNode * ) malloc ( sizeof ( ArcNode ) ); //生成一個(gè)弧結(jié)點(diǎn)s->nextarc=G.AdjList[start]; //插入到鄰接表中s->adjvex=end;G.AdjList[start]=s;} } BOOL TopologicalSort ( Graph G ) {//對(duì)圖G進(jìn)行拓?fù)渑判?#xff0c;若G存在回路，返回False,否則返回Trueint i,k;int count; //計(jì)數(shù)器ArcNode* p;Stack S;FindInDegree ( G ); //求出圖中各頂點(diǎn)的入度Initial ( S ); //堆棧初始化，存放入度為零的頂點(diǎn)for ( i=1; i<=G.vexnum; i++ )if ( !G.indegree[i] ) Push ( S,i ); //入度為零的頂點(diǎn)入棧count=0; //對(duì)輸出頂點(diǎn)記數(shù)printf ( "拓?fù)渑判?" );while ( !StackEmpty ( S ) ){Pop ( S,i ); //輸出i號(hào)頂點(diǎn)并記數(shù)printf ( "%d->",i );count++;for ( p=G.AdjList[i]; p; p=p->nextarc ){k=p->adjvex; //對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接頂點(diǎn)的入度減一if ( ! ( --G.indegree[k] ) ) Push ( S,k ); //若入度為零，入棧}}printf ( "\b\b \n" );if ( count<G.vexnum ) return False; //如輸出頂點(diǎn)數(shù)少于圖中頂點(diǎn)數(shù)，則該圖有回路else return True; } void FindInDegree ( Graph &G ) {//求出圖G的各頂點(diǎn)的入度，存放在G.indegree[1..G.vexnum]中int i;ArcNode* p;for ( i=1; i<=G.vexnum; i++ )G.indegree[i]=0;for ( i=1; i<=G.vexnum; i++ ){for ( p=G.AdjList[i]; p; p=p->nextarc )G.indegree[p->adjvex]++; //弧頭頂點(diǎn)的入度加一} } void Initial ( Stack &S ) {S.top=-1; //棧頂指針初始化為-1 }BOOL Push ( Stack &S,int ch ) {//將元素ch入棧，成功返回True,失敗返回Falseif ( S.top>=MAX-1 ) return False;//判斷是否棧滿else{S.top++; //棧頂指針top加一S.elem[S.top]=ch; //入棧return True;} }BOOL Pop ( Stack &S,int &ch ) {//將棧頂元素出棧,成功返回True，并用ch返回該元素值，失敗返回Falseif ( S.top<=-1 ) return False;//判斷是否棧空else{S.top--; //棧頂指針減一ch=S.elem[S.top+1];return True;} } BOOL StackEmpty ( Stack S ) {//判斷堆棧是否已空，若空返回True,不空返回Falseif ( S.top<=-1 ) return True;else return False; }

行結(jié)果：

二、關(guān)鍵路徑

重要概念：

AOE (Activity On Edges)網(wǎng)絡(luò)?如果在無(wú)有向環(huán)的帶權(quán)有向圖中用有向邊表示一個(gè)工程中的各項(xiàng)活動(dòng)(Activity)，用邊上的權(quán)值表示活動(dòng)的持續(xù)時(shí)間(Duration)，用頂點(diǎn)表示事件(Event)，則這樣的有向圖叫做用邊表示活動(dòng)的網(wǎng)絡(luò)，簡(jiǎn)稱AOE (Activity On Edges)網(wǎng)絡(luò)。AOE網(wǎng)是一個(gè)帶權(quán)的有向無(wú)環(huán)圖。

AOE網(wǎng)絡(luò)在某些工程估算方面非常有用。例如，可以使人們了解：

??? a、完成整個(gè)工程至少需要多少時(shí)間(假設(shè)網(wǎng)絡(luò)中沒(méi)有環(huán))?

??? b、為縮短完成工程所需的時(shí)間, 應(yīng)當(dāng)加快哪些活動(dòng)?

關(guān)鍵路徑(Critical Path)?在AOE網(wǎng)絡(luò)中, 有些活動(dòng)順序進(jìn)行，有些活動(dòng)并行進(jìn)行。從源點(diǎn)到各個(gè)頂點(diǎn)，以至從源點(diǎn)到匯點(diǎn)的有向路徑可能不止一條。這些路徑的長(zhǎng)度也可能不同。完成不同路徑的活動(dòng)所需的時(shí)間雖然不同，但只有各條路徑上所有活動(dòng)都完成了，整個(gè)工程才算完成。因此，完成整個(gè)工程所需的時(shí)間取決于從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑長(zhǎng)度，即在這條路徑上所有活動(dòng)的持續(xù)時(shí)間之和。這條路徑長(zhǎng)度最長(zhǎng)的路徑就叫做關(guān)鍵路徑(Critical Path)。

如圖1就是一個(gè)AOE網(wǎng)，該網(wǎng)中有11個(gè)活動(dòng)和9個(gè)事件。每個(gè)事件表示在它之前的活動(dòng)已經(jīng)完成，在它之后的活動(dòng)可以開始。如事件v5表示a4和a5活動(dòng)已經(jīng)完成，a7和a8活動(dòng)可以開始。每個(gè)弧上的權(quán)值表示完成相應(yīng)活動(dòng)所需要的時(shí)間，如完成活動(dòng)a1需要6天，a8需要7天。

AOE網(wǎng)常用于表示工程的計(jì)劃或進(jìn)度。由于實(shí)際工程只有一個(gè)開始點(diǎn)和一個(gè)結(jié)束點(diǎn)，因此AOE網(wǎng)存在唯一的入度為0的開始點(diǎn)（又稱源點(diǎn)）和唯一的出度為0的結(jié)束點(diǎn)（又稱匯點(diǎn)），例如圖1的AOE網(wǎng)從事件v1開始，以事件v9結(jié)束。同時(shí)AOE網(wǎng)應(yīng)當(dāng)是無(wú)環(huán)的。

那么該工程待研究的問(wèn)題是：1.完成整項(xiàng)工程至少需要多少時(shí)間？2.哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？
由于在AOE-網(wǎng)中有些活動(dòng)可以并行進(jìn)行，所以完成工程的最短時(shí)間是從開始點(diǎn)到完成點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度(這里所說(shuō)的路徑長(zhǎng)度是指路徑上各活動(dòng)持續(xù)時(shí)間之和，不是路徑上弧的數(shù)目)。路徑長(zhǎng)度最長(zhǎng)的路徑叫做關(guān)鍵路徑(Critical path)。
假設(shè)開始點(diǎn)是v1，從v1到vi的最長(zhǎng)路徑叫做時(shí)間vi的最早發(fā)生時(shí)間。這個(gè)時(shí)間決定了所有以vi為尾的弧所表示的活動(dòng)的最早開始時(shí)間。我們用e(i)表示活動(dòng)ai的最早開始時(shí)間。還可以定義一個(gè)活動(dòng)開始的最遲時(shí)間l(i)，這是在不推遲整個(gè)工程完成的前提下，活動(dòng)ai最遲必須開始進(jìn)行的時(shí)間。兩者之差l(i)-e(i)意味著完成活動(dòng)ai的時(shí)間余量。當(dāng)這個(gè)時(shí)間余量等于0的時(shí)候，也即是l(i)=e(i)的活動(dòng)，我們稱其為關(guān)鍵活動(dòng)。顯然，關(guān)鍵路徑上的所有活動(dòng)都是關(guān)鍵活動(dòng)，因此提前完成非關(guān)鍵活動(dòng)并不能加快工程的進(jìn)度。
因此，分析關(guān)鍵路徑的目的是辨別哪些是關(guān)鍵活動(dòng)，以便爭(zhēng)取提高關(guān)鍵活動(dòng)的功效，縮短整個(gè)工期。

?

如何實(shí)現(xiàn)關(guān)鍵路徑？

由上面的分析可知，辨別關(guān)鍵活動(dòng)就是要找e(i)=l(i)的活動(dòng)。為了求得e(i)和l(i)，首先應(yīng)求得事件的最早發(fā)生時(shí)間ve(j)和最遲發(fā)生時(shí)間vl(j)。如果活動(dòng)ai由弧<j,k>表示，其持續(xù)時(shí)間記為dut(<j,k>)，則有如下關(guān)系
e(i) = ve(j)
l(i) = vl(k) – dut(<j,k>)
求解ve(j)和vl(j)需分兩個(gè)步進(jìn)行：
1） 從ve(0)=0開始向前推進(jìn)求得ve(j)
Ve(j) = Max{ve(i) + dut(<i,j>) };<i,j>屬于T，j=1,2…,n-1
其中T是所有以第j個(gè)頂點(diǎn)為頭的弧的集合。

2） 從vl(n-1) = ve(n-1)起向后推進(jìn)求得vl(j)
vl(i) = Min{vl(j) – dut(<i,j>};<i,j>屬于S，i=n-2,…,0
其中，S是所有以第i個(gè)頂點(diǎn)為尾的弧的集合。
這兩個(gè)遞推公式的計(jì)算必須分別在拓?fù)溆行蚝湍嫱負(fù)溆行虻那疤嵯冗M(jìn)行。也就是說(shuō)，ve(j-1)必須在vj的所有前驅(qū)的最早發(fā)生時(shí)間求得之后才能確定，而vl(j-1)必須在Vj的所有后繼的最遲發(fā)生時(shí)間求得之后才能確定。因此可以在拓?fù)渑判虻幕A(chǔ)上計(jì)算ve(j-1)和vl(j-1)。

?

具體算法描述如下：
1．?輸入e條弧<j,k>，建立AOE-網(wǎng)的存儲(chǔ)結(jié)構(gòu)。
2．?拓?fù)渑判?#xff0c;并求得ve[]。從源點(diǎn)V0出發(fā)，令ve[0]=0,按拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最早發(fā)生時(shí)間ve[i]。如果得到的拓?fù)溆行蛐蛄兄许旤c(diǎn)個(gè)數(shù)小于網(wǎng)中頂點(diǎn)數(shù)n，則說(shuō)明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終止；否則執(zhí)行步驟3。
3．?拓?fù)淠嫘?#xff0c;求得vl[]。從匯點(diǎn)Vn出發(fā)，令vl[n-1] = ve[n-1]，按逆拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最遲發(fā)生時(shí)間vl[i](n-2≥i≥2)。
4．?求得關(guān)鍵路徑。根據(jù)各頂點(diǎn)的ve和vl值，求每條弧s的最早開始時(shí)間e(s)和最遲開始時(shí)間l(s)。若某條弧滿足條件e(s) = l(s)，則為關(guān)鍵活動(dòng)。

為了能按逆序拓?fù)溆行蛐蛄械捻樞蛴?jì)算各個(gè)頂點(diǎn)的vl值，需記下在拓?fù)渑判虻倪^(guò)程中求得的拓?fù)溆行蛐蛄?#xff0c;這就需要在拓?fù)渑判蛩惴ㄖ?#xff0c;增設(shè)一個(gè)棧，以記錄拓?fù)溆行蛐蛄?#xff0c;則在計(jì)算求得各頂點(diǎn)的ve值之后，從棧頂?shù)綏５妆銥槟嫱負(fù)溆行蛐蛄小?/p>

?

?

代碼實(shí)現(xiàn)：

#include <iostream> #include <fstream> #include <queue> #include <stack> #include <Windows.h>using namespace std;#define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 //頂點(diǎn)最多個(gè)數(shù) #define LENGTH 5 //頂點(diǎn)字符長(zhǎng)度//鄰接矩陣 typedef struct _Graph {int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //鄰接矩陣char vexs[MAX_VERTEX_NUM][LENGTH]; //頂點(diǎn)數(shù)組int vexnum; //頂點(diǎn)個(gè)數(shù)int arcs; //弧的個(gè)數(shù) }Graph;int LocateVex(const Graph & g, char name[LENGTH]) {for (int i = 0; i < g.vexnum; i++){if (0 == strcmp(g.vexs[i], name)){return i;}}return -1; }//圖的建造 void CreateGraph(Graph &g) {int i = 0,j = 0;ifstream fcin("criticalpath.txt");fcin>>g.vexnum;for (i = 0; i < g.vexnum; i++){for (j = 0; j < g.vexnum; j++){g.matrix[i][j] = INFINITY;}}for (i = 0; i < g.vexnum; i++){fcin>>g.vexs[i];}fcin>>g.arcs;char arcHead[LENGTH];char arcTail[LENGTH];int weight;for (i = 0; i < g.arcs; i++){memset(arcHead, 0, LENGTH);memset(arcTail, 0, LENGTH);fcin>>arcTail>>arcHead>>weight;int x = LocateVex(g, arcHead);int y = LocateVex(g, arcTail);g.matrix[y][x] = weight;} }//v的第一個(gè)鄰接點(diǎn) int FirstAdjVex(const Graph &g, int v) {for (int i = 0; i < g.vexnum; i++){if (g.matrix[v][i] != INFINITY){return i;}}return -1; }//v相對(duì)于w的下一個(gè)鄰接點(diǎn) int NextAdjVex(const Graph &g, int v, int w) {for (int i = w + 1; i < g.vexnum; i++){if (g.matrix[v][i] != INFINITY){return i;}}return -1; }//鄰接矩陣的輸出 void PrintAdjVex(const Graph &g) {for (int i = 0; i < g.vexnum; i++){for (int j = 0; j < g.vexnum; j++){if (g.matrix[i][j] == INFINITY){cout<<"*"<<'\t';}else{cout<<g.matrix[i][j]<<'\t';}}cout<<endl;}cout<<endl; }//************************************關(guān)鍵路徑************************************begin int ve[MAX_VERTEX_NUM] = {0}; int vl[MAX_VERTEX_NUM] = {INFINITY}; //查找入度為0的頂點(diǎn) void FindInDegree(Graph g, int indegree[]) {for (int i = 0; i < g.vexnum; i++){for (int j = 0; j < g.vexnum; j++){if (g.matrix[i][j] != INFINITY){indegree[j]++;}}} }//拓?fù)渑判?bool TopologicalSort(Graph g, stack<int> &s) {int indegree[MAX_VERTEX_NUM] = {0};FindInDegree(g, indegree);queue<int> q;int i = 0;for (; i < g.vexnum; i++){if (indegree[i] == 0){q.push(i);}}int count = 0;while (!q.empty()){i = q.front();s.push(i);q.pop();count++;for (int j = 0; j < g.vexnum; j++){if (g.matrix[i][j] != INFINITY){if (!(--indegree[j])){q.push(j);}if (ve[i] + g.matrix[i][j] > ve[j]){ve[j] = ve[i] + g.matrix[i][j];}}}}if (count < g.vexnum){return false;}else{return true;} }bool CriticalPath(Graph g) {int i = 0, j =0;stack<int> s;if (!TopologicalSort(g, s)){return false;}for (i = 0; i < g.vexnum; i++){vl[i] = INFINITY;}vl[g.vexnum - 1] = ve[g.vexnum - 1];while (!s.empty()){i = s.top();s.pop();for (j = 0; j < g.vexnum; j++){if (g.matrix[i][j] != INFINITY){int tmp = g.matrix[i][j];if (vl[j] - g.matrix[i][j] < vl[i]){vl[i] = vl[j] - g.matrix[i][j];}}}}for (i = 0; i < g.vexnum; i++){for (j = 0; j < g.vexnum; j++){if (g.matrix[i][j] != INFINITY){if (ve[i] == vl[j] - g.matrix[i][j]){cout<<g.vexs[i]<<" "<<g.vexs[j]<<" "<< g.matrix[i][j]<<endl;}}}}cout<<"最長(zhǎng)路徑需要"<<vl[g.vexnum - 1]<<"天"<<endl;return true; }//************************************關(guān)鍵路徑************************************end//輔助函數(shù)，設(shè)置控制臺(tái)的顏色 void SetConsoleTextColor(WORD dwColor) {HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);if (INVALID_HANDLE_VALUE == handle){return;}SetConsoleTextAttribute(handle, dwColor); }int main(int argc, CHAR* argv[]) {Graph graph;CreateGraph(graph);SetConsoleTextColor(FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY);cout<<"************************鄰接矩陣**************************"<<endl;PrintAdjVex(graph);SetConsoleTextColor(FOREGROUND_GREEN | FOREGROUND_INTENSITY);cout<<"************************關(guān)鍵路徑**************************"<<endl<<endl;CriticalPath(graph);cout<<endl<<endl;return 0; }

criticalpath.txt文件內(nèi)容

9
V1 V2 V3 V4 V5 V6 V7 V8 V9
11
V1 V2 6
V1 V3 4
V1 V4 5
V2 V5 1
V3 V5 1
V4 V6 2
V5 V7 9
V5 V8 7
V6 V8 4
V7 V9 2
V8 V9 4

運(yùn)行結(jié)果：

總結(jié)

以上是生活随笔為你收集整理的拓扑排序和关键路径的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。