算法

数据结构 | 有向无环图的应用之拓扑排序与关键路径

拓扑排序与关键路径

Posted by Aiden on April 12, 2018

拓扑排序

1. 什么是拓扑排序:

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

每个顶点出现且只出现一次。 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。 有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。

例如，下面这个图：

image.png

它是一个 DAG 图，那么如何写出它的拓扑排序呢？这里说一种比较常用的方法：

  1. 从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出。
  2. 从图中删除该顶点和所有以它为起点的有向边。
  3. 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

image.png

于是，得到拓扑排序后的结果是 { 1, 2, 4, 3, 5 }。

通常，一个有向无环图可以有一个或多个拓扑排序序列。

2.拓扑排序的实现

#include<iostream>
#include <list>
#include <queue>
using namespace std;

/************************类声明************************/
class Graph
{
    int V;             // 顶点个数
    list<int> *adj;    // 邻接表
    queue<int> q;      // 维护一个入度为0的顶点的集合
    int* indegree;     // 记录每个顶点的入度
public:
    Graph(int V);                   // 构造函数
    ~Graph();                       // 析构函数
    void addEdge(int v, int w);     // 添加边
    bool topological_sort();        // 拓扑排序
};

/************************类定义************************/
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];

    indegree = new int[V];  // 入度全部初始化为0
    for(int i=0; i<V; ++i)
        indegree[i] = 0;
}

Graph::~Graph()
{
    delete [] adj;
    delete [] indegree;
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w);
    ++indegree[w];
}

bool Graph::topological_sort()
{
    for(int i=0; i<V; ++i)
        if(indegree[i] == 0)
            q.push(i);         // 将所有入度为0的顶点入队

    int count = 0;             // 计数，记录当前已经输出的顶点数
    while(!q.empty())
    {
        int v = q.front();      // 从队列中取出一个顶点
        q.pop();

        cout << v << " ";      // 输出该顶点
        ++count;
        // 将所有v指向的顶点的入度减1，并将入度减为0的顶点入栈
        list<int>::iterator beg = adj[v].begin();
        for( ; beg!=adj[v].end(); ++beg)
            if(!(--indegree[*beg]))
                q.push(*beg);   // 若入度为0，则入栈
    }

    if(count < V)
        return false;           // 没有输出全部顶点，有向图中有回路
    else
        return true;            // 拓扑排序成功
}

关键路径算法(AOE)

image.png

如上图，是一个AOE网，点表示状态，边表示活动及其所需要的时间。为了求出关键路径，我们使用一下算法

1.求出到达各个状态的最早时间（按最大计）

这个过程是要从源点开始向汇点顺推：

  1. $V_{1}$ 是源点，其最早开始时间是0。
  2. $V_2$、$V_3$、$V_4$最早时间分别是是6、4、5。
  3. 对于V5而言，V2到V5所花费时间是6+1=7，而V3到V5所花费时间是4+1=5。我们要按最大计，也就是V5最早时间是$\max{7,5}=7$，按最大计是因为只有活动$a_4$和$a_5$同时完成了，才能到达$V_5$状态。$V_3$到$V_5$需要5分钟，但是此时$a_4$活动尚未完成（7分钟），所以都不能算到达$V_5$，故而要按最大计。
  4. $V_6$只有从$V_4$到达，所以$V_6$的最早完成时间是$(5+2=)7$。
  5. 同理，$V_7$最早完成时间是15。
  6. 对于$V_8$而言，和$V_5$处理方法一致。$V8=max{V_5+7,V_6+4}={7+7,7+4}=14$
  7. $V_9$可算出是18。

这样，我们可以得到各个状态的最早时间的表

image.png

2.求出到达各个状态的最晚时间（按最小计）

这个过程是要从汇点开始向源点逆推：

  1. V9完成时间为18，最V7最迟开始时间是（18-2=）16

image.png

  1. 因为活动$a_{10}$所需时间2。如果V7开始时间比16晚，则V9完成时间就会比18晚，这显然不对。

  2. 同理，V8最迟开始时间为14。

  3. 对于V5而言，可以从V7、V8两个点开始向前推算，此时要按最小计，即V5(最晚)=min{V7-9,V8-7}=min{16-9,14-7}=7。 请注意！！，min{V7-9,V8-7}中，V7、V8取的都是前面算出的最迟开始时间（而不是最早开始时间）。

image.png

按最小计，是因为如果按最大计去计算V5的最晚开始时间，那么加上a7和a8的活动时间后，V7、V8至少有一个会比之前逆推算得出的最晚时间还要晚，这就发生了错误。

同理，可计算出剩下的点

这样，我们可以得到各个状态的最晚时间的表：

image.png

事实上，源点和汇点的最晚时间和最早时间必定是相同的。

求出关键路径

1.求出关键活动，则关键活动所在路径即为关键路径 :

对于a1：

image.png

这表明，a1最早只能从0时刻开始，最晚也只能从（6-6=）0时刻开始，因此，a1是关键活动。

对于a2 :

image.png

a2最早要从0时刻开始，但是它最晚开始时间却是（6-4=）2。也就是说，从0开始做，4时刻即完成；从2开始做，6时刻恰好完成。从而在[0,2]区间内任意时间开始做a2都能保证按时完成。（请区别顶点的最早最晚和活动的最早最晚时间)。图示中的最早最晚是顶点状态的时间，活动的最早最晚开始时间却是基于此来计算的）。

一般的:

image.png

活动用时X时间，它最早要从E1时刻开始（一开始就开始），最晚要从L2-X时刻开始（即恰好完成）。所以，如果它是关键活动，则必然有E1=L2-X，否则它就不是关键活动。

值得注意的是，顶点的最早开始时间等于最晚开始时间 是 该顶点处于关键路径 的 不充分不必要条件

image.png

上表中蓝色底纹表示的点即为处于关键路径的点。尽管它们的最早时间与最晚时间都相同，但是这与它们是否为关键路径的点无关。因为这还取决于起始点的最早时间以及活动时间。

image.png

// grp-top.cpp : 定义控制台应用程序的入口点。
//
// grp-top.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <stdlib.h>


#define MAXVEX 100
#define IFY 65535


typedef char VertexType;
typedef int  EdgeType;
typedef int  IdxType;
typedef int QueueType;
typedef int StackType;


//-------
int *g_etv = NULL;
int *g_ltv = NULL;
int *g_StkAfterTop;
int g_topOfStk;


///---------------------------------------
//边节点
typedef struct EdgeNode{
    IdxType idx;
    int weigh;
    struct EdgeNode* next;
}eNode;

//顶点节点
typedef struct VexNode{
    int numIn;        //入度数量
    IdxType idx;
    eNode *fitstedge;
}vNode;

//图的集合：包含了一个顶点数组
typedef struct {
    vNode adjList[MAXVEX];
    int numVextexs,numEdges;
}GraphAdjList;

///-----------------------------------
/*VertexType g_init_vexs[MAXVEX] = {'A','B','C','D','E','F','G','H','I','J','K','L'};

char *g_input[] = {
    "A->B->C->D",
    "B->E",
    "C->F->I->J",
    "D->E->I->J",
    "E",
    "F->K",
    "G->F->H->K",
    "H->I",
    "I->J->L",
    "J->E->K",
    "K->L",
    "L"
};*/

///-----------------------------------
VertexType g_init_vexs[MAXVEX] = {'A','B','C','D','E','F','G','H','I','J'};

char *g_input[] = {
    "A->B->C",
    "B->D->E",
    "C->D->F",
    "D->E",
    "E->G->H",
    "F->H",
    "G->J",
    "H->I",
    "I->J",
    "J",
    NULL
};

char *g_input_weigh[] = {
    "3,4",//A
    "5,6",//B
    "8,7",//C
    "3",//D
    "9,4",//E
    "6",//F
    "2",//G
    "5",//H
    "3",//I
    " ",//J
    NULL
};
//===============================================================
//队列

//队列节点
typedef struct Node {
    QueueType data;
    struct Node *next;
}QNode,*qQNode;

//队列指示
typedef struct {
    int length;
    qQNode frnt,rear;    
}spQueue;

void init_Queue(spQueue *Q)
{
    (*Q).frnt = NULL;
    (*Q).rear = NULL;
    (*Q).length = 0;
}
bool isEmptyQueue(spQueue Q)
{
    if (Q.length == 0)
    {
        return true;
    }
    return false;
}
//进队
void unshiftQueue(spQueue *Q,QueueType elem)
{
    //队列空
    if (isEmptyQueue(*Q))
    {
        qQNode n = (qQNode)malloc(sizeof(QNode));
        n->data = elem;
        n->next = NULL;

        (*Q).frnt = n;
        (*Q).rear = n;
        (*Q).length = 1;
    }
    else
    {
        qQNode n = (qQNode)malloc(sizeof(QNode));
        n->data = elem;
        n->next = NULL;

        (*Q).rear->next = n;

        (*Q).rear = n;
        (*Q).length++;
    }
}

//出队
QueueType shiftQueue(spQueue *Q)
{
    if (isEmptyQueue(*Q))
    {
        printf("Warning:Queue is empty!!!\n");
        return NULL;
    }
    if ((*Q).length == 1)
    {
        QueueType sh = (*Q).frnt->data;
        (*Q).frnt = NULL;
        (*Q).rear = NULL;
        (*Q).length = 0;
        return sh;
    }
    QueueType sh = (*Q).frnt->data;
    (*Q).frnt = (*Q).frnt->next;
    (*Q).length--;

    return sh;
}

//打印队列
void prt_que(spQueue que)
{
    if (isEmptyQueue(que))
    {
        return ;
    }
    qQNode pos = que.frnt;
    while(que.rear->next != pos && pos != NULL)
    {
        printf(" %d ",pos->data);
        pos = pos->next;
    }
    printf("\n");
}
//===============================================================

///-------
//由节点找节点的序号
IdxType strFindIdx(char ch)
{
    int i=0;
    VertexType *p = g_init_vexs;
    while(p != NULL)
    {
        if(*p == ch)
        {
            return i;
        }
        p++;
        i++;
    }
    return i;
}

//由序号找节点
VertexType idxFindStr(IdxType i)
{
    return g_init_vexs[i];
}

void prt_strings(char *p)
{
    char *pos = p;
    while (NULL != *pos)
    {
        printf("%c",*pos);
        pos++;
    }
    printf("\n");
}

void prt_strArrays(char *p[],int num)
{
    char **pos = p;
    int i=0;
    while( *pos != NULL && i < num)
    {
        prt_strings(*pos);
        pos++;
        i++;
    }
}

//自己规定：顶点只能是大写。
bool isVexter(char p)
{
    if (p>='A' && p<='Z')
    {
        return true;
    }
    return false;
}

bool isNumeric(char p)
{
    if (p >= '0' && p <= '9')
    {
        return true;
    }
    return false;
}

void init_GrapAdjList(GraphAdjList *g,char **str,char **wstr)
{
    char **pos = str;

    int cnt=0;
    int vcnt = 0;
    char **wpos = wstr;//weight value

    //入度清零
    int i;
    for (i=0;i<MAXVEX;i++)
    {
        (*g).adjList[i].numIn = 0;
    }

    while (*pos != NULL) //g_input的每行的首指针
    {
        int i=0;
        while(**pos != NULL) //g_input的每行字母
        {
            if(isVexter(**pos)) //判断是否为顶点（我规定‘A’-‘Z’之间为顶点标志）
            {
                if (i == 0) //建立顶点的节点
                {
                    (*g).adjList[cnt].idx = strFindIdx(**pos);
                    (*g).adjList[cnt].fitstedge = NULL;

                    i=1;
                }
                else if(i == 1) //建立第一个边的节点
                {
                    eNode* n = (eNode*)malloc(sizeof(eNode));
                    n->idx = strFindIdx(**pos);
                    n->next = NULL;

                    //weight
                    while (!isNumeric(**wpos))
                    {
                        (*wpos)++;
                    }
                    n->weigh = **wpos-'0';
                    (*wpos)++;

                    (*g).adjList[cnt].fitstedge = n;
                    i=2;

                    //添加入度
                    int iidx = strFindIdx(**pos);
                    (*g).adjList[iidx].numIn++;
                }
                else //边节点连接到前一个边节点上
                {    
                    eNode* n = (eNode*)malloc(sizeof(eNode));
                    n->idx = strFindIdx(**pos);
                    n->next = NULL;

                    //weight
                    while (!isNumeric(**wpos))
                    {
                        (*wpos)++;
                    }
                    n->weigh = **wpos-'0';
                    (*wpos)++;

                    //first splist
                    eNode *r = (*g).adjList[cnt].fitstedge;
                    while (r->next != NULL)
                    {
                        r = r->next;
                    }
                    r->next = n;

                    //添加入度
                    int iidx = strFindIdx(**pos);
                    (*g).adjList[iidx].numIn++;
                }
            }
            (*pos)++;
        }

        wpos++;
        cnt++;
        pos++;

    }
    (*g).numVextexs = cnt;
}

int TopplogicalSort(GraphAdjList *g)
{
    int count=0;
    eNode *e=NULL;

    StackType *stack=NULL;
    StackType top=0;
    stack = (StackType *)malloc((*g).numVextexs*sizeof(StackType));

    int i;

    //初始化拓扑序列栈
    g_topOfStk = 0;
    //开辟拓扑序列栈对应的最早开始时间数组
    g_etv = (int *)malloc((*g).numVextexs*sizeof(int));
    //初始化数组
    for (i=0;i<(*g).numVextexs;i++)
    {
        g_etv[i]=0;
    }
    //开辟拓扑序列的顶点数组栈
    g_StkAfterTop = (int *)malloc(sizeof(int)*(*g).numVextexs);




    for (i=0;i<(*g).numVextexs;i++)
    {
        if (!(*g).adjList[i].numIn)
        {
            stack[++top] = i;
    //        printf("init no In is %c\n",g_init_vexs[i]);
        }
    }


    while(top)
    {
        int geter = stack[top];
        top--;

        //把拓扑序列保存到拓扑序列栈，为后面做准备
        g_StkAfterTop[g_topOfStk++] = geter;

        printf("%c -> ",g_init_vexs[(*g).adjList[geter].idx]);
        count++;

        //获取当前点出度的点，对出度的点的入度减一（当前点要出图）。
        //获取当前顶点的出度点表
        e = (*g).adjList[geter].fitstedge;
        while(e)
        {
            int eIdx = e->idx;
            //选取的出度点的入度减一
            int crntIN = --(*g).adjList[eIdx].numIn;
            if (crntIN == 0)
            {
                //如果为0，则说明该顶点没有入度了，是下一轮的输出点。
                stack[++top] = eIdx;
        //        printf("running the vex is %c\n",g_init_vexs[e->idx]);
            }

            //求出关键路径
            if ((g_etv[geter] + e->weigh) > g_etv[eIdx])
            {
                g_etv[eIdx] = g_etv[geter] + e->weigh;
            }

            e = e->next;
        }
    }
    if (count < (*g).numVextexs)//如果图本身就是一个大环，或者图中含有环，这样有环的顶点不会进栈而被打印出来。
    {
        return false;
    }
    else
    {
        printf("finish\n");
        return true;
    }

}
void CriticalPath(GraphAdjList g)
{
    int i;
    int geter;
    eNode *e = NULL;
    g_topOfStk--;
    //1.初始化最迟开始时间数组(汇点的最早开始时间（初值）)
    g_ltv = (int *)malloc(sizeof(int)*g.numVextexs);
    for (i=0;i<g.numVextexs;i++)
    {
        g_ltv[i] = g_etv[g.numVextexs-1];
    }

    //2.求每个点的最迟开始时间，从汇点到源点推。
    while (g_topOfStk)
    {
        //获取当前出栈（反序）的序号
        geter = g_StkAfterTop[g_topOfStk--];
        //对每个出度点
        if (g.adjList[geter].fitstedge != NULL)
        {
            e = g.adjList[geter].fitstedge;
            while(e != NULL)
            {
                int eIdx = e->idx;
                if (g_ltv[eIdx] - e->weigh < g_ltv[geter])
                {
                    g_ltv[geter] = g_ltv[eIdx] - e->weigh;
                }
                e = e->next;
            }
        }
    }

    int ete,lte;//活动最早开始和最迟开始时间



    printf("start:->");
    //3.求关键活动，即ltv和etv相等的
    for (i=0;i<g.numVextexs;i++)
    {
        if (g.adjList[i].fitstedge)
        {
            e = g.adjList[i].fitstedge;
            while(e)
            {
                int eIdx = e->idx;
                //活动（i->eIdx）最早开始时间：事件（顶点） i最早开始时间
                ete = g_etv[i];
                //活动（i->eIdx）最迟开始时间：事件（顶点） eIdx 最迟开始时间 减去 活动持续时间
                lte = g_ltv[eIdx] - e->weigh;
                if (ete == lte)
                {
                    printf("(%c - %c)->",g_init_vexs[i],g_init_vexs[eIdx]);
                }
                e= e->next;
            }
        }
    }
    printf(" end\n");
}


int _tmain(int argc, _TCHAR* argv[])
{
    GraphAdjList grp;
    printf("print Matix: of Vextexs:\n");
    prt_strArrays(g_input,10);
    printf("print Matix: of Weigh:\n");
    prt_strArrays(g_input_weigh,10);

    init_GrapAdjList(&grp,g_input,g_input_weigh);
    printf("Top sort:\n");
    if (!TopplogicalSort(&grp))
    {
        printf("grp wrong!\n");
    }

    CriticalPath(grp);

    getchar();
    return 0;
}
CATALOG
    ABOUT ME

    天行健,君子以自强不息!

    FEATURED TAGS
    算法 Java 设计模式 Spring web Linux 系统工具 cpp 网络 消息队列 spark kubernetes 机器学习 olap datalake