Fork me on GitHub

图的拓扑排序与关键路径

发表于 | 分类于
字数统计: 1,921 | 阅读时长 ≈ 8

拓扑排序

AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧边数活动间的优先关系，这样的有向图表示活动的网，称为AOV网。

AOV网中不能出现回路。

拓扑序列：设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v1,v2,…,vn，满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必须在顶点vj之前·，这样的序列称为拓扑序列。

拓扑排序：对一个有向图构造拓扑序列的过程。

算法的基本思路：从一个网中选择一个入度为0的顶点输出，然后删除此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点(表明是AOV网)或不存在入度为0的顶点为止。

所用结构：增加入度域的邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct EdgeNode
{
    int adjvex;
    int weight;
    struct EdgeNode *next;
}EdgeNode;

typedef struct VertexNode
{
    int in;
    int data;
    EdgeNode *firstedge;
}VertexNode,AdjList[MAXVEX];

typedef struct
{
    AdjList adjlist;
    int numVertexes,numEdges;
}graphAdjList,*GraphAdjList;

算法(需要辅助数据结构–栈):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Status TopologicalSort(GraphAdjList GL)
{
    EdgeNode *e;
    int top = -1;//栈指针下标
    int count = 0;//统计输出顶点个数
    int *stack;//创建栈，用于存储入度为0的顶点
    
    stack = (int*)malloc(GL->numVertexes * sizeof(int));
    for (int i = 0;i < GL->numVertexes;i++)
        if (GL->adjList[i].in == 0)
            stack[++top] = i;//将最开始入度为0的顶点入栈
    while (top != -1)
    {
        int gettop = stack[top--];//将一个入度为0的顶点出栈进行操作
        printf("%d -> "GL->adjList[gettop].data);
        count++;
        for (e = GL->adjList[gettop].firstedge;e;e = e->next)
            //遍历刚出栈顶点的所有相邻接顶点，将新的入度为0的顶点入栈
        {
            int k = adjVex;
            if (!(--GL->adjList[k].in))
                stack[++top] = k;
        }
    }
    if (count < GL->numVertexes)
        return ERROR;
    else return OK;
}

时间复杂度为O(n+e)。

该算法执行结果仅仅为所有拓扑排序方案的一种。

关键路径

相关概念：

AOE网：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网称为AOE网。

没有入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点。一般情况下AOE网只有一个源点一个汇点。

AOV网是顶点表示活动的网，它只描述活动之间的制约关系，而AOE网是用边表示活动的网，边上的权值表示活动的持续时间。AOE网要建立在活动没有矛盾的基础之上，再来分析完成整个工程至少需要多少时间，或为缩短完成工程所需时间，应加快哪些活动等问题。

我们把路径上各个活动的持续时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。

只有缩短关键路径上的关键活动时间才能减少整个工期的长度。

算法原理：

我们只需找到所有活动的最早开始时间和最晚开始时间，并且比较它们，如果相等就意味着此活动是关键活动，活动间的路径为关键路径，如果不等，则就不是。

几个参数：

  • 事件最早发生的时间etv：即顶点vk的最早发生时间。
  • 事件最晚发生的时间ltv：顶点vk的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的时间，超出此时间会延误整个工期。
  • 活动最早开工的时间ete：即弧ak的最早发生时间。
  • 活动最晚开工的时间lte：即弧ak的最晚发生时间，也就是不推迟工期的最晚开工时间。

通过1和2可以求得3和4，然后再根据ete[k]是否等于lte[k]相等来判断ak是否是关键活动。

算法：

1
2
3
4
//全局变量
int *etv,*ltv;//事件最早发生时间与最晚发生时间数组
int *stack2;//用于存储拓扑序列的栈
int top2;//stack2的指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//改进的拓扑排序算法
Status TopologicalSort(GraphAdjList GL)
{
    EdgeNode *e;
    int top = -1;//栈指针下标
    int count = 0;//统计输出顶点个数
    int *stack;//创建栈，用于存储入度为0的顶点
    
    stack = (int*)malloc(GL->numVertexes * sizeof(int));
    for (int i = 0;i < GL->numVertexes;i++)
        if (GL->adjList[i].in == 0)
            stack[++top] = i;//将最开始入度为0的顶点入栈
    top2 = -1;
    etv = (int*)malloc(GL->numVertexes*sizeof(int));
    for(int i = 0;i < GL->numVertexes;i++)
        etv[i] = 0;//初始化为0
    stack2 = (int*)malloc(GL->numVertexes*sizeof(int));
    
    while (top != -1)
    {
        int gettop = stack[top--];//将一个入度为0的顶点出栈进行操作
        count++;
        stack2[++top2] = gettop;//将弹出的顶点序号压入拓扑序列的栈
        for (e = GL->adjList[gettop].firstedge;e;e = e->next)
            //遍历刚出栈顶点的所有相邻接顶点，将新的入度为0的顶点入栈
        {
            int k = adjVex;
            if (!(--GL->adjList[k].in))
                stack[++top] = k;
            
            if ((etv[gettop]+e->weight) > etv[k])//求各顶点事件最早发生的时间值
                etv[k] = etv[gettop] + e->weight;
        }
    }
    if (count < GL->numVertexes)
        return ERROR;
    else return OK;
}

求etv[k]时需注意，必须将之前所有事件发生了之后才能发生顶点vk的事件，故当 (etv[gettop]+e->weight) > etv[k] 时改变etv[k]的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void CriticalPath(GraphAdjList GL)
{
    EdgeNode *e;
    int k;
    int ete,lte;//声明活动最早开工时间和最晚开工时间变量
    
    TopologicalSort(GL);//求拓扑序列，计算数组etv与stack2的值
    ltv = (int*)malloc(GL->numVertexes*sizrof(int));//事件最晚发生时间
    for (int i = 0;i < GL->numVertexes;i++)
        ltv[i] = etv[GL->numVertexes-1];//初始化ltv
    while (top2 != -1)
    {
        int gettop = stack2[top2--];
        for (e = GL->adjList[gettop].firstedge;e;e=e->next)
        {//求各顶点事件的最迟发生时间ltv值
            k = e->adjvex;
            if ((ltv[k] - e->weight) < ltv[gettop])
                ltv[gettop] = ltv[k] - e->weight;//
        }
    }
    
    for (int j = 0;j < GL->numVertexes;j++)
    {
        for (e = GL->adjList[j].firstedge;e;e = e->next)
        {
            k = e->adjVex;
            ete = etv[j];//活动的最早开工时间,即该活动前一个事件最早发生的时间
            ltv = ltv[k] - e->weight;//活动的最迟开工时间,即该活动后一个事件最迟发生的时间向前推移该活动所需的时间的结果
            if (ele == lte)//如果两者相等，说明活动仅仅只能在这一刻开工，无任何缓冲余地，即该活动在关键路径上
                printf("<v%d,v%d> length: %d , ",GL->adjList[j].data,GL->adjList[k].data,e->weight);
        }
    }
}

求ltv时，各事件最迟发生的时间为 其后面的事件最迟发生的时间向前提前对应的活动所需时间后最早的时间，即，一旦超过了该时间，一定有至少一个后面的事件发生的时间超过其最迟发生时间，以此类推，整个工期必被加长。

时间复杂度为O(n+e)。

如果是多条关键路径，则只提高一条关键路径上的关键活动的速度并不能缩短整个工程的工期，必须同时提高几条关键路径上的活动的速度才行。

-------------本文结束感谢您的阅读-------------
undefined