图的拓扑排序与关键路径

发表于 更新于 分类于 ，
本文字数： 3.5k

拓扑排序 —— 有向图的顶点构成的一个线性序列

关键路径 —— 设计中从输入到输出经过的延时最长的逻辑路径

数据结构课代码实现 之 图的拓扑排序与关键路径

简要理解

拓扑排序

使用对一个有向无环图 (Directed Acyclic Graph简称DAG) G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边 <u,v> 存在，则 u 在线性序列中出现在 v 之前

同一图的拓扑排序不唯一

关键路径

对图先进行拓扑排序，求出每一个活动 (图中的边) 最早的发生时间 (用对应边的起点保存)，用栈将拓扑排序储存，再进行逆拓扑排序，求出每一个活动的最迟发生时间 (用对应边的终点保存)，如果活动的最早发生时间与最迟发生时间相等，则该活动为关键活动

附上之前的文章：

有向图的拓扑排序

代码实现

邻接表存图

拓扑排序

这里用栈实现，亦可用队列实现

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
39
40
41
42
43
44
45
46
47
int Topologic(ALGraph &G)
{
    int indegree[G.vexnum]; // 用数组保存每个结点的入度
    memset(indegree, 0, sizeof(indegree));

    for(int i = 0;i < G.vexnum;i++)
    {
         for(ArcNode* p = G.vertices[i].firstarc;p->nextarc != NULL;p = p->nextarc)
        {
            int k = p->adjvex;
            indegree[k]++; // 计算入度
        }
    }

    stack<int> s; // 用栈来保存入度为 0 的结点
    for(int i = 0;i < G.vexnum;i++)
        if(!indegree[i])
            s.push(i); // 先找一遍嗷
    
    int cnt = 0; // 记录拓扑排序过程中的结点数

    while(!s.empty())
    {
        int t = s.top(); // 每次出栈一个入度为 0 的一个结点 并将其并入拓扑排序中
        s.pop();
        cout << "当前入度为零的节点的序号为：" << t << endl << "保存的数据为：" << G.vertices[t].data << endl;
        cnt++;
        for(ArcNode* p = G.vertices[t].firstarc;p->nextarc != NULL;p = p->nextarc)
        {
            int k = p->adjvex;  // 用出栈结点更新与他相连的结点入度
            if(!(--indegree[k])) // 入度为 0 入栈
                s.push(k);
        }
    }
    if(cnt < G.vexnum) // 拓扑排序中的点小于图中点数 存在环
        return ERROR;
    else
        return OK;
}

int main()
{
    ALGraph g;
    CreateGraph(g);
    Topologic(g);
    return 0;
}

关键路径

最早开始时间 ：ve(k) = max{ve(j) + dut(<j,k>)}

结点 j 为 所有以结点 k 为尾的弧的头结点

活动的最早开始时间由之前所有活动中 用时最长的活动决定

最迟开始时间：vl(j) = min{vl(k) - dut(<j,k>)}

结点 j 为 所有以结点 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
stack<int> T;

int ve[MAX_VERTEX_NUM]; // 保存每个活动的最早开始时间

int vl[MAX_VERTEX_NUM]; // 保存每个活动的最迟开始时间                                                       

int Topologic(ALGraph &G)
{
    int indegree[G.vexnum];
    memset(indegree, 0, sizeof(indegree));
    memset(ve, 0,sizeof(ve));

    for(int i = 0;i < G.vexnum;i++)
    {
         for(ArcNode* p = G.vertices[i].firstarc;p->nextarc != NULL;p = p->nextarc)
        {
            int k = p->adjvex;
            indegree[k]++;
        } 
    }

    stack<int> s;

    for(int i = 0;i < G.vexnum;i++)
        if(!indegree[i])
            s.push(i);
    
    int cnt = 0;

    while(!s.empty())
    {
        int t = s.top();
        s.pop();
        T.push(t);  // 用栈 T 保存逆拓扑排序
        cout << "当前入度为零的节点的序号为：" << t << endl << "保存的数据为：" << G.vertices[t].data << endl;
        cnt++;
        for(ArcNode* p = G.vertices[t].firstarc;p->nextarc != NULL;p = p->nextarc)
        {
            int k = p->adjvex;
            if(ve[k] < ve[t] + p->cost)
                ve[k] = ve[t] + p->cost; // 活动的最早开始时间由之前所有活动中 用时最长的活动决定
            if(!(--indegree[k]))
                s.push(k);
        }
    }
    if(cnt < G.vexnum)
        return ERROR;
    else
        return OK;
}

int CriticalPach(ALGraph &G)
{
    if(!Topologic(G)) return ERROR; // 如果图中有环 则无拓扑序列 无关键路径
    for(int i = 0;i < G.vexnum;i++)
        vl[i] = ve[G.vexnum - 1]; // 初始化所有活动的最迟开始时间
    while(!T.empty())
    {
        int t = T.top();
        T.pop();
        for(ArcNode* p = G.vertices[t].firstarc;p->nextarc != NULL;p = p->nextarc)
        {
            int k = p->adjvex;
            int dut = p->cost;
            if(vl[k] - dut < vl[t]) vl[t] = vl[k] - dut; // 活动的最迟开始时间由之后所有活动中 用时最长的活动决定
        }
    }
    for(int i = 0;i < G.vexnum;i++)
    {
        for(ArcNode* p = G.vertices[i].firstarc;p->nextarc != NULL;p = p->nextarc)
        {
            int k = p->adjvex;
            int dut = p->cost;
            int ee = ve[i], el = vl[k] - dut;
            char tag = (ee == el) ? '*' : ' '; // 是否为关键路径
            cout << G.vertices[i].data << " " << G.vertices[k].data << " " << dut << " " << ee << " " << el << " " << tag << endl; 
        }
    }
}
int main()
{
    ALGraph g1;
    CreateGraphDouble(g1);
    CriticalPach(g1);
    return 0;
}