关于递归实现拓扑排序的空间复杂度疑问：为何不是O(V+E)？

我刚接触算法与数据结构，最近研究拓扑排序的递归实现时发现一个矛盾点：各类资料普遍说这个算法的空间复杂度是O(V)（指存储结果的栈的大小），但我觉得这里忽略了递归调用栈的空间占用——毕竟递归解法会产生调用栈，所以我认为实际空间复杂度应该是O(V+E)才对。

对应的Java实现代码如下：

void topologicalVisit(GraphNode node, Stack<GraphNode> stack) {
  ArrayList<GraphNode> neighbors = getNeighbors(node);
  for (GraphNode neighbor : neighbors) {
    if (!neighbor.isVisited) {
      topologicalVisit(neighbor, stack);
    }
  }
  node.isVisited = true;
  stack.push(node);
}

void topologicalSort() {
  Stack<GraphNode> stack = new Stack<>();
  for (GraphNode node : nodeList) {
    if (!node.isVisited) {
      topologicalVisit(node, stack);
    }
  }

  while (!stack.isEmpty()) {
    System.out.print(stack.pop().name + " ");
  }
}

解答 #

首先明确：拓扑排序递归实现的最坏情况下空间复杂度确实是O(V)，而非O(V+E)，原因如下：

1. 递归调用栈的深度上限是V
   拓扑排序处理的是有向无环图（DAG），递归调用栈的深度等于当前遍历路径的长度。DAG中最长路径的节点数最多是V（比如一条链式的DAG：1→2→3→…→V），此时递归栈的深度就是V，不会超过这个值——因为每个节点只会被访问一次，一旦标记为已访问就不会再进入递归。

2. 为什么不是O(V+E)
   E是边的数量，但递归调用栈的空间和边数没有直接关系。每一条边只会触发一次递归调用，但调用完成后就会出栈，不会同时占用空间。比如一个节点有100条边，它会依次递归调用这100个邻居，但每次调用完成后栈就会弹出，所以同一时刻栈里的元素数量只和当前路径长度有关，和总边数无关。

3. 总空间的构成
   算法的总空间包括：

   • 存储结果的栈：大小是O(V)，因为每个节点都会入栈一次；
   • 递归调用栈：最坏情况是O(V)；
   • 访问标记数组（代码里的isVisited）：O(V)。
     把这些加起来，总空间复杂度还是O(V)——因为多个O(V)项合并后还是O(V)。

补充：如果有人提到O(V+E)，可能是混淆了邻接表的存储空间（邻接表本身需要O(V+E)的空间来存储图结构），但这属于图的存储开销，不是算法运行过程中额外的空间复杂度。算法的空间复杂度通常指除了输入数据之外，运行时临时占用的空间。

内容的提问来源于stack exchange，提问作者Alper Arslan