程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 圖-----------拓撲排序+AOE網絡關鍵路徑

圖-----------拓撲排序+AOE網絡關鍵路徑

編輯：C++入門知識

1.拓撲排序（1）舉個例子，要學習某些課程必須先學過一些課程

用圖把這個東東描述出來就變成：

那麼，問題來啦，是否可以找到一個序列，使得這個序列上的所有課程都滿足：先修課程在後修的課程前面？這樣的序列就是拓撲序列..... (2)怎麼求拓撲序列? 簡單的說是不斷去掉沒有前驅的點，得到的這些點就是拓撲序列；還是上面的例子： step1:9沒有前驅，去掉(和它相關的邊也去掉)； step2:這時候有8,6,4,三個點沒有前驅，隨便選一個去掉（這個以隨便就說明拓撲序列不唯一喔~） ......(下面，你懂的~) (3)算法要用到沒有前驅所以要圖的入度；上面的模擬過程知道實際上是BFS: a.建立入度為零的頂點排隊 b.掃描頂點表，將入度為0的頂點入隊； c.while（排隊不空） { 輸出隊頭結點；記下輸出結點的數目；刪去與之關聯的出邊；若有入度為0的結點，入隊 } d.若輸出結點個數小於總的頂點個數，則輸出有環路； (4)象征性的貼一小段代碼：

void topsort(Adgraph* G)  
{  
    queue<int> Q;  
    int x,count=0;  
    for(int i=1; i<=G->n; i++)  
        if(G->Ad[i].indegree==0) Q.push(i);//入度為0的頂點入隊   
    while(!Q.empty())  
    {  
        x=Q.front();  
        Q.pop();  
        cout << G->Ad[x].element;//輸出點   
        count++;//計數器++   
        link *m=G->Ad[x].firstedge;  
        while(m!=NULL)  
        {  
            if((--G->Ad[m->v].indegree)==0) Q.push(m->v) ;  
            //每當去掉頂點，入度--；如果這時候它變成沒有前驅的頂點，入隊   
            m=m->next;  
        }  
    }  
    if (count<G->n) cout<<"圖中有環路" << endl;  
}  

void topsort(Adgraph* G)
{
    queue<int> Q;
    int x,count=0;
    for(int i=1; i<=G->n; i++)
        if(G->Ad[i].indegree==0) Q.push(i);//入度為0的頂點入隊
    while(!Q.empty())
    {
        x=Q.front();
        Q.pop();
        cout << G->Ad[x].element;//輸出點
        count++;//計數器++
        link *m=G->Ad[x].firstedge;
        while(m!=NULL)
        {
            if((--G->Ad[m->v].indegree)==0) Q.push(m->v) ;
//每當去掉頂點，入度--；如果這時候它變成沒有前驅的頂點，入隊
            m=m->next;
        }
    }
    if (count<G->n) cout<<"圖中有環路" << endl;
}

2.AOE網絡（1）AOE是什麼東東？

a. AOE上頂點表示事件，邊表示活動，邊上的權值表示活動需要的時間，入度為0的點叫做源點（V1）,出度為0的點叫做結束點（v9）; b.我們要解決的問題：從源點到達結束點經過的活動的最大（最大喔！）時間，比如上面的紅線部分就是完成最大花費時間，關鍵路徑就是這條長度最長的路徑（a1->a4->a7->a10或者a1->a4->a8->a11[關鍵路徑不唯一]） (2)問題怎麼求解？ a.事件(eVent)的最早(Early)發生時間---源點到這個點的最長路徑---VE[j]； b.事件(eVent)的最遲(Late)發生時間---在保證匯點Vn在VE(n)時刻完成的前提下，事件Vk的允許的最遲開始時間-----VL(k) c.活動(Activity)的最早(Early)開始如果這個活動i是由<事件j,事件k>之間的，那麼容易知道活動i最早的開始時間和時間j最早的發生時間是一樣的 AE(i) = VE(j); d.活動(Activity)的最遲(Late)發生如果這個活動i是由<事件j,事件k>之間的,為不推遲工期，活動i的最遲開始時間AL(i)應該是i的最遲完成時間VL(k)減去i的持續時間，即AL(i) = VL(k) - ACT[j][k]; e.松弛時間（Share time）:就是這個活動最遲開始時間和最早開始時間的差：AL[i]-AE[i] 松弛時間為0，那麼這個活動為關鍵活動；（上面的東東有一個大前提：一個活動開始，那麼它之前的活動必須全部完成） f.逆拓撲序列：拓撲序列反過來； g.怎麼樣求AE,VE,AL,VL? 基於上面的定義，我們可以用式子簡單表示： VE:從VE[1]=0開始向前遞推，VE[i]=max{VE[j]+ACT<Vj,Vi>},其中<Vj,Vi>是集合｛指向Vi的所有邊｝中的一個元素； VL:從VL[n]=VE[n]開始反向遞推，VL[i]=min{VL[j]-ACT<Vi,Vj>},期中<Vi,Vj>是集合｛從Vi發出的所有邊｝中的一個元素； AE:活動k用<Vi,Vj>表示，AE[k]=VE[i]; AL:活動k用<Vi,Vj>表示,AL[k]=AL[j]-ACT<Vi,Vj> h.算法 1.建立鄰接表； 2.從源點出發，令VE[1]=0,按照拓撲順序求解VE[i]（判斷有沒有環）； 3.從結束點出發，VL[n]=VE[n],按照逆拓撲序列求解VL[i]； 4.求解AE[i],AL[i]； 5.如果是關鍵活動，輸出； hint:以上全部是自己YY的，不是按照什麼專業術語嚴格證明的，大家看懂個大概，嚴格的定義和求解還是看書吧！象征性的再貼一段代碼~

//Topsort And AOE      
#include <iostream>      
#include<stack>      
#include<queue>      
#include<cstdio>      
using namespace std;    
struct link    
{    
    int v;//事件編號      
    int count;//活動的編號      
    int weight;//活動的時間      
    link * next;    
};    
struct node    
{    
    int indegree;//入度      
    char element;//事件      
    struct link* firstedge;    
};//頭結點      
struct Adgraph    
{    
    int n,e;    
    struct node Ad[101];    
};//鄰接表      
void Create_AOE(struct Adgraph* G)    
{    
    int k,i,j,t;    
    cin >> G->n >> G->e;//節點和邊      
    for (k=1; k<=G->n; k++)    
    {    
        cin >> G->Ad[k].element;    
        G->Ad[k].firstedge=NULL;    
        G->Ad[k].indegree=0;    
    }//頭結點的初始化      
    for(k=1; k<=G->e; k++)    
    {    
        printf("輸入兩個頂點(事件編號),邊的權值(活動時間)\n");    
        cin >> j >> i >> t;    
        G->Ad[i].indegree++;    
        link* p=new link;    
        p->v=i;    
        p->weight=t;    
        p->next=G->Ad[j].firstedge;    
        G->Ad[j].firstedge=p;//在表頭插入      
    }    
    printf("AOE網絡構建完成\n-----人家是華麗麗的分割線-----\n打印鄰接表：\n");    
    for(i=1; i<=G->n; i++)    
    {    
        cout << G->Ad[i].element;    
        link *m=G->Ad[i].firstedge;    
        while(m!=NULL)    
        {    
            printf("->%c,%d",G->Ad[m->v].element,m->weight);    
            m=m->next;    
        }    
        printf("->^\n");    
    }//鄰接表打印      
    printf("\n");    
}    
void Criticalpath(Adgraph* G)//G為帶權值的鄰接表      
{    
    queue<int> Q;    
    stack<int> S;    
    int i,j,k,count=0,ve[101],vl[101],ae,al;    
    //時間的最早發生時間和最晚發生時間，活動的最早發生時間和最晚發生時間      
    //m用來計數,判斷是否有回路      
    for(i=1; i<=G->n; i++)ve[i]=0; //首先每個事件的最早發生時間都為0      
    for(i=1; i<=G->n; i++)    
        if(G->Ad[i].indegree==0) Q.push(i);    
    //將入度為0的頂點入隊      
    printf("Topsort:");    
    while(!Q.empty())    
    {    
        j=Q.front();    
        Q.pop();    
        count++;    
        cout << G->Ad[j].element;    
        S.push(j);//把正序的拓撲序下標列入棧      
        link *p=G->Ad[j].firstedge;    
        while(p!=NULL)    
        {    
            k=p->v;    
            G->Ad[k].indegree--;    
            if(ve[j] + p->weight > ve[k])    
                ve[k] = ve[j] + p->weight;    
            if(G->Ad[k].indegree==0) Q.push(k) ;    
            p=p->next;    
        }    
    }//用topsort求最早的發生時間      
    printf("\n");    
    if(count<G->n)    
    {    
        printf("有環路！\n");    
        return;    
    }    
    for(i=1; i<=G->n; i++) //為各事件v(i)的最遲發生時間vl[i]置初值      
        vl[i]=ve[G->n];    
    printf("Opp_Topsort:");    
    while(!S.empty())//按拓撲序列的逆序取頂點      
    {    
        j=S.top();    
        S.pop();//出棧      
        cout << G->Ad[j].element;    
        link *p=G->Ad[j].firstedge;    
        while(p!=NULL)    
        {    
            k=p->v;    
            if((vl[k] - p->weight)<vl[j])    
                vl[j]=vl[k]-p->weight;  //修改vl[j]      
            p=p->next;    
        }    
    }    
    printf("\nActivity<EnventA->EnventB>      AE     AL    Share time  Is Criticalpath?:\n");    
    for(j=1; j<=G->n; j++) //掃描頂點表      
    {    
        link *p=G->Ad[j].firstedge;    
        while(p!=NULL)    
        {    
            k=p->v;    
            ae=ve[j];    
            al=vl[k]-p->weight;    
            printf("<事件%c,事件%c>\t\t\t%d\t%d\t%d    \t",G->Ad[j].element,G->Ad[k].element,ae,al,al-ae);    
            if(al==ae)//關鍵活動      
                printf("Yes");    
                else printf("No");    
            printf("\n");    
            p=p->next;    
        }    
    }    
}    
int main()    
{    
    struct Adgraph G;    
    Create_AOE(&G);    
    Criticalpath(&G);    
    return 0;    
}    

//Topsort And AOE   
#include <iostream>   
#include<stack>   
#include<queue>   
#include<cstdio>   
using namespace std;  
struct link  
{  
    int v;//事件編號   
    int count;//活動的編號   
    int weight;//活動的時間   
    link * next;  
};  
struct node  
{  
    int indegree;//入度   
    char element;//事件   
    struct link* firstedge;  
};//頭結點   
struct Adgraph  
{  
    int n,e;  
    struct node Ad[101];  
};//鄰接表   
void Create_AOE(struct Adgraph* G)  
{  
    int k,i,j,t;  
    cin >> G->n >> G->e;//節點和邊   
    for (k=1; k<=G->n; k++)  
    {  
        cin >> G->Ad[k].element;  
        G->Ad[k].firstedge=NULL;  
        G->Ad[k].indegree=0;  
    }//頭結點的初始化   
    for(k=1; k<=G->e; k++)  
    {  
        printf("輸入兩個頂點(事件編號),邊的權值(活動時間)\n");  
        cin >> j >> i >> t;  
        G->Ad[i].indegree++;  
        link* p=new link;  
        p->v=i;  
        p->weight=t;  
        p->next=G->Ad[j].firstedge;  
        G->Ad[j].firstedge=p;//在表頭插入   
    }  
    printf("AOE網絡構建完成\n-----人家是華麗麗的分割線-----\n打印鄰接表：\n");  
    for(i=1; i<=G->n; i++)  
    {  
        cout << G->Ad[i].element;  
        link *m=G->Ad[i].firstedge;  
        while(m!=NULL)  
        {  
            printf("->%c,%d",G->Ad[m->v].element,m->weight);  
            m=m->next;  
        }  
        printf("->^\n");  
    }//鄰接表打印   
    printf("\n");  
}  
void Criticalpath(Adgraph* G)//G為帶權值的鄰接表   
{  
    queue<int> Q;  
    stack<int> S;  
    int i,j,k,count=0,ve[101],vl[101],ae,al;  
    //時間的最早發生時間和最晚發生時間，活動的最早發生時間和最晚發生時間   
    //m用來計數,判斷是否有回路   
    for(i=1; i<=G->n; i++)ve[i]=0; //首先每個事件的最早發生時間都為0   
    for(i=1; i<=G->n; i++)  
        if(G->Ad[i].indegree==0) Q.push(i);  
    //將入度為0的頂點入隊   
    printf("Topsort:");  
    while(!Q.empty())  
    {  
        j=Q.front();  
        Q.pop();  
        count++;  
        cout << G->Ad[j].element;  
        S.push(j);//把正序的拓撲序下標列入棧   
        link *p=G->Ad[j].firstedge;  
        while(p!=NULL)  
        {  
            k=p->v;  
            G->Ad[k].indegree--;  
            if(ve[j] + p->weight > ve[k])  
                ve[k] = ve[j] + p->weight;  
            if(G->Ad[k].indegree==0) Q.push(k) ;  
            p=p->next;  
        }  
    }//用topsort求最早的發生時間   
    printf("\n");  
    if(count<G->n)  
    {  
        printf("有環路！\n");  
        return;  
    }  
    for(i=1; i<=G->n; i++) //為各事件v(i)的最遲發生時間vl[i]置初值   
        vl[i]=ve[G->n];  
    printf("Opp_Topsort:");  
    while(!S.empty())//按拓撲序列的逆序取頂點   
    {  
        j=S.top();  
        S.pop();//出棧   
        cout << G->Ad[j].element;  
        link *p=G->Ad[j].firstedge;  
        while(p!=NULL)  
        {  
            k=p->v;  
            if((vl[k] - p->weight)<vl[j])  
                vl[j]=vl[k]-p->weight;  //修改vl[j]   
            p=p->next;  
        }  
    }  
    printf("\nActivity<EnventA->EnventB>      AE     AL    Share time  Is Criticalpath?:\n");  
    for(j=1; j<=G->n; j++) //掃描頂點表   
    {  
        link *p=G->Ad[j].firstedge;  
        while(p!=NULL)  
        {  
            k=p->v;  
            ae=ve[j];  
            al=vl[k]-p->weight;  
            printf("<事件%c,事件%c>\t\t\t%d\t%d\t%d    \t",G->Ad[j].element,G->Ad[k].element,ae,al,al-ae);  
            if(al==ae)//關鍵活動   
                printf("Yes");  
                else printf("No");  
            printf("\n");  
            p=p->next;  
        }  
    }  
}  
int main()  
{  
    struct Adgraph G;  
    Create_AOE(&G);  
    Criticalpath(&G);  
    return 0;  
}  //Topsort And AOE      
#include <iostream>      
#include<stack>      
#include<queue>      
#include<cstdio>      
using namespace std;    
struct link    
{    
    int v;//事件編號      
    int count;//活動的編號      
    int weight;//活動的時間      
    link * next;    
};    
struct node    
{    
    int indegree;//入度      
    char element;//事件      
    struct link* firstedge;    
};//頭結點      
struct Adgraph    
{    
    int n,e;    
    struct node Ad[101];    
};//鄰接表      
void Create_AOE(struct Adgraph* G)    
{    
    int k,i,j,t;    
    cin >> G->n >> G->e;//節點和邊      
    for (k=1; k<=G->n; k++)    
    {    
        cin >> G->Ad[k].element;    
        G->Ad[k].firstedge=NULL;    
        G->Ad[k].indegree=0;    
    }//頭結點的初始化      
    for(k=1; k<=G->e; k++)    
    {    
        printf("輸入兩個頂點(事件編號),邊的權值(活動時間)\n");    
        cin >> j >> i >> t;    
        G->Ad[i].indegree++;    
        link* p=new link;    
        p->v=i;    
        p->weight=t;    
        p->next=G->Ad[j].firstedge;    
        G->Ad[j].firstedge=p;//在表頭插入      
    }    
    printf("AOE網絡構建完成\n-----人家是華麗麗的分割線-----\n打印鄰接表：\n");    
    for(i=1; i<=G->n; i++)    
    {    
        cout << G->Ad[i].element;    
        link *m=G->Ad[i].firstedge;    
        while(m!=NULL)    
        {    
            printf("->%c,%d",G->Ad[m->v].element,m->weight);    
            m=m->next;    
        }    
        printf("->^\n");    
    }//鄰接表打印      
    printf("\n");    
}    
void Criticalpath(Adgraph* G)//G為帶權值的鄰接表      
{    
    queue<int> Q;    
    stack<int> S;    
    int i,j,k,count=0,ve[101],vl[101],ae,al;    
    //時間的最早發生時間和最晚發生時間，活動的最早發生時間和最晚發生時間      
    //m用來計數,判斷是否有回路      
    for(i=1; i<=G->n; i++)ve[i]=0; //首先每個事件的最早發生時間都為0      
    for(i=1; i<=G->n; i++)    
        if(G->Ad[i].indegree==0) Q.push(i);    
    //將入度為0的頂點入隊      
    printf("Topsort:");    
    while(!Q.empty())    
    {    
        j=Q.front();    
        Q.pop();    
        count++;    
        cout << G->Ad[j].element;    
        S.push(j);//把正序的拓撲序下標列入棧      
        link *p=G->Ad[j].firstedge;    
        while(p!=NULL)    
        {    
            k=p->v;    
            G->Ad[k].indegree--;    
            if(ve[j] + p->weight > ve[k])    
                ve[k] = ve[j] + p->weight;    
            if(G->Ad[k].indegree==0) Q.push(k) ;    
            p=p->next;    
        }    
    }//用topsort求最早的發生時間      
    printf("\n");    
    if(count<G->n)    
    {    
        printf("有環路！\n");    
        return;    
    }    
    for(i=1; i<=G->n; i++) //為各事件v(i)的最遲發生時間vl[i]置初值      
        vl[i]=ve[G->n];    
    printf("Opp_Topsort:");    
    while(!S.empty())//按拓撲序列的逆序取頂點      
    {    
        j=S.top();    
        S.pop();//出棧      
        cout << G->Ad[j].element;    
        link *p=G->Ad[j].firstedge;    
        while(p!=NULL)    
        {    
            k=p->v;    
            if((vl[k] - p->weight)<vl[j])    
                vl[j]=vl[k]-p->weight;  //修改vl[j]      
            p=p->next;    
        }    
    }    
    printf("\nActivity<EnventA->EnventB>      AE     AL    Share time  Is Criticalpath?:\n");    
    for(j=1; j<=G->n; j++) //掃描頂點表      
    {    
        link *p=G->Ad[j].firstedge;    
        while(p!=NULL)    
        {    
            k=p->v;    
            ae=ve[j];    
            al=vl[k]-p->weight;    
            printf("<事件%c,事件%c>\t\t\t%d\t%d\t%d    \t",G->Ad[j].element,G->Ad[k].element,ae,al,al-ae);    
            if(al==ae)//關鍵活動      
                printf("Yes");    
                else printf("No");    
            printf("\n");    
            p=p->next;    
        }    
    }    
}    
int main()    
{    
    struct Adgraph G;    
    Create_AOE(&G);    
    Criticalpath(&G);    
    return 0;    
}    

//Topsort And AOE   
#include <iostream>   
#include<stack>   
#include<queue>   
#include<cstdio>   
using namespace std;  
struct link  
{  
    int v;//事件編號   
    int count;//活動的編號   
    int weight;//活動的時間   
    link * next;  
};  
struct node  
{  
    int indegree;//入度   
    char element;//事件   
    struct link* firstedge;  
};//頭結點   
struct Adgraph  
{  
    int n,e;  
    struct node Ad[101];  
};//鄰接表   
void Create_AOE(struct Adgraph* G)  
{  
    int k,i,j,t;  
    cin >> G->n >> G->e;//節點和邊   
    for (k=1; k<=G->n; k++)  
    {  
        cin >> G->Ad[k].element;  
        G->Ad[k].firstedge=NULL;  
        G->Ad[k].indegree=0;  
    }//頭結點的初始化   
    for(k=1; k<=G->e; k++)  
    {  
        printf("輸入兩個頂點(事件編號),邊的權值(活動時間)\n");  
        cin >> j >> i >> t;  
        G->Ad[i].indegree++;  
        link* p=new link;  
        p->v=i;  
        p->weight=t;  
        p->next=G->Ad[j].firstedge;  
        G->Ad[j].firstedge=p;//在表頭插入   
    }  
    printf("AOE網絡構建完成\n-----人家是華麗麗的分割線-----\n打印鄰接表：\n");  
    for(i=1; i<=G->n; i++)  
    {  
        cout << G->Ad[i].element;  
        link *m=G->Ad[i].firstedge;  
        while(m!=NULL)  
        {  
            printf("->%c,%d",G->Ad[m->v].element,m->weight);  
            m=m->next;  
        }  
        printf("->^\n");  
    }//鄰接表打印   
    printf("\n");  
}  
void Criticalpath(Adgraph* G)//G為帶權值的鄰接表   
{  
    queue<int> Q;  
    stack<int> S;  
    int i,j,k,count=0,ve[101],vl[101],ae,al;  
    //時間的最早發生時間和最晚發生時間，活動的最早發生時間和最晚發生時間   
    //m用來計數,判斷是否有回路   
    for(i=1; i<=G->n; i++)ve[i]=0; //首先每個事件的最早發生時間都為0   
    for(i=1; i<=G->n; i++)  
        if(G->Ad[i].indegree==0) Q.push(i);  
    //將入度為0的頂點入隊   
    printf("Topsort:");  
    while(!Q.empty())  
    {  
        j=Q.front();  
        Q.pop();  
        count++;  
        cout << G->Ad[j].element;  
        S.push(j);//把正序的拓撲序下標列入棧   
        link *p=G->Ad[j].firstedge;  
        while(p!=NULL)  
        {  
            k=p->v;  
            G->Ad[k].indegree--;  
            if(ve[j] + p->weight > ve[k])  
                ve[k] = ve[j] + p->weight;  
            if(G->Ad[k].indegree==0) Q.push(k) ;  
            p=p->next;  
        }  
    }//用topsort求最早的發生時間   
    printf("\n");  
    if(count<G->n)  
    {  
        printf("有環路！\n");  
        return;  
    }  
    for(i=1; i<=G->n; i++) //為各事件v(i)的最遲發生時間vl[i]置初值   
        vl[i]=ve[G->n];  
    printf("Opp_Topsort:");  
    while(!S.empty())//按拓撲序列的逆序取頂點   
    {  
        j=S.top();  
        S.pop();//出棧   
        cout << G->Ad[j].element;  
        link *p=G->Ad[j].firstedge;  
        while(p!=NULL)  
        {  
            k=p->v;  
            if((vl[k] - p->weight)<vl[j])  
                vl[j]=vl[k]-p->weight;  //修改vl[j]   
            p=p->next;  
        }  
    }  
    printf("\nActivity<EnventA->EnventB>      AE     AL    Share time  Is Criticalpath?:\n");  
    for(j=1; j<=G->n; j++) //掃描頂點表   
    {  
        link *p=G->Ad[j].firstedge;  
        while(p!=NULL)  
        {  
            k=p->v;  
            ae=ve[j];  
            al=vl[k]-p->weight;  
            printf("<事件%c,事件%c>\t\t\t%d\t%d\t%d    \t",G->Ad[j].element,G->Ad[k].element,ae,al,al-ae);  
            if(al==ae)//關鍵活動   
                printf("Yes");  
                else printf("No");  
            printf("\n");  
            p=p->next;  
        }  
    }  
}  
int main()  
{  
    struct Adgraph G;  
    Create_AOE(&G);  
    Criticalpath(&G);  
    return 0;  
}