Topological Sort Space Complexity

Question

Here is the topological sort algorithm, I checked everywhere and I always found the space complexity as O(V) which is the size of the stack, but what I don't understand is: Why nobody considers this is a recursive solution. So, recursion also adds to space complexity and I think it is actually O(V+E).

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 + " ");
  }
}

(I am sorry, I am just new with algorithm and ds)

Answer 1

You may be right that this particular implementation uses O(+) space in the worst case. It depends on how getNeighbors is implemented. If that method creates a new ArrayList and returns it, then this will consume O() memory in the worst case.

But that would be particular to that implementation. If getNeighbors would return the internal neighbors arraylist itself, then no auxiliary memory is allocated other than the local variable neighbors (This may be bad practice as such a getter still allows the caller to mutate that list in the graph's data structure). Or, the graph's API could have given an iterator over the neighbors. Either way the call stack would only have needed O() space. With an iterator it would be something like:

void topologicalVisit(GraphNode node, Stack<GraphNode> stack) {
  ListIterator<GraphNode> neighborIterator = getNeighborIterator(node);
  while(neighborIterator.hasNext()) {
    GraphNode neighbor = neighborIterator.next();
    if (!neighbor.isVisited) {
      topologicalVisit(neighbor, stack);
    }
  }
  node.isVisited = true;
  stack.push(node);
}

Some notes though:

• The depth of the recursion is limited by the number of nodes, not by the number of edges. As the graph is assumed to be a DAG (a precondition for topological sort), a node is not visited more than once in a single recursion path; there is no path into recursion that is longer than the number of nodes (minus one).

• If it is not guaranteed that the graph is a DAG, then this code could get into an infinite recursion, as it could run over a cycle. To protect your code against a graph that has cycles, you should add a separate state for when a node is being expanded (i.e. it is on the recursion path), so that you would detect a cycle and could raise an exception. See Wikipedia's depth-first algorithm where they use a temporary mark for this purpose.