拓扑排序

拓扑排序是一种针对有向无环图(DAG, Directed Acyclic Graph)的重要算法，常用于处理具有依赖关系的任务调度问题。

基本概念

【定义】拓扑排序是将有向无环图中的所有顶点排成一个线性序列，使得图中任意一对顶点u和v，如果存在一条从u到v的路径，那么在序列中u一定出现在v之前。

关键特性

1. 拓扑排序只适用于有向无环图（DAG）
2. 如果图中存在环，则无法进行拓扑排序
3. 对同一个图，可能存在多个合法的拓扑排序序列
4. 拓扑排序可以用来检测图中是否存在环

应用场景

1. 任务调度：确定具有依赖关系的任务的执行顺序
2. 编译系统：确定程序模块的编译顺序
3. 课程安排：根据课程的先修关系安排学习顺序
4. 数据处理管道：确定数据流的处理顺序

BFS实现（Kahn算法）

Kahn算法是基于广度优先搜索的拓扑排序算法，其核心思想是不断移除没有入边的节点。

算法步骤

1. 计算图中每个顶点的入度
2. 将所有入度为0的顶点加入队列
3. 取出队列中的一个顶点，将其加入结果序列
4. 将该顶点的所有出边删除，更新相邻顶点的入度
5. 如果有新的入度为0的顶点，将其加入队列
6. 重复步骤3-5，直到队列为空
7. 如果结果序列的长度等于图中顶点数，则得到一个拓扑排序；否则，图中存在环，无法进行拓扑排序

代码实现

const int MAXN = 100005;

vector<int> graph[MAXN];       // 邻接表表示的有向图
int inDegree[MAXN];            // 记录每个顶点的入度
vector<int> topologicalOrder;  // 存储拓扑排序的结果

// 返回true表示成功找到拓扑排序，false表示图中存在环
bool kahnsAlgorithm(int n) {
    // 初始化入度
    memset(inDegree, 0, sizeof(inDegree));

    // 计算每个顶点的入度
    for (int u = 1; u <= n; u++) {
        for (int v : graph[u]) {
            inDegree[v]++;
        }
    }

    queue<int> q;

    // 将所有入度为0的顶点加入队列
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    // 处理队列中的顶点
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topologicalOrder.push_back(u);  // 将顶点加入拓扑序列

        // 移除所有从u出发的边
        for (int v : graph[u]) {
            inDegree[v]--;

            // 如果v的入度变为0，将其加入队列
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // 检查是否所有顶点都已加入拓扑序列
    return topologicalOrder.size() == n;
}

// 打印拓扑排序结果
void printTopologicalOrder() {
    for (int vertex : topologicalOrder) {
        cout << vertex << " ";
    }
    cout << endl;
}

时间复杂度分析

• 时间复杂度：O(V+E)，其中V是顶点数，E是边数
• 空间复杂度：O(V)，需要额外的队列和入度数组

DFS实现

也可以使用深度优先搜索实现拓扑排序，其核心思想是在递归调用结束后将顶点加入序列。

算法步骤

1. 对图中每个未访问的顶点，开始一次DFS
2. 在DFS过程中，递归地访问所有邻接顶点
3. 当一个顶点的所有邻接顶点都已被访问，将该顶点加入结果序列的头部
4. 最终结果序列即为拓扑排序

代码实现

const int MAXN = 100005;

vector<int> graph[MAXN];       // 邻接表表示的有向图
bool visited[MAXN];            // 记录顶点是否被访问过
bool inStack[MAXN];            // 记录顶点是否在当前DFS路径上（用于检测环）
vector<int> topologicalOrder;  // 存储拓扑排序的结果
bool hasCycle;                 // 标记图中是否存在环

// DFS遍历
void dfs(int u) {
    visited[u] = true;
    inStack[u] = true;  // 标记顶点u在当前DFS路径上

    // 访问所有邻接顶点
    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs(v);
        } else if (inStack[v]) {
            // 如果v已经在当前DFS路径上，说明存在环
            hasCycle = true;
            return;
        }
    }

    inStack[u] = false;  // 顶点u已经处理完毕，移出当前路径
    topologicalOrder.push_back(u);  // 将顶点加入拓扑序列
}

// 拓扑排序主函数
bool topologicalSort(int n) {
    // 初始化
    memset(visited, false, sizeof(visited));
    memset(inStack, false, sizeof(inStack));
    topologicalOrder.clear();
    hasCycle = false;

    // 对每个未访问的顶点开始DFS
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }

    // 如果存在环，无法进行拓扑排序
    if (hasCycle) {
        return false;
    }

    // 由于DFS后加入的顺序与拓扑排序相反，需要反转
    reverse(topologicalOrder.begin(), topologicalOrder.end());
    return true;
}

时间复杂度分析

• 时间复杂度：O(V+E)
• 空间复杂度：O(V)，需要额外的访问标记数组和调用栈空间

实战应用

判断图中是否存在环

拓扑排序可以用来判断一个有向图是否包含环：

• 如果能够得到一个完整的拓扑排序（排序结果包含所有顶点），则图中不存在环
• 如果无法得到完整的拓扑排序，则图中存在环

求解依赖问题

许多实际问题可以建模为依赖图，然后通过拓扑排序求解：

// 例：课程安排问题
// n个课程，课程编号为1到n
// prerequisites[i] = [a, b]表示课程a依赖于课程b（必须先学习课程b）
bool canFinish(int n, vector<pair<int, int>>& prerequisites) {
    // 构建邻接表
    vector<int> graph[n+1];
    int inDegree[n+1] = {0};

    for (const auto& pre : prerequisites) {
        int course = pre.first;
        int prereq = pre.second;
        graph[prereq].push_back(course);
        inDegree[course]++;
    }

    queue<int> q;
    int count = 0;

    // 将所有入度为0的课程加入队列
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    // 拓扑排序
    while (!q.empty()) {
        int course = q.front();
        q.pop();
        count++;

        for (int next : graph[course]) {
            inDegree[next]--;
            if (inDegree[next] == 0) {
                q.push(next);
            }
        }
    }

    // 如果所有课程都能被选修，则返回true
    return count == n;
}

找到所有可能的拓扑排序

在某些情况下，我们可能需要找到所有可能的拓扑排序序列。可以使用回溯法实现：

void allTopologicalSorts(int n, vector<int>& result, bool visited[],
                         vector<int> graph[], vector<int>& inDegree) {
    bool allVisited = true;

    // 检查是否所有顶点都已访问
    for (int i = 1; i <= n; i++) {
        if (!visited[i] && inDegree[i] == 0) {
            // 选择当前入度为0的顶点
            visited[i] = true;
            result.push_back(i);

            // 减少邻居的入度
            for (int neighbor : graph[i]) {
                inDegree[neighbor]--;
            }

            // 递归查找下一个顶点
            allTopologicalSorts(n, result, visited, graph, inDegree);

            // 回溯
            visited[i] = false;
            result.pop_back();
            for (int neighbor : graph[i]) {
                inDegree[neighbor]++;
            }

            allVisited = false;
        }
    }

    // 如果所有顶点都已访问，输出当前排序
    if (allVisited && result.size() == n) {
        printArrangement(result);
    }
}

拓扑排序的变种

字典序最小的拓扑排序

有时我们需要找到字典序最小的拓扑排序。只需在BFS实现中使用优先队列代替普通队列：

bool lexicographicalTopSort(int n) {
    // 使用优先队列（小顶堆）
    priority_queue<int, vector<int>, greater<int>> pq;

    // 将所有入度为0的顶点加入队列
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) {
            pq.push(i);
        }
    }

    // 处理队列中的顶点
    while (!pq.empty()) {
        int u = pq.top();
        pq.pop();
        topologicalOrder.push_back(u);

        for (int v : graph[u]) {
            inDegree[v]--;
            if (inDegree[v] == 0) {
                pq.push(v);
            }
        }
    }

    return topologicalOrder.size() == n;
}

关键路径问题

在带权有向无环图中，关键路径是从源点到汇点的最长路径，常用于项目管理中的关键路径分析(CPM)。可以通过拓扑排序求解：

void criticalPath(int n) {
    vector<int> early(n+1, 0);  // 最早开始时间
    vector<int> late(n+1, INT_MAX);  // 最晚开始时间

    // 计算最早开始时间（正向拓扑排序）
    // ... 拓扑排序代码 ...

    // 根据拓扑排序结果计算每个活动的最早开始时间
    for (int u : topologicalOrder) {
        for (auto& [v, weight] : graph[u]) {
            early[v] = max(early[v], early[u] + weight);
        }
    }

    // 初始化汇点的最晚开始时间
    int sink = n;  // 假设n是汇点
    late[sink] = early[sink];

    // 计算最晚开始时间（反向拓扑排序）
    for (int i = topologicalOrder.size() - 1; i >= 0; i--) {
        int u = topologicalOrder[i];
        for (auto& [v, weight] : graph[u]) {
            late[u] = min(late[u], late[v] - weight);
        }
    }

    // 找出关键活动（最早开始时间等于最晚开始时间的活动）
    for (int u = 1; u <= n; u++) {
        if (early[u] == late[u]) {
            cout << u << " is on the critical path\n";
        }
    }
}

练习题目推荐

1. POJ 1094 Sorting It All Out（拓扑排序基础）
2. POJ 1270 Following Orders（输出所有可能的拓扑排序）
3. CodeForces 510C Fox And Names（字典序最小的拓扑排序）
4. POJ 1128 Frame Stacking（拓扑排序应用）
5. UVA 10305 Ordering Tasks（基础拓扑排序题）

总结与技巧

1. 检测环：通过拓扑排序可以轻松检测图中是否存在环
2. 多源点拓扑排序：对所有入度为0的点同时开始BFS
3. 输出所有方案：使用回溯法生成所有可能的拓扑排序
4. 优化技巧：
   • 使用邻接表而非邻接矩阵表示图
   • 预先计算入度，避免重复计算
   • 使用优先队列可以获得字典序最小的拓扑排序