Topological Sorting

[!NOTE] You cannot put on your shoes before your socks. Topological Sorting is the algorithm for linearizing dependencies.

1. The Problem: Dependency Hell

In a Directed Acyclic Graph (DAG), we want to find a linear ordering of vertices such that for every edge u → v, vertex u comes before v in the ordering.

• Directed: Order matters.
• Acyclic: No cycles allowed. If A depends on B, and B depends on A, you’re stuck.

Applications

• Build Systems (Make, Maven, npm): Compiling libraries in order.
• Task Scheduling: Determining the sequence of jobs.
• Course Prerequisites: CS101 before CS102.

2. Kahn’s Algorithm (BFS based)

This algorithm uses the concept of In-Degree (number of incoming edges).

1. Calculate In-Degree for all nodes.
2. Add all nodes with In-Degree == 0 to a Queue (Ready set).
3. While Queue is not empty:
   • Remove node u from Queue (Add to result).
   • For each neighbor v of u:
   • Decrease In-Degree of v by 1.
   • If In-Degree of v becomes 0, add v to Queue.

---

3. Interactive: The Task Scheduler

Resolve the dependencies. Click the glowing nodes (In-Degree 0) to “Complete” them and unlock the next tasks.

Processing Queue: []

Result: []

---

4. Code Implementation: Kahn’s Algorithm

Java

public List<Integer> topologicalSort(int V, List<List<Integer>> adj) {
  int[] inDegree = new int[V];
  for (int u = 0; u < V; u++) {
    for (int v : adj.get(u)) {
      inDegree[v]++;
    }
  }

  Queue<Integer> queue = new LinkedList<>();
  for (int i = 0; i < V; i++) {
    if (inDegree[i] == 0) queue.add(i);
  }

  List<Integer> result = new ArrayList<>();
  while (!queue.isEmpty()) {
    int u = queue.poll();
    result.add(u);

    for (int v : adj.get(u)) {
      inDegree[v]--;
      if (inDegree[v] == 0) {
        queue.add(v);
      }
    }
  }

  if (result.size() != V) {
    throw new IllegalStateException("Graph has a cycle!");
  }
  return result;
}

Go

func TopologicalSort(V int, adj map[int][]int) ([]int, error) {
  inDegree := make([]int, V)
  for u := 0; u < V; u++ {
    for _, v := range adj[u] {
      inDegree[v]++
    }
  }

  queue := []int{}
  for i := 0; i < V; i++ {
    if inDegree[i] == 0 {
      queue = append(queue, i)
    }
  }

  result := []int{}
  for len(queue) > 0 {
    u := queue[0]
    queue = queue[1:]
    result = append(result, u)

    for _, v := range adj[u] {
      inDegree[v]--
      if inDegree[v] == 0 {
        queue = append(queue, v)
      }
    }
  }

  if len(result) != V {
    return nil, fmt.Errorf("Graph has a cycle")
  }
  return result, nil
}

---

5. Deep Dive Strategy Lab: Topological Sorting

Intuition Through Analogy

Think of this chapter like city route planning. The goal is not to memorize a fixed trick, but to repeatedly answer:

1. What is the bottleneck?
2. Which constraint dominates (time, memory, latency, correctness)?
3. Which representation makes the bottleneck easier to eliminate?