Topological Sort Algorithm and Applications

Topological Sort

Welcome to Topological Sort, an algorithm for Directed Acyclic Graphs (DAGs). A topological sort is a linear ordering of a DAG's vertices such that for every directed edge from vertex u to vertex v, u comes before v in the ordering. This is incredibly useful for scheduling tasks with dependencies, such as a build process, course prerequisites, or project management.

---

1. The Core Idea: Ordering by Dependency

Imagine you have a list of tasks, where some tasks must be completed before others can begin. A topological sort gives you a valid sequence in which to perform these tasks.

It's important to note that a topological sort is only possible if the graph has no directed cycles. If a cycle exists (e.g., Task A depends on B, and B depends on A), then no valid ordering is possible.

There are two main algorithms for performing a topological sort: Kahn's Algorithm (which is BFS-based) and a DFS-based approach.

---

2. Kahn's Algorithm (BFS-based)

Kahn's algorithm works by identifying vertices that have no incoming edges (an in-degree of 0) and adding them to the sorted list. It then removes these vertices and their outgoing edges from the graph and repeats the process.

2.1. The Algorithm Step-by-Step

1. Compute In-degrees: Calculate the in-degree for every vertex in the graph.

2. Initialization:

   • Create a queue and add all vertices with an in-degree of 0 to it.
   • Create a list to store the sorted order.

3. Processing Loop:

   • While the queue is not empty:
     • Dequeue: Remove a vertex u from the queue and add it to the sorted list.
     • Update Neighbors: For each neighbor v of u:
       • Decrement the in-degree of v.
       • If the in-degree of v becomes 0, add v to the queue.

4. Completion:

   • If the sorted list contains N vertices, it is a valid topological sort. If it contains fewer than N vertices, the graph has a cycle.

2.2. Implementation

function topologicalSortKahn(adj) {
  const N = adj.length;
  const inDegree = Array(N).fill(0);
  for (let u = 0; u < N; u++) {
    for (const v of adj[u]) {
      inDegree[v]++;
    }
  }

  const queue = [];
  for (let i = 0; i < N; i++) {
    if (inDegree[i] === 0) {
      queue.push(i);
    }
  }

  const sortedOrder = [];
  while (queue.length > 0) {
    const u = queue.shift();
    sortedOrder.push(u);

    for (const v of adj[u]) {
      inDegree[v]--;
      if (inDegree[v] === 0) {
        queue.push(v);
      }
    }
  }

  if (sortedOrder.length !== N) {
    throw new Error("Graph contains a cycle, topological sort not possible.");
  }

  return sortedOrder;
}

---

3. DFS-based Algorithm

This approach uses Depth-First Search. The key idea is that a vertex is added to the sorted list only after all its descendants have been visited.

3.1. The Algorithm Step-by-Step

1. Initialization:

   • Create a visited set and a list to store the sorted order.

2. DFS Traversal:

   • For each vertex u in the graph:
     • If u has not been visited, perform a DFS traversal starting from u.

3. DFS Function (visit(u)):

   • Mark u as visited.
   • For each neighbor v of u:
     • If v has not been visited, recursively call visit(v).
   • After visiting all descendants of u, add u to the front of the sorted list.

4. Completion:

   • The final list is a valid topological sort.

3.2. Implementation

function topologicalSortDFS(adj) {
  const N = adj.length;
  const visited = new Set();
  const sortedOrder = [];

  function visit(u) {
    visited.add(u);
    for (const v of adj[u]) {
      if (!visited.has(v)) {
        visit(v);
      }
    }
    // All descendants visited, add u to the front
    sortedOrder.unshift(u);
  }

  for (let i = 0; i < N; i++) {
    if (!visited.has(i)) {
      visit(i);
    }
  }

  return sortedOrder;
}

---

4. Complexity Analysis

Both Kahn's algorithm and the DFS-based approach have the same complexity:

• Time Complexity: O(N + M), where N is the number of vertices and M is the number of edges.
• Space Complexity: O(N) for storing the in-degrees, the queue, and the sorted list.

---

Key Takeaway: Topological sort is essential for ordering tasks with dependencies in a DAG. Both Kahn's algorithm (using a queue and in-degrees) and the DFS-based approach (using recursion) can achieve this in linear time. The existence of a topological sort is also a proof that the graph is a DAG.