拓扑排序 Topological Sort

拓扑排序 Topological Sort

拓扑序列 Topological Order

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

设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列$v_1、v_2、…、v_n$称为一个拓扑序列，当且仅当该顶点序列满足下列条件：若$<v_i，v_j>$是图中的有向边或者从顶点$v_i$到顶点$v_j$有一条路径，则在序列中顶点$v_i$必须排在顶点$v_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)$。这是一种相对高效的算法，特别适用于稀疏图（边的数量较少）的拓扑排序问题。

AOE网

定义

若用一个带权有向图（DAG）描述工程的预计进度，以顶点表示事件，有向边表示活动，边e的权c(e)表示完成活动e所需的时间（比如天数），或者说活动e持续时间$\to$AOE网。

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

在AOE网中，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径。完成整个工程的最短时间就是网中关键路径的长度。

关键路径上的活动称为关键活动，或者说关键路径是由关键活动构成的。

事件的最早开始和最迟开始时间

• 事件v的最早开始时间：规定源点事件的最早开始时间为0。定义图中任一事件v的最早开始时间ee(v)等于x、y、z到v所有路径长度的最大值

$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) = \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)$
• 活动a的最迟开始时间l(a)指终点y事件的最迟开始时间与该活动所需时间之差，即：$l(a)=le(y)-c$

关键活动

对于每个活动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)$