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

发表于 2018/04/12 更新于 2024/10/18

作者

次浏览 19 分钟阅读

拓扑排序

1. 什么是拓扑排序:

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

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

例如，下面这个图：

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

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

于是，得到拓扑排序后的结果是 { 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)

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

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

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

$V_{1}$ 是源点，其最早开始时间是0。
$V_2$、$V_3$、$V_4$最早时间分别是是6、4、5。
对于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$，故而要按最大计。
$V_6$只有从$V_4$到达，所以$V_6$的最早完成时间是$(5+2=)7$。
同理，$V_7$最早完成时间是15。
对于$V_8$而言，和$V_5$处理方法一致。$V8=max{V_5+7,V_6+4}={7+7,7+4}=14$
$V_9$可算出是18。

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

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

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

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

因为活动$a_{10}$所需时间2。如果V7开始时间比16晚，则V9完成时间就会比18晚，这显然不对。
同理，V8最迟开始时间为14。
对于V5而言，可以从V7、V8两个点开始向前推算，此时要按最小计，即V5(最晚)=min{V7-9,V8-7}=min{16-9,14-7}=7。请注意！！，min{V7-9,V8-7}中，V7、V8取的都是前面算出的最迟开始时间（而不是最早开始时间）。

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

同理，可计算出剩下的点

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

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

求出关键路径

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

对于a1：

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

对于a2 :

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

一般的:

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

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

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

// 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;
}

Base

算法

本文由作者按照 CC BY 4.0 进行授权