17. 图-拓扑排序与关键路径

概念

AOV 网（Activity On Vertex network）：用顶点表示活动、有向边表示活动之间的先后约束的有向图。如课程学习中"先修课"关系。若 AOV 网中存在环，则说明活动之间存在循环依赖，无法安排顺序。

拓扑排序（Topological Sort）：把 AOV 网中的所有顶点排成一个线性序列，使得每条边的起点 u 都排在终点 v 之前。该序列称为拓扑序列。有向无环图（DAG）一定存在拓扑序列；若排序得到的顶点数少于 n，则图中必存在环。因此拓扑排序常被用来检测有向图中是否有环。

Kahn 算法（队列/栈版）：

计算所有顶点的入度；
把所有入度为 0 的顶点入队（这些顶点没有前置依赖，可先安排）；
出队一个顶点 u 加入拓扑序列，删除它所有的出边，即把其每个后继的入度减 1；若某后继入度变为 0 则入队；
重复直到队列为空。若输出的顶点数 < n，说明图中存在环。

AOE 网（Activity On Edge network）：用有向边表示活动、顶点表示事件（活动之间的里程碑）的带权有向图，通常只有一个源点（入度为 0）和一个汇点（出度为 0），边权表示活动耗时。AOE 网用于计算整个工程的最短工期以及哪些活动不能拖延。

关键路径（Critical Path）：AOE 网中从源点到汇点路径长度最长的路径。整个工程的工期就是关键路径的长度——关键路径上的活动一旦延误，整个工程就会延期。

两个关键时间量：

ve(v) 事件最早发生时间：从源点沿拓扑序正向递推，ve(v) = max(ve(u) + w(u,v))（取所有入边中的最大值），源点 ve = 0。所谓"最早"，是指到该事件为止的所有前置活动都完成的最早时刻。
vl(v) 事件最迟发生时间：从汇点沿拓扑序逆向递推，vl(v) = min(vl(w) - w(v,w))（取所有出边中的最小值），汇点 vl = ve(汇点)。所谓"最迟"，是指为保证工期不延误、该事件最晚必须发生的时刻。

关键活动：活动 <u,v> 的最早开始时间 e = ve(u)，最迟开始时间 l = vl(v) - w(u,v)。若 e == l，说明该活动一点缓冲余地都没有，称为关键活动。关键活动串起来即构成关键路径。

核心操作 / 算法

Kahn 拓扑排序（O(n+e)）：

统计每个顶点的入度；
入度为 0 的顶点全部入队；
出队 u -> 加入序列；对其每条出边 <u,v> 的入度减 1，减到 0 就入队；
队列空为止。序列长度 < n 说明有环。

关键路径（O(n+e)）：

先做拓扑排序得到拓扑序列；
正向遍历拓扑序列，按 ve(v) = max(ve(u) + w(u,v)) 求所有事件最早发生时间 ve；汇点的 ve 即工程总工期；
反向遍历拓扑序列，按 vl(u) = min(vl(v) - w(u,v)) 求所有事件最迟发生时间 vl（初始化 vl(汇点) = ve(汇点)）；
对每条边 <u,v>，计算 e = ve(u)、l = vl(v) - w(u,v)，满足 e == l 的即为关键活动，沿关键活动构成的路径即关键路径。

复杂度分析

操作	时间复杂度	空间复杂度	说明
Kahn 拓扑排序	O(n+e)	O(n)	每个顶点入队出队一次，每条边扫描一次
关键路径（ve/vl 递推）	O(n+e)	O(n)	在拓扑序基础上正/反向各扫一遍所有边
判环（拓扑排序结果 < n）	O(n+e)	O(n)	复用拓扑排序

为什么：每个顶点恰好入队一次、出队一次，共 O(n)；每条边在"删出边减入度"时恰好被处理一次，共 O(e)，故 O(n+e)。关键路径在拓扑排序（O(n+e)）基础上再正向、反向各扫描一遍所有边，仍是 O(n+e)；空间上只需入度数组、ve、vl 各 O(n)。

语言实现

下面 4 种语言的实现演示相同的操作：对同一个 AOV/AOE 网（7 个顶点、9 条带权边，DAG），先运行 Kahn 拓扑排序输出拓扑序列，再运行关键路径算法输出工程总工期、关键活动与关键路径。每个文件都给出完整的拓扑排序实现；关键路径的完整代码在 C 与 Python 中给出，C++ 与 Java 中则给出 Kahn 拓扑排序并说明关键路径与 C/Python 完全对应。

C

#include <stdio.h>

#define MAX 20
#define NO_EDGE -1

int n;
int w[MAX][MAX];        // 邻接矩阵存边权，NO_EDGE 表示无边

int topoOrder[MAX];     // 保存拓扑序列

// Kahn 拓扑排序：返回输出顶点数，若小于 n 说明有环
int topoSort() {
    int indeg[MAX];
    for (int i = 0; i < n; i++) {
        indeg[i] = 0;
        for (int j = 0; j < n; j++)
            if (w[j][i] != NO_EDGE) indeg[i]++;   // 统计入度
    }
    // 用数组模拟队列
    int queue[MAX], front = 0, rear = 0;
    for (int i = 0; i < n; i++)
        if (indeg[i] == 0) queue[rear++] = i;

    int cnt = 0;
    while (front < rear) {
        int u = queue[front++];
        topoOrder[cnt++] = u;
        for (int v = 0; v < n; v++)
            if (w[u][v] != NO_EDGE) {
                indeg[v]--;
                if (indeg[v] == 0) queue[rear++] = v;
            }
    }
    return cnt;
}

// 关键路径：返回总工期，并打印关键活动
int criticalPath() {
    int cnt = topoSort();
    if (cnt < n) {
        printf("图中存在环，无法计算关键路径\n");
        return -1;
    }
    int ve[MAX] = {0};
    // 正向：求事件最早发生时间 ve
    for (int i = 0; i < n; i++) {
        int u = topoOrder[i];
        for (int v = 0; v < n; v++)
            if (w[u][v] != NO_EDGE && ve[u] + w[u][v] > ve[v])
                ve[v] = ve[u] + w[u][v];
    }
    // 找汇点（出度为 0 的顶点），其 ve 即总工期
    int sink = topoOrder[n - 1];
    int vl[MAX];
    for (int i = 0; i < n; i++) vl[i] = ve[sink];
    // 反向：求事件最迟发生时间 vl
    for (int i = n - 1; i >= 0; i--) {
        int u = topoOrder[i];
        for (int v = 0; v < n; v++)
            if (w[u][v] != NO_EDGE && vl[v] - w[u][v] < vl[u])
                vl[u] = vl[v] - w[u][v];
    }
    printf("关键活动: ");
    for (int u = 0; u < n; u++)
        for (int v = 0; v < n; v++)
            if (w[u][v] != NO_EDGE) {
                int e = ve[u], l = vl[v] - w[u][v];
                if (e == l) printf("(%d->%d) ", u, v);
            }
    printf("\n");
    return ve[sink];
}

int main() {
    n = 7;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            w[i][j] = NO_EDGE;

    // AOE 网带权边 (u, v, weight)
    int raw[][3] = {{0,1,3},{0,2,2},{1,3,2},{2,3,4},
                    {2,4,3},{3,5,2},{4,5,3},{3,6,4},{5,6,1}};
    for (int i = 0; i < 9; i++)
        w[raw[i][0]][raw[i][1]] = raw[i][2];

    int cnt = topoSort();
    printf("拓扑序列: ");
    for (int i = 0; i < cnt; i++) printf("%d ", topoOrder[i]);
    printf("\n");
    printf("顶点数 %d，排序 %d 个 → %s\n", n, cnt, cnt < n ? "存在环" : "无环");

    int total = criticalPath();
    if (total != -1) printf("工程总工期(关键路径长度): %d\n", total);
    return 0;
}

C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// Kahn 拓扑排序：用邻接表，O(n+e)。返回拓扑序列；若有环，序列长度 < n。
vector<int> topoSort(int n, const vector<vector<pair<int,int>>>& adj) {
    vector<int> indeg(n, 0);
    for (int u = 0; u < n; u++)
        for (auto& e : adj[u])
            indeg[e.first]++;
    queue<int> q;
    for (int i = 0; i < n; i++)
        if (indeg[i] == 0) q.push(i);
    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (auto& e : adj[u]) {
            if (--indeg[e.first] == 0) q.push(e.first);
        }
    }
    return order;
}

// 关键路径：基于拓扑序正/反向递推 ve 与 vl，打印关键活动并返回工期。
// 与 C/Python 的完整实现完全对应，这里一并给出以便对照。
int criticalPath(int n, const vector<vector<pair<int,int>>>& adj) {
    vector<int> order = topoSort(n, adj);
    if ((int)order.size() < n) { cout << "存在环，无法计算关键路径\n"; return -1; }

    vector<int> ve(n, 0);
    for (int u : order)
        for (auto& e : adj[u])
            ve[e.first] = max(ve[e.first], ve[u] + e.second);

    int sink = order.back();
    vector<int> vl(n, ve[sink]);
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i];
        for (auto& e : adj[u])
            vl[u] = min(vl[u], vl[e.first] - e.second);
    }

    cout << "关键活动: ";
    for (int u = 0; u < n; u++)
        for (auto& e : adj[u])
            if (ve[u] == vl[e.first] - e.second)
                cout << "(" << u << "->" << e.first << ") ";
    cout << endl;
    return ve[sink];
}

int main() {
    int n = 7;
    vector<vector<pair<int,int>>> adj(n);
    // AOE 网带权边 (u, v, weight)
    int raw[][3] = {{0,1,3},{0,2,2},{1,3,2},{2,3,4},
                    {2,4,3},{3,5,2},{4,5,3},{3,6,4},{5,6,1}};
    for (auto& e : raw) adj[e[0]].push_back({e[1], e[2]});

    vector<int> order = topoSort(n, adj);
    cout << "拓扑序列: ";
    for (int v : order) cout << v << " ";
    cout << endl;
    cout << "顶点数 " << n << "，排序 " << order.size() << " 个 → "
         << (order.size() < n ? "存在环" : "无环") << endl;

    int total = criticalPath(n, adj);
    if (total != -1) cout << "工程总工期(关键路径长度): " << total << endl;
    return 0;
}

Java

import java.util.*;

public class TopoSort {
    // Kahn 拓扑排序：邻接表，O(n+e)。返回拓扑序列；若有环，长度 < n。
    static List<Integer> topoSort(int n, List<List<int[]>> adj) {
        int[] indeg = new int[n];
        for (int u = 0; u < n; u++)
            for (int[] e : adj.get(u))
                indeg[e[0]]++;
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++)
            if (indeg[i] == 0) q.offer(i);
        List<Integer> order = new ArrayList<>();
        while (!q.isEmpty()) {
            int u = q.poll();
            order.add(u);
            for (int[] e : adj.get(u))
                if (--indeg[e[0]] == 0) q.offer(e[0]);
        }
        return order;
    }

    // 关键路径：与 C/Python 完整实现对应，打印关键活动并返回工期。
    static int criticalPath(int n, List<List<int[]>> adj) {
        List<Integer> order = topoSort(n, adj);
        if (order.size() < n) { System.out.println("存在环，无法计算关键路径"); return -1; }

        int[] ve = new int[n];
        for (int u : order)
            for (int[] e : adj.get(u))
                ve[e[0]] = Math.max(ve[e[0]], ve[u] + e[1]);

        int sink = order.get(order.size() - 1);
        int[] vl = new int[n];
        Arrays.fill(vl, ve[sink]);
        for (int i = n - 1; i >= 0; i--) {
            int u = order.get(i);
            for (int[] e : adj.get(u))
                vl[u] = Math.min(vl[u], vl[e[0]] - e[1]);
        }

        System.out.print("关键活动: ");
        for (int u = 0; u < n; u++)
            for (int[] e : adj.get(u))
                if (ve[u] == vl[e[0]] - e[1])
                    System.out.print("(" + u + "->" + e[0] + ") ");
        System.out.println();
        return ve[sink];
    }

    public static void main(String[] args) {
        int n = 7;
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        // AOE 网带权边 (u, v, weight)
        int[][] raw = {{0,1,3},{0,2,2},{1,3,2},{2,3,4},
                       {2,4,3},{3,5,2},{4,5,3},{3,6,4},{5,6,1}};
        for (int[] e : raw) adj.get(e[0]).add(new int[]{e[1], e[2]});

        List<Integer> order = topoSort(n, adj);
        System.out.print("拓扑序列: ");
        for (int v : order) System.out.print(v + " ");
        System.out.println();
        System.out.println("顶点数 " + n + "，排序 " + order.size() + " 个 → "
                + (order.size() < n ? "存在环" : "无环"));

        int total = criticalPath(n, adj);
        if (total != -1) System.out.println("工程总工期(关键路径长度): " + total);
    }
}

Python

from collections import deque


def topo_sort(n, adj):
    """Kahn 拓扑排序：邻接表，O(n+e)。返回拓扑序列；若有环长度 < n。"""
    indeg = [0] * n
    for u in range(n):
        for v, _ in adj[u]:
            indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v, _ in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order


def critical_path(n, adj):
    """关键路径：在拓扑序上正/反向递推 ve/vl，打印关键活动并返回工期。"""
    order = topo_sort(n, adj)
    if len(order) < n:
        print("存在环，无法计算关键路径")
        return -1

    # 正向求事件最早发生时间 ve
    ve = [0] * n
    for u in order:
        for v, w in adj[u]:
            if ve[u] + w > ve[v]:
                ve[v] = ve[u] + w

    # 反向求事件最迟发生时间 vl
    sink = order[-1]
    vl = [ve[sink]] * n
    for u in reversed(order):
        for v, w in adj[u]:
            if vl[v] - w < vl[u]:
                vl[u] = vl[v] - w

    # 关键活动：e = ve[u]，l = vl[v] - w，两者相等即为关键活动
    critical = []
    for u in range(n):
        for v, w in adj[u]:
            if ve[u] == vl[v] - w:
                critical.append(f"({u}->{v})")
    print("关键活动:", " ".join(critical))
    return ve[sink]


if __name__ == "__main__":
    n = 7
    # AOE 网带权边 (u, v, weight)
    raw = [(0,1,3),(0,2,2),(1,3,2),(2,3,4),
           (2,4,3),(3,5,2),(4,5,3),(3,6,4),(5,6,1)]
    adj = [[] for _ in range(n)]
    for u, v, w in raw:
        adj[u].append((v, w))

    order = topo_sort(n, adj)
    print("拓扑序列:", order)
    print(f"顶点数 {n}，排序 {len(order)} 个 → {'存在环' if len(order) < n else '无环'}")

    total = critical_path(n, adj)
    if total != -1:
        print("工程总工期(关键路径长度):", total)

17.图-拓扑排序与关键路径.md 14 KB Trvalý odkaz Historie Surový