Topological Sort Tutorial

Introduction

Topological Sort is an algorithm used to order the vertices of a Directed Acyclic Graph (DAG) in a linear sequence. In this sequence, for every directed edge ( uv ) from vertex ( u ) to vertex ( v ), ( u ) comes before ( v ). This sorting is useful in scenarios where you need to schedule tasks or resolve dependencies.

Key Concepts

1. Directed Acyclic Graph (DAG): A graph with directed edges and no cycles.
2. Topological Order: A linear ordering of vertices such that for every directed edge ( uv ), vertex ( u ) comes before vertex ( v ).

Algorithms for Topological Sort

1. Kahn's Algorithm

Kahn's Algorithm uses the concept of in-degrees (number of incoming edges) to determine the order of vertices. It is suitable for finding a topological sort using Breadth-First Search (BFS).

2. Depth-First Search (DFS) Based Algorithm

The DFS-based algorithm uses a stack to store the vertices in the topological order. It is suitable for finding a topological sort using Depth-First Search (DFS).

Kahn's Algorithm Implementation

Here’s a JavaScript implementation of Kahn’s Algorithm for Topological Sort:

function topologicalSortKahn(graph) {
  const inDegree = new Array(graph.length).fill(0);
  const queue = [];
  const result = [];

  // Compute the in-degrees of all vertices
  for (let u = 0; u < graph.length; u++) {
    for (const v of graph[u]) {
      inDegree[v]++;
    }
  }

  // Add vertices with in-degree 0 to the queue
  for (let i = 0; i < inDegree.length; i++) {
    if (inDegree[i] === 0) {
      queue.push(i);
    }
  }

  // Process the vertices in the queue
  while (queue.length > 0) {
    const u = queue.shift();
    result.push(u);

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

  // Check for cycles (if result length != graph length)
  if (result.length !== graph.length) {
    throw new Error('The graph contains a cycle');
  }

  return result;
}

// Example Usage
const graph = [
  [1, 2], // 0 -> 1, 0 -> 2
  [2],    // 1 -> 2
  []      // 2
];

console.log(topologicalSortKahn(graph)); // Output: [0, 1, 2] or [0, 2, 1]

Topological Sort on 2d Grid

class TopologicalSort {
    constructor(rows, cols) {
        this.rows = rows;
        this.cols = cols;
        this.graph = new Map();
        this.inDegree = new Map();
    }

    // Convert grid position to unique key
    key(row, col) {
        return `${row},${col}`;
    }

    // Add directed edge from (r1,c1) to (r2,c2)
    addEdge(r1, c1, r2, c2) {
        const from = this.key(r1, c1);
        const to = this.key(r2, c2);
        
        if (!this.graph.has(from)) this.graph.set(from, []);
        if (!this.inDegree.has(to)) this.inDegree.set(to, 0);
        if (!this.inDegree.has(from)) this.inDegree.set(from, 0);
        
        this.graph.get(from).push(to);
        this.inDegree.set(to, this.inDegree.get(to) + 1);
    }

    // Get topological ordering
    sort() {
        const queue = [];
        const result = [];
        
        // Add all nodes with 0 in-degree
        for (const [node, degree] of this.inDegree) {
            if (degree === 0) queue.push(node);
        }
        
        while (queue.length) {
            const node = queue.shift();
            result.push(node);
            
            if (this.graph.has(node)) {
                for (const neighbor of this.graph.get(node)) {
                    this.inDegree.set(neighbor, this.inDegree.get(neighbor) - 1);
                    if (this.inDegree.get(neighbor) === 0) {
                        queue.push(neighbor);
                    }
                }
            }
        }
        
        return result.length === this.inDegree.size ? result : [];
    }
}

Topological sorting using DFS

function topologicalSort(graph) {
  const visited = new Set(); // Tracks visited nodes
  const stack = []; // Stores the topological order

  // Helper function for DFS
  function dfs(node) {
    if (visited.has(node)) return; // If already visited, skip
    visited.add(node); // Mark node as visited

    // Visit all its neighbors
    for (const neighbor of graph[node]) {
      dfs(neighbor);
    }

    // Add the node to the stack when finished
    stack.push(node);
  }

  // Iterate through all nodes in the graph
  for (const node of Object.keys(graph).map(Number)) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }

  // Reverse the stack to get the correct topological order
  return stack.reverse();
}

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

console.log(topologicalSort(graph));
// Output: [5, 4, 2, 3, 1, 0] (One valid order)

207. Course Schedule

/* 0: Not visited 1: Visiting (current DFS path) 2: Fully visited (processed) */

function canFinish(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  const visited = new Array(numCourses).fill(0);

  // Build adjacency list
  for (const [course, prereq] of prerequisites) {
    graph[prereq].push(course);
  }

  // Helper function for DFS
  function dfs(course) {
    if (visited[course] === 1) return false; // Cycle detected
    if (visited[course] === 2) return true;  // Already processed

    visited[course] = 1; // Mark as visiting

    for (const nextCourse of graph[course]) {
      if (!dfs(nextCourse)) return false;
    }

    visited[course] = 2; // Mark as fully visited
    return true;
  }

  // Check all courses
  for (let i = 0; i < numCourses; i++) {
    if (!dfs(i)) return false;
  }

  return true;
}

210. Course Schedule II

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var findOrder = function (numCourses, prerequisites) {
  const visited = {}
  const graph = {}
  const res = []

  for (let i = 0; i < numCourses; i++) {
    visited[i] = 0 //Unvisited
    graph[i] = []
  }

  for (const [u, v] of prerequisites) {
    graph[v].push(u)
  }

  const dfs = (node) => {
    if (visited[node] === 1) return false //Visiting
    if (visited[node] === -1) return true //Visited
    visited[node] = 1

    for (const nbr of graph[node]) {
      if (!dfs(nbr)) return false
    }

    visited[node] = -1
    res.push(node)
    return true
  }

  for (let i = 0; i < numCourses; i++) {
    if (visited[i] === 0 && !dfs(i)) return []
  }
  return res.reverse()
};