Topological Sort

Introduction

Topological sorting is a linear ordering of vertices in a directed graph where for every directed edge from vertex u to vertex v, vertex u comes before vertex v in the ordering. This concept is fundamental in solving problems involving dependencies, scheduling, and ordering tasks.

Key Characteristics

• Directed Acyclic Graph (DAG): Topological sort is only possible for Directed Acyclic Graphs. If the graph contains a cycle, a topological ordering does not exist.
• Linear Ordering: The result is a sequence of vertices where the relative order respects the direction of edges.

Why Use Topological Sort?

Topological sort is widely used in scenarios where tasks have prerequisites. For example:

1. Course Schedule: Determining the order in which you should take courses based on their prerequisites.
2. Build Systems: Managing dependencies in software compilation (e.g., Makefiles).
3. Task Scheduling: Assigning resources to jobs where some jobs must be completed before others.
4. Dependency Injection: Managing object creation order in software frameworks.

The Algorithms

There are two primary approaches to perform a topological sort: DFS (Depth First Search) and BFS (Kahn's Algorithm).

1. DFS Approach

The DFS approach involves traversing the graph recursively. When a node is finished (all its descendants have been visited), it is pushed onto a stack. The final topological order is obtained by popping elements from the stack.

Steps:

1. Create a stack and a visited set.
2. Perform DFS on all unvisited nodes.
3. When a node is fully processed (all neighbors visited), push it onto the stack.
4. Finally, pop all elements from the stack to get the topological order.

2. Kahn's Algorithm (BFS Approach)

Kahn's algorithm is based on the concept of indegree (the number of incoming edges to a node). Nodes with an indegree of 0 have no prerequisites and can be processed first.

Steps:

1. Calculate the indegree for every node.
2. Initialize a queue with all nodes having an indegree of 0.
3. While the queue is not empty:

• Dequeue a node and add it to the result.
• For each neighbor of the dequeued node, decrement its indegree.
• If a neighbor's indegree becomes 0, enqueue it.

1. If the result contains all nodes, it is a valid topological sort. If not, the graph contains a cycle.

Code Implementation

TypeScript Implementation (DFS)

type Graph = { [key: string]: string[] };

function topologicalSortDFS(graph: Graph): string[] {
  const visited = new Set<string>();
  const stack: string[] = [];

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

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

  return stack.reverse();
}

TypeScript Implementation (Kahn's Algorithm)

function topologicalSortKahn(graph: Graph): string[] {
  const indegree: { [key: string]: number } = {};
  const queue: string[] = [];
  const result: string[] = [];

  // Initialize indegree for all nodes
  for (const node in graph) {
    indegree[node] = 0;
  }
  for (const node in graph) {
    for (const neighbor of graph[node]) {
      indegree[neighbor]++;
    }
  }

  // Add nodes with indegree 0 to queue
  for (const node in indegree) {
    if (indegree[node] === 0) {
      queue.push(node);
    }
  }

  // Process queue
  while (queue.length > 0) {
    const node = queue.shift()!;
    result.push(node);

    for (const neighbor of graph[node]) {
      indegree[neighbor]--;
      if (indegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }

  if (result.length !== Object.keys(graph).length) {
    throw new Error("Graph contains a cycle");
  }

  return result;
}

Complexity Analysis

Both algorithms have the same time and space complexity:

• Time Complexity: O(V + E)
• We visit every vertex (V) once.
• We examine every edge (E) once to find neighbors or update indegrees.
• Space Complexity: O(V + E)
• We store the graph structure (O(E)).
• We store the visited set, stack, queue, and indegree map (O(V)).

Detecting Cycles

If a graph contains a cycle, a topological sort is impossible.

• In DFS: If you encounter a node that is already in the current recursion stack, a cycle exists.
• In Kahn's Algorithm: If the length of the resulting array is less than the total number of vertices, a cycle exists because some nodes were never processed (their indegree never reached zero).

Common Mistakes

1. Ignoring Disconnected Graphs: Always iterate through all nodes in the graph, not just the starting node, to ensure all components are processed.
2. Incorrect Stack Reversal: In the DFS approach, the order of nodes pushed onto the stack is the reverse of the topological order. Remember to reverse the stack at the end.
3. Modifying Input Graph: Be careful not to modify the input graph structure (like removing edges) unless explicitly intended, as it might affect other parts of the algorithm.

Practice Problems

1. Course Schedule II (LeetCode 210): Given a list of courses and their prerequisites, return the order to finish all courses.
2. Alien Dictionary (LeetCode 269): Determine the order of letters in an alien language based on sorted words.
3. Task Scheduler (LeetCode 621): Schedule tasks with cooldown periods (can be modeled using topological sort concepts).
4. Find Eventual Safe States (LeetCode 802): Find all nodes that are eventually safe (no outgoing edges to unsafe nodes).

Summary

Topological sort is a powerful algorithm for ordering tasks based on dependencies. Understanding both the DFS and Kahn's (BFS) approaches provides flexibility in solving different variations of the problem, particularly when you need to detect cycles or handle disconnected components.