来自我的博客：拓扑排序 Topological Sort – Snow’s Blog (ivansnow02.github.io)

拓扑排序 Topological Sort

拓扑序列 Topological Order

拓扑序列是一个有向无环图（Directed Acyclic Graph，简称DAG）的一切极点的线性序列。

设G=(V，E)是一个具有n个极点的有向图，V中极点序列v1、v2、…、vnv_1、v_2、…、v_n称为一个拓扑序列，当且仅当该极点序列满意下列条件：若<vi，vj><v_i，v_j>是图中的有向边或者从极点viv_i到极点vjv_j有一条途径，则在序列中极点viv_i有必要排在极点vjv_j之前。

进程

  1. 从有向图中挑选一个没有前驱（即入度为0）的极点而且输出它。
  2. 从图中删去该极点，而且删去从该极点宣布的悉数有向边。
  3. 重复上述两步，直到剩余的图中不再存在没有前驱的极点为止。

成果

  • 图中悉数极点都被输出，即得到包括悉数极点的拓扑序列，称为成功的拓扑排序。
  • 图中极点未被悉数输出，即只能得到部分极点的拓扑序列，称为失利的拓扑排序，阐明有向图中存在回路。

代码

基于BFS的拓扑排序

struct Edge {
    int from, to, cost;
    Edge(int u, int v, int w): from(u), to(v), cost(w) {}
};
vector<Edge> edges; // 存储一切边
vector<int> G[MAXN]; // G[i] 存储极点i宣布的一切边
int inDegree[MAXN]; // 存储每个极点的入度
vector<int> result;
void TopologicalSort(int V) {
    queue<int> q;
    // 统计每个极点的入度
    for (int i = 0; i < edges.size(); ++i) {
        int to = edges[i].to;
        inDegree[to]++;
    }
    // 将入度为0的极点入队
    for (int i = 0; i < V; ++i) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);
        // 遍历极点u宣布的一切边
        for (int i = 0; i < G[u].size(); ++i) {
            Edge& e = edges[G[u][i]];
            int v = e.to;
            // 删去边(u, v)，更新极点v的入度
            if (--inDegree[v] == 0) {
                q.push(v);
            }
        }
    }
}

基于DFS的拓扑排序

void TopSort(vector<Edge>& edges, vector<vector<int>>& G) {
    stack<int> st;            // 界说一个栈
    int ind[MAXV];            // 记录每个极点的入度
    memset(ind, 0, sizeof(ind));
    for (const Edge& edge : edges) {
        int to = edge.to;
        ind[to]++;            // 极点to的入度增1
    }
    for (int i = 0; i < G.size(); i++) {
        if (ind[i] == 0) {
            st.push(i);      // 将一切入度为0的极点进栈
        }
    }
    while (!st.empty()) {
        int i = st.top();
        st.pop();             // 出栈一个极点i
        printf("%d ", i);     // 输出拓扑序列中的一个极点i
        for (int j : G[i]) {  // 遍历极点i的一切邻接点
            int w = edges[j].to;
            ind[w]--;         // 极点w的入度减1
            if (ind[w] == 0) {
                st.push(w);   // 入度为0的邻接点w进栈
            }
        }
    }
}

剖析

运用邻接表进行拓扑排序的时刻复杂度为O(V+E)O(V + E)。这是一种相对高效的算法，特别适用于稀少图（边的数量较少）的拓扑排序问题。

AOE网

界说

若用一个带权有向图（DAG）描述工程的估计进度，以极点表示事情，有向边表示活动，边e的权c(e)表示完成活动e所需的时刻（比如天数），或者说活动e持续时刻→\toAOE网。

一般AOE网中只有一个入度为0的极点，称为源点，和一个出度为0的极点，称为汇点。

在AOE网中，从源点到汇点的一切途径中，具有最大途径长度的途径称为要害途径。完成整个工程的最短时刻就是网中要害途径的长度。

要害途径上的活动称为要害活动，或者说要害途径是由要害活动构成的。

事情的最早开端和最迟开端时刻

  • 事情v的最早开端时刻：规定源点事情的最早开端时刻为0。界说图中任一事情v的最早开端时刻ee(v)等于x、y、z到v一切途径长度的最大值

ee(v)={0v为源点max{ee(x)+a,ee(y)+b,ee(z)+c}不然ee(v) = \begin{cases} 0 &v为源点 \\ max\{ee(x)+a,\ ee(y) + b,\ ee(z)+c\} &不然 \end{cases}

  • 事情v的最迟开端时刻：界说在不影响整个工程进度的前提下，事情v有必要发生的时刻称为v的最迟开端时刻le(v)应等于ee(y)与v到汇点的最长途径长度之差

le(v)={ee(v)v为汇点min{le(x)−a,le(y)−b,le(z)−c}不然le(v) = \begin{cases} ee(v) &v为汇点 \\ min\{le(x)-a,\ le(y) – b,\ le(z)-c\} &不然 \end{cases}

活动的最早开端时刻和最迟开端时刻

  • 活动a的最早开端时刻e(a)指该活动起点x事情的最早开端时刻，即： e(a)=ee(x)e(a)=ee(x)
  • 活动a的最迟开端时刻l(a)指结尾y事情的最迟开端时刻与该活动所需时刻之差，即：l(a)=le(y)−cl(a)=le(y)-c

要害活动

对于每个活动a，求出d(a)=l(a)−e(a)d(a)=l(a)-e(a)，若d(a)为0，则称活动a为要害活动。 对要害活动来说，不存在富余时刻。

运用拓扑排序求要害途径

struct Edge {
    int from, to, cost;
    Edge(int u, int v, int w): from(u), to(v), cost(w) {}
};
vector<Edge> edges; // 存储一切边
vector<int> G[MAXN]; // G[i] 存储极点i宣布的一切边
int inDegree[MAXN]; // 存储每个极点的入度
int earliest[MAXN]; // 存储每个极点的最早开端时刻
int latest[MAXN]; // 存储每个极点的最晚开端时刻
void addEdge(int u, int v, int w) {
    edges.push_back(Edge(u, v, w));
    int m = edges.size();
    G[u].push_back(m - 1);
    inDegree[v]++;
}
void calcEarliestTime(int n) {
    memset(earliest, 0, sizeof(earliest));
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < G[u].size(); i++) {
            Edge& e = edges[G[u][i]];
            int v = e.to;
            int w = e.cost;
            earliest[v] = max(earliest[v], earliest[u] + w);
            inDegree[v]--;
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
    }
}
void calcLatestTime(int n) {
    memset(latest, INF, sizeof(latest));
    latest[n - 1] = earliest[n - 1];
    queue<int> q;
    q.push(n - 1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < G[u].size(); i++) {
            Edge& e = edges[G[u][i]];
            int v = e.to;
            int w = e.cost;
            latest[u] = min(latest[u], latest[v] - w);
            if (--inDegree[v] == 0) {
                q.push(v);
            }
        }
    }
}
void findCriticalPath(int n) {
    for (int i = 0; i < edges.size(); i++) {
        Edge& e = edges[i];
        int u = e.from;
        int v = e.to;
        int w = e.cost;
        int earliestU = earliest[u];
        int latestV = latest[v] - w;
        if (earliestU == latestV) {
            cout << u << " -> " << v << " : " << w << "\n";
        }
    }
}

剖析

因为运用了拓扑排序，时刻复杂度为O(V+E)O(V+E)