【图论】拓扑排序

更新于 分类于 ， 阅读次数： 本文字数： 838 阅读时长 ≈ 1 分钟

拓扑排序是基于DAG的排序方法

定义

有向无环图（DAG），顶点线性排序使得对于每一个有向边，起始节点都在尾节点的前面

分析

记录每个点的入度

对于每个点，遍历它的所有出边并更新到达节点的入度，如果该到达节点的入度为00 则加入队列

复杂度O(E+V)O(E+V)

应用

  • 找环
  • 找最长路
  • 找优先级最大（等效于最长路）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void toposort()
{
    while (!topo.empty())
    {
        int cur = topo.front();
        topo.pop();
        for (int i = 1; i <= n; i++)
        {
            if (graph[cur][i])
            {
                in[i]--;
                d[i] = max(d[i], d[cur] + 1);
                if (!in[i])
                    topo.push(i);
            }
        }
    }
}
  • 字典序拓扑排序：上述队列改成优先队列，复杂度O(E+Vlog⁡V)O(E+V\log V)

关键路径

离散数学里学的东西，学之前完全没听说过…

  • 定义：顶点表活动，有向边表优先级，这样的DAG称AOV(activity on vertex network)；边有权值表时间，称AOE网(activity on edge)；AOE网上的最长路径称关键路径，只有这条路径上的关键活动进行时间变化能够影响到整体时间。
  • uu 节点的最早开始时间ve[u]ve[u] ，最晚开始时间vl[u]vl[u] 。
  • 以最早开始时间为例，对于边(u,v,w)(u,v,w) ，更新操作：ve[v]=max(ve[v],ve[u]+w)ve[v]=max(ve[v],ve[u]+w) 。
  • 正反图分别进行拓扑排序，过程中进行ve,vlve,vl 的更新，ve[u]=vl[u]ve[u]=vl[u] 的点即为关键路径上的点。