本文讲解了拓扑的排序的一般实现方法和它在AOV和AOE网络中的应用。

AOV 网

日常生活中，一项工程都可以看作是由若干个子工程组成的集合，这些子工程之间必定存在一定的先后顺序，即某些子工程必须在其他的一些子工程完成后才能开始。

我们用有向图来表现子工程之间的先后关系，子工程之间的先后关系为有向边，这种有向图称为顶点活动网络，即 AOV 网 (Activity On Vertex Network)。一个 AOV 网必定是一个 DAG，即不带有回路。在 AOV 网中，顶点表示活动，弧(边)表示活动间的优先关系。

拓扑排序也可以解释为将 AOV 网中所有活动排成一个序列，使得每个活动的前驱活动都排在该活动的前面（一个 AOV 网中的拓扑排序也不是唯一的。

拓扑排序

流程

• 在建图的过程中统计所有边的入度
• 找到没有入度的节点入队
• 记录并弹出队头，减少其他节点入度
  • 如果有节点的入度减少为零，那么将它入队
• 重复执行，直到队列空

如果弹出的节点数量等于图中所有节点的数量，那么该图存在一个拓扑序列。

代码实现

const int N = 1e5 + 10;
int h[N] , e[N] , ne[N] , idx;
int IN[N];
vector<int> route;

void add(int a , int b)
{
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}

void TpSort(int n)
{
    queue<int> q;

	// 寻找所有可能的入口 这些入口可以存在于图的多个联通分量中
    for(int i = 1 ; i <= n ; i++)
    {
        if(IN[i] == 0) q.push(i);
    }
    
    while(q.size())
    {
        int f = q.front(); q.pop(); route.push_back(f);
        for(int i = h[f] ; i != -1 ; i = ne[i])
        {
            int j = e[i]; IN[j]--;
            // 只有在入度减少时，新的入口才可能出现
            if(IN[j] == 0)
                q.push(j);
        }
    }

	// 判别序列是否包含所有节点
    if((int)route.size() < n) {cout << -1; return;}
    for(auto i : route) cout << i << " ";
}

AOE网

与 AOV 网对应的是 AOE 网（Activity On Edge Network) 即边表示活动的网。

AOE 网是一个带权的有向无环图，其中顶点表示事件，弧表示活动持续的时间。通常，AOE 网可以用来估算工程的完成时间。AOE 网是无环的，且存在唯一入度为零的起始顶点（源点），以及唯一出度为零的完成顶点（汇点）。

相关概念

• 活动：AOE 网中，弧表示活动。弧的权值表示活动持续的时间，活动在事件被触发后开始。
• 事件：AOE 网中，顶点表示事件，事件能被触发。
• 弧(活动) 的最早开始时间：初始点到该弧起点的最长路径长度，记为 earliest(e)。
  • 最长路径代表该节点的入度为零的最早时刻
• 弧(活动) 的最迟开始时间：在不推迟整个工期的前提下，工程达到弧起点所表示的状态最晚能容忍的时间，记为 latest(e)。

关键路径

AOE 网中的有些活动是可以并行进行的，所以完成整个工程的最短时间是从源点到汇点的最长活动路径长度（路径长度是指路径上各活动的持续时间之和，即弧的权值之和）。因为一项工程需要完成所有工程内的活动，所以最长的活动路径即是关键路径，它决定工程完成的总时间。

d(i) = l(i) − e(i)，即活动最迟开始时间与最早开始时间的差额，这代表着活动可以拖延的时间。如果一个活动的时间余量为 0，就意味着该活动不能拖延时间，称为 关键活动，必须立即完成，否则就将拖延整个工期。 而时间余量为 0 的所有边连起来，就是关键路径了。 要求时间余量 d, 就要先求活动的最早开始时间 e 和最迟开始时间 l，要求 e 和 l 就要先求事件最早发生时间 ve 和最迟发生时间 vl。

#include<bits/stdc++.h>
#define N 100010
using namespace std;
struct edge {
    int to, w;
}; 
vector <edge> g[N]; // 邻接表
int indgr[N], topo[N], n, m; 
int ve[N], e[N], vl[N];
bool topoSort() {
    queue <int> q;
    int k = 0; 
    for(int i = 1; i <= n; i++)
        if(indgr[i] == 0) q.push(i); 
    while(!q.empty()) {
        int u = q.front(); q.pop();
        topo[++k] = u; // 记录拓扑序列
        for(int i = 0; i < g[u].size(); i++) {
            int v = g[u][i].to;
            if(--indgr[v]==0) q.push(v); 
        } 
    }
    if(k < n) return 0; 
    return 1; 
}

void build_ve() { // 计算事件每个节点的最晚到达时间(节点的每条出边的最早发生时间)
    for(int i = 1; i <= n; i++) ve[i]=0; 
    	
    for(int j = 1; j <= n; j++) {
        int u = topo[j]; 
        // 按拓扑遍历所有出边 更新边对象节点的最晚到达时间(取)
        // 这个过程可以在拓扑排序过程中同步发生
        for(int i = 0; i < g[u].size(); i++) {
            int v = g[u][i].to, w = g[u][i].w;
            ve[v] = max(ve[v], ve[u] + w);
        }
    } 
}
void build_vl() { // 计算事件最迟发生时间

	// 活动的最早发生事件 = 边的最早开始时间 = 顶点最晚到达时间
    for(int i = 1; i <= n; i++) vl[i] = ve[n]; 

    for(int j = n-1; j >= 1; j--) {
        int u = topo[j]; 
	    // 按逆拓扑序 对于节点的所有后置节点
		// 当前节点的最晚到达时间 (只有这个节点到达了，这个节点的出边才能开始)
		// 是后置节点的最晚到达时间 - 活动的时间 中最早的时间
        for(int i = 0; i < g[u].size(); ++i){
            int v = g[u][i].to, w = g[u][i].w;
            vl[u] = min(vl[u], vl[v] - w);
        }
    }
}


int main() {
    cin >> n >> m; // n 个事件，m 个活动
    for(int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back((edge){v,w}); 
        indgr[v]++; // 记录入度 
    } 
    if(topoSort()) { // 拓扑排序成功
        for(int i = 1; i <= n; i++) {
            cout << topo[i] << " "; 
        }
        cout << endl;
        build_ve();
        build_vl();
        critical();
    }
    else {
        cout << -1 << endl;
    }
    return 0;
}

测试样例

样例1:
6 8
1 2 3
1 3 2
2 4 2
2 5 3
3 4 4
3 6 3
4 6 2
5 6 1

输出1:
1 2 3 5 4 6 
<1,3>
<3,4>
<4,6>

样例2:
8 12
1 2 6
1 3 7
2 4 3
2 5 5
3 5 4
4 6 2
4 8 5
5 4 3
5 6 4
5 7 3
6 8 2
7 8 4

输出2:
1 2 3 5 4 7 6 8 
<1,2>
<2,5>
<5,4>
<4,8>
19

Copyright

Copyright Ownership:Pray0

License under:Attribution 4.0 International (CC-BY-4.0)

Previous pageEulerian Path

Next pageMinimum Spanning Tree