拓扑排序是对有向图顶点进行线性排列的一种方法。对于图中的每条边 u -> v，拓扑序都必须保证 u 出现在 v 之前。

只有有向无环图（DAG）一定存在拓扑排序。如果图中存在环，环上的顶点无法满足彼此的先后约束。

一、使用 DFS 求拓扑排序

DFS 版本需要记录每个顶点的访问状态：

  • 0：还没有访问。
  • 1：正在当前递归路径中访问。
  • 2：已经访问完成。

当访问边 u -> v 时，如果 v 的状态为 1，说明从 v 可以沿当前递归路径回到 u，因此发现了有向环。

#include <algorithm>
#include <utility>
#include <vector>

bool Dfs(int vertex,
         const std::vector<std::vector<int>>& graph,
         std::vector<int>& state,
         std::vector<int>& order) {
  state[vertex] = 1;

  for (int next : graph[vertex]) {
    if (state[next] == 1) {
      return false; // 找到有向环
    }
    if (state[next] == 0 &&
        !Dfs(next, graph, state, order)) {
      return false;
    }
  }

  state[vertex] = 2;
  order.push_back(vertex); // 后序加入
  return true;
}

std::vector<int> TopologicalSortByDfs(
    int vertex_count, const std::vector<std::pair<int, int>>& edges) {
  std::vector<std::vector<int>> graph(vertex_count);
  for (const auto& [from, to] : edges) {
    graph[from].push_back(to);
  }

  std::vector<int> state(vertex_count, 0);
  std::vector<int> order;
  order.reserve(vertex_count);

  for (int vertex = 0; vertex < vertex_count; ++vertex) {
    if (state[vertex] == 0 &&
        !Dfs(vertex, graph, state, order)) {
      return {}; // 空结果表示存在环
    }
  }

  std::reverse(order.begin(), order.end());
  return order;
}

顶点在所有后继顶点完成后才加入 order，因此得到的是后序排列；将后序排列反转后，就是拓扑序。

DFS 的时间复杂度为 O(V + E)，空间复杂度为 O(V + E)。递归深度很大的图可能导致栈空间不足，此时可以使用 BFS 版本，或自行实现显式栈。

二、使用 BFS 求拓扑排序

Kahn 算法的核心是入度：

  1. 统计每个顶点的入度。
  2. 将所有入度为 0 的顶点加入队列。
  3. 取出队首顶点，将它加入结果，并把所有出边指向顶点的入度减 1。
  4. 新变为入度 0 的顶点加入队列。
#include <optional>
#include <queue>
#include <utility>
#include <vector>

std::optional<std::vector<int>> TopologicalSortByBfs(
    int vertex_count, const std::vector<std::pair<int, int>>& edges) {
  std::vector<std::vector<int>> graph(vertex_count);
  std::vector<int> indegree(vertex_count, 0);

  for (const auto& [from, to] : edges) {
    graph[from].push_back(to);
    ++indegree[to];
  }

  std::queue<int> pending;
  for (int vertex = 0; vertex < vertex_count; ++vertex) {
    if (indegree[vertex] == 0) {
      pending.push(vertex);
    }
  }

  std::vector<int> order;
  order.reserve(vertex_count);

  while (!pending.empty()) {
    const int vertex = pending.front();
    pending.pop();
    order.push_back(vertex);

    for (int next : graph[vertex]) {
      if (--indegree[next] == 0) {
        pending.push(next);
      }
    }
  }

  if (static_cast<int>(order.size()) != vertex_count) {
    return std::nullopt; // 存在有向环
  }
  return order;
}

如果队列为空时仍有顶点没有加入结果，说明这些顶点属于某个环，或者依赖于环中的顶点，因此不存在完整的拓扑序。

同一个图通常可以有多个合法的拓扑序。若题目要求字典序最小的拓扑序，可以把普通队列替换为最小堆。

三、DFS 和 BFS 的比较

方法 主要依据 环检测方式 适合场景
DFS 后序遍历 发现指向递归栈的边 递归表达自然、需要沿依赖深入
BFS / Kahn 顶点入度 结果顶点数小于 V 迭代实现、需要逐层处理入度

两种方法的时间复杂度都是 O(V + E)。

四、常见题目

五、总结

  • 拓扑排序只适用于有向无环图。
  • DFS 使用逆后序遍历得到拓扑序，并通过递归栈检测环。
  • BFS 使用入度为 0 的顶点逐步删除依赖，并通过结果数量检测环。
  • 如果无法处理全部顶点，图中一定存在有向环。