數(shù)據(jù)結(jié)構(gòu)與算法-關(guān)鍵路徑

一、定義

在一個(gè)表示工程的帶權(quán)有向圖中，用頂點(diǎn)表示事件，用有向邊表示活動(dòng)，用邊上的權(quán)值表示活動(dòng)的持續(xù)時(shí)間，這種有向圖的邊表示活動(dòng)的網(wǎng)，我們稱之為AOE網(wǎng)(Acitivity On Edge Network)。
AOE網(wǎng)中，沒(méi)有入邊的頂點(diǎn)稱為始點(diǎn)或源點(diǎn)。
AOE網(wǎng)中，沒(méi)有出邊的頂點(diǎn)稱為終點(diǎn)或匯點(diǎn)。
正常情況下，AOE網(wǎng)中，只有一個(gè)源點(diǎn)一個(gè)匯點(diǎn)。
AOV網(wǎng)和AOE網(wǎng)都是用來(lái)工程建模的。但是它們還是有很大的不同。

  1. AOV網(wǎng)是頂點(diǎn)表示活動(dòng)的網(wǎng)，它只是描述活動(dòng)之間的制約關(guān)系。
  2. AOE網(wǎng)是用邊表示活動(dòng)的網(wǎng)，邊上的權(quán)值表示活動(dòng)持續(xù)的時(shí)間。

我們把路徑上各活動(dòng)持續(xù)的時(shí)間之和稱為路徑長(zhǎng)度，從源點(diǎn)到匯點(diǎn)具有最大長(zhǎng)度的路徑叫關(guān)鍵路徑。在關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)。

相關(guān)參數(shù)

  1. 事件的最早發(fā)生時(shí)間etv(earliest time of vertex)：即頂點(diǎn)Vk的最早發(fā)生時(shí)間。
  2. 事件的最晚發(fā)生時(shí)間ltv(lastest time of vertex)：即頂點(diǎn)Vk的最晚發(fā)生時(shí)間，也就是每個(gè)頂點(diǎn)對(duì)應(yīng)的事件最晚需要開(kāi)始的時(shí)間，超出此時(shí)間，整個(gè)工程將會(huì)延誤整個(gè)工期。
  3. 活動(dòng)的最早開(kāi)工時(shí)間ete(earliest time of edge)：即弧ak的最早發(fā)生時(shí)間。
  4. 活動(dòng)的最晚開(kāi)工時(shí)間lte(lastest time of edge)：即弧ak的最晚發(fā)生時(shí)間，也就是不推遲工期的最晚開(kāi)工時(shí)間。

二、算法思路

  1. 求事件的最早發(fā)生時(shí)間etv的過(guò)程，就是我們從頭到尾找拓?fù)湫蛄械倪^(guò)程。
  2. 計(jì)算tlv其實(shí)就是把拓?fù)湫蛄械惯^(guò)來(lái)進(jìn)行。

三、代碼實(shí)現(xiàn)

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXEDGE 30
#define MAXVEX 30
#define INFINITYC 65535

typedef int Status;    /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */

/* 鄰接矩陣結(jié)構(gòu) */
typedef struct
{
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;

/* 鄰接表結(jié)構(gòu)****************** */
//邊表結(jié)點(diǎn)
typedef struct EdgeNode
{
    //鄰接點(diǎn)域，存儲(chǔ)該頂點(diǎn)對(duì)應(yīng)的下標(biāo)
    int adjvex;
    //用于存儲(chǔ)權(quán)值，對(duì)于非網(wǎng)圖可以不需要
    int weight;
    //鏈域，指向下一個(gè)鄰接點(diǎn)
    struct EdgeNode *next;
}EdgeNode;

//頂點(diǎn)表結(jié)點(diǎn)
typedef struct VertexNode
{
    //頂點(diǎn)入度
    int in;
    //頂點(diǎn)域，存儲(chǔ)頂點(diǎn)信息
    int data;
    //邊表頭指針
    EdgeNode *firstedge;
}VertexNode, AdjList[MAXVEX];

typedef struct
{
    AdjList adjList;
    //圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)
    int numVertexes,numEdges;
}graphAdjList,*GraphAdjList;

/* **************************** */

/* 關(guān)于AOE網(wǎng)圖的存儲(chǔ)代碼段-Begin */
//1.完成AOE網(wǎng)圖關(guān)于鄰接矩陣的存儲(chǔ)
void CreateMGraph(MGraph *G)/* 構(gòu)件圖 */
{
    int i, j;
    /* printf("請(qǐng)輸入邊數(shù)和頂點(diǎn)數(shù):"); */
    G->numEdges=13;
    G->numVertexes=10;

    for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */
    {
        G->vexs[i]=i;
    }

    for (i = 0; i < G->numVertexes; i++)/* 初始化圖 */
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            if (i==j)
                G->arc[i][j]=0;
            else
                G->arc[i][j]=INFINITYC;
        }
    }

    G->arc[0][1]=3;
    G->arc[0][2]=4;
    G->arc[1][3]=5;
    G->arc[1][4]=6;
    G->arc[2][3]=8;
    G->arc[2][5]=7;
    G->arc[3][4]=3;
    G->arc[4][6]=9;
    G->arc[4][7]=4;
    G->arc[5][7]=6;
    G->arc[6][9]=2;
    G->arc[7][8]=5;
    G->arc[8][9]=3;

}


//2.將鄰近矩陣轉(zhuǎn)化成鄰接表
void CreateALGraph(MGraph G,GraphAdjList *GL){

    int i,j;
    EdgeNode *e;

    *GL = (GraphAdjList)malloc(sizeof(graphAdjList));

    (*GL)->numVertexes=G.numVertexes;
    (*GL)->numEdges=G.numEdges;

    //讀入頂點(diǎn)信息，建立頂點(diǎn)表
    for(i= 0;i <G.numVertexes;i++)
    {
        (*GL)->adjList[i].in=0;
        (*GL)->adjList[i].data=G.vexs[i];
        //將邊表置為空表
        (*GL)->adjList[i].firstedge=NULL;
    }

    //建立邊表
    for(i=0;i<G.numVertexes;i++)
    {
        for(j=0;j<G.numVertexes;j++)
        {
            if (G.arc[i][j]!=0 && G.arc[i][j]<INFINITYC)
            {
                e=(EdgeNode *)malloc(sizeof(EdgeNode));
                //鄰接序號(hào)為j
                e->adjvex=j;
                e->weight=G.arc[i][j];
                //將當(dāng)前頂點(diǎn)上的指向的結(jié)點(diǎn)指針賦值給e
                e->next=(*GL)->adjList[i].firstedge;
                //將當(dāng)前頂點(diǎn)的指針指向e
                (*GL)->adjList[i].firstedge=e;
                (*GL)->adjList[j].in++;

            }
        }
    }
}
/* 關(guān)于AOE網(wǎng)圖的存儲(chǔ)代碼段-End! */
int *etv,*ltv; /* 事件最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間數(shù)組，全局變量 */
int *stack2;   /* 用于存儲(chǔ)拓?fù)湫蛄械臈?*/
int top2;       /* 用于stack2的指針*/

//拓?fù)渑判?Status TopologicalSort(GraphAdjList GL){

    //若GL無(wú)回路,則輸出拓?fù)渑判蛐蛄星曳祷貭顟B(tài)OK, 否則返回狀態(tài)ERROR;
    EdgeNode *e;
    int i,k,gettop;
    //棧指針下標(biāo);
    int top = 0;
    //用于統(tǒng)計(jì)輸出的頂點(diǎn)個(gè)數(shù).作為拓?fù)渑判蚴欠翊嬖诨芈返呐袛嘁罁?jù);
    int count = 0;
    //建棧,將入度in = 0的頂點(diǎn)入棧;
    int *stack = (int *)malloc(GL->numVertexes * sizeof(int));

    //遍歷頂點(diǎn)表上入度in ?= 0 入棧
    for (i = 0; i < GL->numVertexes;i++) {
        //printf("%d %d\n",i,GL->adjList[i].in);
        if ( 0 == GL->adjList[i].in ) {
            stack[++top] = i;
        }
    }

    //* stack2 的棧指針下標(biāo)
    top2 = 0;
    //* 初始化拓?fù)湫蛄袟?    stack2 = (int *)malloc(sizeof(int) * GL->numVertexes);
    //* 事件最早發(fā)生時(shí)間數(shù)組
    etv = (int *)malloc(sizeof(GL->numVertexes * sizeof(int)));
    //* 初始化etv 數(shù)組
    for (i = 0 ; i < GL->numVertexes; i++) {
        //初始化
        etv[i] = 0;
    }

    printf("TopologicSort:\t");
    while (top != 0) {
        gettop = stack[top--];
        printf("%d -> ", GL->adjList[gettop].data);
        count++;

        //將彈出的頂點(diǎn)序號(hào)壓入拓?fù)渑判虻臈Ｖ?
        stack2[++top2] = gettop;
        
        //例如gettop為V0 ,那么與V0相連接的結(jié)點(diǎn)就有etv[1] = 3; etv[2] = 4;
        //例如gettop為V1 ,那么與V1連接的結(jié)點(diǎn)就有etv[4]= 3+6=9; etv[3] = 8;
        //例如gettop為V2 ,那么與V2連接的結(jié)點(diǎn)就有etv[5]= 4+7=11; etv[3] = 12;
        //例如gettop為V3 ,那么與V3連接的結(jié)點(diǎn)就有etv[4]= 12+3=15;
        for(e = GL->adjList[gettop].firstedge; e; e = e->next)
        {
            k = e->adjvex;
            
            //將i頂點(diǎn)連接的鄰接頂點(diǎn)入度減1,如果入度減一后為0,則入棧
            if(!(--GL->adjList[k].in))
                stack[++top] = k;

            //求各頂點(diǎn)事件的最早發(fā)生的時(shí)間etv值
            //printf("etv[gettop]+e->weight = %d\n",etv[gettop]+e->weight);
            //printf("etv[%d] = %d\n",k,etv[k]);
            if ((etv[gettop] + e->weight) > etv[k]) {
                etv[k] = etv[gettop] + e->weight;
            }
        }

    }
    printf("\n");
    
    //打印etv(事件最早發(fā)生時(shí)間數(shù)組)
//    for (i = 0; i < GL->numVertexes; i++) {
//        printf("etv[%d] = %d\n",i,etv[i]);
//    }
//    printf("\n");
    
    if(count < GL->numVertexes)
        return ERROR;
    else
        return OK;
    return OK;
}

//求關(guān)鍵路徑, GL為有向網(wǎng),則輸出G的各項(xiàng)關(guān)鍵活動(dòng);
void CriticalPath(GraphAdjList GL){
    EdgeNode *e;
    int i,gettop,k,j;
    
    //聲明活動(dòng)最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間變量;
    int ete,lte;
    
    //求得拓?fù)湫蛄?計(jì)算etv數(shù)組以及stack2的值
    TopologicalSort(GL);
   
    //打印etv數(shù)組(事件最早發(fā)生時(shí)間)
    printf("etv:\n");
    for(i = 0; i < GL->numVertexes; i++)
        printf("etv[%d] = %d \n",i,etv[i]);
    printf("\n");
    
    //事件最晚發(fā)生時(shí)間數(shù)組
    ltv = (int *)malloc(sizeof(int) * GL->numVertexes);
   
    //初始化ltv數(shù)組
    for (i = 0; i < GL->numVertexes; i++) {
        //初始化ltv數(shù)組. 賦值etv最后一個(gè)事件的值
        ltv[i] = etv[GL->numVertexes-1];
        //printf("ltv[%d] = %d\n",i,ltv[i]);
    }
    
    //計(jì)算ltv(事件最晚發(fā)生時(shí)間) 出棧求ltv
    while (top2 != 0) {
        
        //出棧(棧頂元素)
        gettop = stack2[top2--];
        
        //找到與棧頂元素連接的頂點(diǎn); 例如V0是與V1和V2連接
        for (e = GL->adjList[gettop].firstedge; e; e = e->next) {
            //獲取與gettop 相連接的頂點(diǎn)
            k = e->adjvex;
            //計(jì)算min(ltv[k]-e->weight,ltv[gettop])
            if (ltv[k] - e->weight < ltv[gettop]) {
                //更新ltv 數(shù)組
                ltv[gettop] = ltv[k] - e->weight;
            }
        }
    }
    
    //打印ltv 數(shù)組
    printf("ltv:\n");
    for (i = 0 ; i < GL->numVertexes; i++) {
        printf("ltv[%d] = %d \n",i,ltv[i]);
    }
    
    printf("\n");
    //求解ete,lte 并且判斷l(xiāng)te與ete 是否相等.相等則是關(guān)鍵活動(dòng);
    //2層循環(huán)(遍歷頂點(diǎn)表,邊表)
    for(j=0; j<GL->numVertexes;j++)
    {
        for (e = GL->adjList[j].firstedge; e; e = e->next) {
            //獲取與j連接的頂點(diǎn);
            k = e->adjvex;
            //ete 就是表示活動(dòng) <Vk, Vj> 的最早開(kāi)工時(shí)間, 是針對(duì)這條弧來(lái)說(shuō)的.而這條弧的弧尾頂點(diǎn)Vk 的事件發(fā)生了, 它才可以發(fā)生. 因此ete = etv[k];
            ete = etv[j];
            //lte 表示活動(dòng)<Vk, Vj> 的最晚開(kāi)工時(shí)間, 但此活動(dòng)再晚也不能等Vj 事件發(fā)生才開(kāi)始,而是必須在Vj 事件之前發(fā)生. 所以lte = ltv[j] - len<Vk, Vj>.
            lte = ltv[k]-e->weight;
            //如果ete == lte 則輸出j,k以及權(quán)值;
            if (ete == lte) {
                printf("<%d-%d> length:%d\n",GL->adjList[j].data, GL->adjList[k].data, e->weight);
            }
        }
    }
    
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, 關(guān)鍵路徑的求解!\n");
    MGraph G;
    GraphAdjList GL;
    CreateMGraph(&G);
    CreateALGraph(G,&GL);
    
    //拓?fù)渑判?    //TopologicalSort(GL);
    
    //關(guān)鍵路徑
    CriticalPath(GL);

    return 0;
}

四、算法復(fù)雜度

該算法使用了拓?fù)渑判?，拓?fù)渑判虻乃惴◤?fù)雜度為O(n+e)，因此求解關(guān)鍵路徑的算法復(fù)雜度也為O(n+e)。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容