Topological Sort Using Depth-First Search (DFS)

Problem Statement❯

Topological Sort is a linear ordering of vertices in a directed graph such that for every directed edge u → v, vertex u comes before v in the ordering.

It is only applicable to Directed Acyclic Graphs (DAGs) and is used in scenarios like task scheduling, build systems, and dependency resolution.

Examples❯

Graph (Edges)	Topological Sort	Description
0 → 1, 0 → 2, 1 → 3, 2 → 3	0 → 2 → 1 → 3	Multiple valid orderings possible, DFS pushes deeper nodes first
5 → 0, 5 → 2, 4 → 0, 4 → 1, 2 → 3, 3 → 1	5 → 4 → 2 → 3 → 1 → 0	Topological sort based on dependencies
1 → 2, 2 → 3	1 → 2 → 3	Straightforward chain
None	Any order	Empty graph or no edges
0 → 1, 1 → 2, 2 → 0	Not possible	Cycle detected, not a DAG

Solution❯

Understanding Topological Sort Using DFS

Topological sorting is used to order the vertices of a directed acyclic graph (DAG) such that for every directed edge u → v, vertex u comes before v in the ordering.

When is it used?

This is particularly useful in scenarios like task scheduling, course prerequisite planning, or build systems where some tasks must be done before others.

How does the DFS approach help?

In a DFS-based topological sort, we go as deep as possible before backtracking. As we finish visiting all neighbors of a node, we push it onto a stack. This means the deepest dependencies get placed on the stack first, ensuring the correct topological order when the stack is reversed.

Case 1: Normal DAG

In a regular acyclic graph with no special structure, each node will be visited once, and the order of pushing nodes onto the stack will ensure that dependencies are respected.

Case 2: Disconnected Components

If the graph has multiple components that aren't connected, we need to run DFS on every unvisited node to ensure all components are included in the topological order.

Case 3: Cycle Detection

If the graph contains a cycle, topological sorting is not possible. The standard DFS-based approach doesn’t detect cycles by itself unless we add an additional mechanism to track recursion stack states. So it’s assumed the graph is a DAG for correctness.

Example

Consider a graph with edges: A → B, B → C, A → C. Starting DFS from A visits B, then C. C is pushed first, then B, then A. Final topological order (after reversing the stack) is A, B, C.

Algorithm Steps❯

Initialize a visited set and a stack (for order).
Define a recursive dfs(node):
- Mark node as visited.
- For each neighbor of node:
  - If not visited, call dfs(neighbor).
- After visiting all neighbors, push node to stack.
Call dfs on all unvisited nodes.
Reverse the stack to get the topological order.

Code

JavaScript

function topologicalSort(graph) {
  const visited = new Set();
  const stack = [];

  function dfs(node) {
    visited.add(node);
    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        dfs(neighbor);
      }
    }
    stack.push(node);
  }

  for (const node in graph) {
    if (!visited.has(Number(node))) {
      dfs(Number(node));
    }
  }

  return stack.reverse();
}

const graph = {
  5: [0, 2],
  4: [0, 1],
  2: [3],
  3: [1],
  0: [],
  1: []
};

console.log("Topological Sort:", topologicalSort(graph));

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(V + E)	Even in the best case, each vertex and its edges must be visited to ensure proper order.
Average Case	O(V + E)	Every node is visited once and all its outgoing edges are checked once during DFS.
Worst Case	O(V + E)	In the worst case, the graph is dense, and all vertices and edges must be processed.

Space Complexity❯

O(V + E)

Explanation: We use a visited set (O(V)), a stack (O(V)), and an adjacency list (O(V + E)) to represent the graph.

⬅ Previous TopicCheck if a Graph is Bipartite using DFS

Next Topic ⮕Topological Sort using Kahn's Algorithm