Skip to main content
Mapagam

Implementing Topological Sort

1. Understanding Topological Ordering

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

Property Description Notes
Directed Acyclic Graph (DAG) A graph with directed edges and no cycles Topological sort is only possible on DAGs
In-degree Number of incoming edges to a vertex Used in Kahn's algorithm for topological sort
Linear Ordering Each vertex appears once in the sequence Not unique; multiple valid orderings may exist

Example: Basic Concept

const graph = {
  'A': ['B'],
  'B': ['C'],
  'C': []
};

// Valid topological order: A → B → C
Note: If a cycle exists in the graph, topological sorting is not possible.

Steps to Perform Topological Sort

  1. Calculate in-degrees for all vertices
  2. Add all vertices with in-degree 0 to a queue
  3. Process the queue, reducing in-degrees of neighbors
  4. If any vertex has in-degree > 0 after processing, a cycle exists

2. Implementing Kahn's Algorithm

Kahn's algorithm is a classic approach for performing topological sorting on directed acyclic graphs (DAGs). It works by repeatedly removing nodes with no incoming edges and updating the graph accordingly.

Step Description Action
1 Calculate in-degrees for all nodes Count incoming edges for each node
2 Initialize queue with nodes having in-degree 0 Add all nodes with zero in-degrees to a queue
3 Process nodes in queue Remove node from queue, add to result, reduce in-degrees of neighbors
4 Update in-degrees Decrease in-degree of neighbors when a node is processed
5 Repeat until queue is empty Continue processing nodes with in-degree 0
6 Check for cycles If result size is less than total nodes, graph has a cycle

Example: Kahn's Algorithm Implementation in JavaScript

function topologicalSortKahn(vertices, edges) {
  const inDegree = new Array(vertices).fill(0);
  const adjList = Array(vertices)
    .fill()
    .map(() => []);

  // Build adjacency list and in-degree array
  for (const [from, to] of edges) {
    adjList[from].push(to);
    inDegree[to]++;
  }

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

  const result = [];

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

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

  return result.length === vertices ? result : [];
}

// Example usage:
const vertices = 6;
const edges = [
  [5, 2],
  [5, 0],
  [4, 0],
  [4, 1],
  [2, 3],
  [3, 1]
];

console.log(topologicalSortKahn(vertices, edges)); // [5, 4, 2, 3, 1, 0]
Note: The algorithm returns an empty array if a cycle is detected, indicating that topological sorting is not possible.

Algorithm Summary

  • Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges
  • Space Complexity: O(V + E) for storing the adjacency list and in-degree array
  • Use Case: Detecting cycles, scheduling tasks with dependencies

3. Implementing DFS-based Topological Sort

Topological sorting using Depth-First Search (DFS) is a classic algorithm for ordering vertices in a Directed Acyclic Graph (DAG). It works by performing DFS and pushing nodes to a stack once all their descendants are visited.

Step Description Implementation
1. Initialize Mark all nodes as unvisited and create an empty stack. const visited = new Set();\nconst stack = [];
2. DFS Traversal For each unvisited node, perform DFS. function dfs(node) {\n visited.add(node);\n for (const neighbor of graph[node]) {\n if (!visited.has(neighbor)) {\n dfs(neighbor);\n }\n }\n stack.push(node);\n}
3. Build Result Pop elements from the stack to get topological order. const result = [];\nwhile (stack.length > 0) {\n result.push(stack.pop());\n}\nreturn result;

Example: DFS-based Topological Sort

const graph = {\n  'A': ['B'],\n  'B': ['C'],\n  'C': []\n};\n\nfunction topologicalSort(graph) {\n  const visited = new Set();\n  const stack = [];\n\n  function dfs(node) {\n    visited.add(node);\n    for (const neighbor of graph[node]) {\n      if (!visited.has(neighbor)) {\n        dfs(neighbor);\n      }\n    }\n    stack.push(node);\n  }\n\n  for (const node in graph) {\n    if (!visited.has(node)) {\n      dfs(node);\n    }\n  }\n\n  const result = [];\n  while (stack.length > 0) {\n    result.push(stack.pop());\n  }\n  return result;\n}\n\nconsole.log(topologicalSort(graph)); // ['A', 'B', 'C']
Note: This approach assumes the graph is a DAG. If cycles exist, the algorithm will not detect them but will still produce an ordering.

4. Detecting Cycle in Directed Graph

Method Description Time Complexity Space Complexity
DFS-based Detection Uses DFS to detect back edges in a directed graph. If a back edge exists, a cycle is present. O(V + E) O(V)
Kahn's Algorithm (BFS) Uses in-degree tracking and BFS to detect cycles by ensuring all nodes are processed. O(V + E) O(V)

Example: DFS-based Cycle Detection

function hasCycleDFS(graph) {
  const visited = new Set();
  const recStack = new Set();

  for (let node in graph) {
    if (!visited.has(node)) {
      if (detectCycleUtil(graph, node, visited, recStack)) {
        return true;
      }
    }
  }

  return false;
}

function detectCycleUtil(graph, node, visited, recStack) {
  visited.add(node);
  recStack.add(node);

  for (let neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      if (detectCycleUtil(graph, neighbor, visited, recStack)) {
        return true;
      }
    } else if (recStack.has(neighbor)) {
      return true;
    }
  }

  recStack.delete(node);
  return false;
}

Example: Kahn's Algorithm for Cycle Detection

function hasCycleKahn(graph) {
  const inDegree = {};
  for (let node in graph) {
    inDegree[node] = 0;
  }

  for (let node in graph) {
    for (let neighbor of graph[node]) {
      inDegree[neighbor]++;
    }
  }

  const queue = [];
  for (let node in inDegree) {
    if (inDegree[node] === 0) {
      queue.push(node);
    }
  }

  let processedCount = 0;
  while (queue.length > 0) {
    const node = queue.shift();
    processedCount++;

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

  return processedCount !== Object.keys(graph).length;
}
Note: The DFS method uses recursion stack to detect back edges, while Kahn's algorithm uses in-degrees and a queue.

5. Finding All Topological Orderings

Topological sorting is not unique for a given directed acyclic graph (DAG). There can be multiple valid orderings of nodes that respect the dependencies. Finding all topological orderings involves exploring all possible valid sequences.

Property Description Notes
Algorithm Backtracking-based approach to generate all valid orderings Starts with nodes having in-degree 0, recursively explores all valid next nodes
Time Complexity O(V! × E) Where V is the number of vertices and E is the number of edges. In worst case, all permutations are valid
Space Complexity O(V) For storing the in-degree array and recursion stack

Example: Finding All Orderings

function findAllTopologicalOrderings(graph) {
  const vertices = Object.keys(graph);
  const inDegree = {};
  const result = [];

  // Initialize in-degrees
  vertices.forEach(v => inDegree[v] = 0);
  vertices.forEach(v => {
    graph[v].forEach(n => inDegree[n]++);
  });

  const backtrack = (currentOrder) => {
    if (currentOrder.length === vertices.length) {
      result.push([...currentOrder]);
      return;
    }

    for (const v of vertices) {
      if (inDegree[v] === 0) {
        // Choose
        currentOrder.push(v);
        const tempInDegree = { ...inDegree };
        graph[v].forEach(n => inDegree[n]--);

        // Explore
        backtrack(currentOrder);

        // Unchoose (backtrack)
        currentOrder.pop();
        Object.assign(inDegree, tempInDegree);
      }
    }
  };

  backtrack([]);
  return result;
}

// Example usage:
const graph = {
  'A': ['C'],
  'B': ['C'],
  'C': ['D'],
  'D': []
};

console.log(findAllTopologicalOrderings(graph));
// Output: [['A', 'B', 'C', 'D'], ['B', 'A', 'C', 'D']]
Note: The number of valid topological orderings can grow factorially with the number of nodes, making this approach inefficient for large graphs.

6. Scheduling Tasks with Prerequisites

Topological sort is commonly used to schedule tasks that have prerequisites. It ensures that a task is only scheduled after all its dependencies are completed.

Task Prerequisites Order
Task A [] 1
Task B ['A'] 2
Task C ['A', 'B'] 3

Example: Scheduling Tasks Using Topological Sort

const tasks = ['A', 'B', 'C'];
const prerequisites = [
  ['A', 'B'],
  ['B', 'C']
];

function scheduleTasks(tasks, prerequisites) {
  const graph = new Map();
  const inDegree = new Map();

  // Initialize graph and in-degree
  tasks.forEach(task => {
    graph.set(task, []);
    inDegree.set(task, 0);
  });

  // Build the graph
  prerequisites.forEach(([prereq, task]) => {
    graph.get(prereq).push(task);
    inDegree.set(task, inDegree.get(task) + 1);
  });

  // Find tasks with no prerequisites
  const queue = [];
  inDegree.forEach((degree, task) => {
    if (degree === 0) queue.push(task);
  });

  const result = [];

  while (queue.length > 0) {
    const task = queue.shift();
    result.push(task);

    // Reduce in-degree of dependent tasks
    graph.get(task).forEach(dependent => {
      inDegree.set(dependent, inDegree.get(dependent) - 1);
      if (inDegree.get(dependent) === 0) {
        queue.push(dependent);
      }
    });
  }

  return result;
}

console.log(scheduleTasks(tasks, prerequisites)); // ['A', 'B', 'C']
Note: If a cycle exists in the prerequisites, scheduling is impossible. The algorithm can detect cycles by checking if all tasks are included in the result.

7. Finding Minimum Height Trees

Minimum Height Trees (MHTs) are trees with the smallest possible height when rooted at any node. The height of a tree is defined as the maximum distance from the root to any leaf node.

Property Description Notes
Tree Representation Graph with n nodes and n-1 edges, connected and acyclic Each node has a degree (number of neighbors)
Height Definition Maximum depth of any node from root Minimized by choosing optimal root(s)
Root Selection Optimal root(s) are the center(s) of the tree Center is the middle node(s) of the longest path

Example: Finding MHT Roots

function findMinHeightTrees(n, edges) {
    if (n === 1) return [0];
    
    const adj = Array(n).fill().map(() => []);
    const degree = Array(n).fill(0);
    
    for (const [u, v] of edges) {
        adj[u].push(v);
        adj[v].push(u);
        degree[u]++;
        degree[v]++;
    }
    
    const leaves = [];
    for (let i = 0; i < n; i++) {
        if (degree[i] === 1) leaves.push(i);
    }
    
    let remaining = n;
    while (remaining > 2) {
        const newLeaves = [];
        for (const leaf of leaves) {
            const neighbor = adj[leaf].pop();
            degree[neighbor]--;
            if (degree[neighbor] === 1) newLeaves.push(neighbor);
        }
        leaves.splice(0, leaves.length, ...newLeaves);
        remaining -= leaves.length;
    }
    
    return leaves;
}

// Example usage:
const n = 4;
const edges = [[1, 0], [1, 2], [1, 3]];
console.log(findMinHeightTrees(n, edges)); // Output: [1]
Note: The algorithm uses a BFS-like approach to iteratively remove leaf nodes until 1 or 2 nodes remain, which represent the MHT roots.

Algorithm Summary

  • Build adjacency list and compute degrees of each node
  • Start with all leaf nodes (degree 1) in a queue
  • Repeatedly remove leaves and update neighbor degrees
  • Continue until 1 or 2 nodes remain — these are the MHT roots

8. Finding Alien Dictionary Order

Given a list of words sorted lexicographically according to an alien language's alphabet order, reconstruct the possible alphabetical order of the language.

Property Description Notes
Input List of words in lexicographically sorted order Words are from the alien dictionary
Output Valid topological order of the alien alphabet May have multiple valid orders
Approach Build a graph from adjacent word comparisons and perform topological sort Each pair of words gives a constraint on character order

Example: Alien Dictionary Order

const words = ["wrt", "wrf", "er", "ett", "rtff"];

function alienOrder(words) {
  const graph = new Map();
  const inDegree = new Map();

  // Initialize all characters
  for (let word of words) {
    for (let char of word) {
      if (!graph.has(char)) {
        graph.set(char, []);
        inDegree.set(char, 0);
      }
    }
  }

  // Build graph from adjacent words
  for (let i = 0; i < words.length - 1; i++) {
    const word1 = words[i];
    const word2 = words[i + 1];

    let j = 0;
    while (j < word1.length && j < word2.length) {
      const char1 = word1[j];
      const char2 = word2[j];

      if (char1 !== char2) {
        // Add edge from char1 to char2
        if (!graph.get(char1).includes(char2)) {
          graph.get(char1).push(char2);
          inDegree.set(char2, inDegree.get(char2) + 1);
        }
        break;
      }
      j++;
    }

    // Check for invalid case: longer word comes before shorter one with same prefix
    if (j < word1.length && j === word2.length) {
      return "";
    }
  }

  // Topological sort using Kahn's algorithm
  const queue = [];
  for (let [char, degree] of inDegree) {
    if (degree === 0) queue.push(char);
  }

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

    for (let neighbor of graph.get(char)) {
      inDegree.set(neighbor, inDegree.get(neighbor) - 1);
      if (inDegree.get(neighbor) === 0) {
        queue.push(neighbor);
      }
    }
  }

  // Check if all characters were included (no cycles)
  return result.length === inDegree.size ? result.join("") : "";
}

console.log(alienOrder(words)); // "wertf"
Note: The algorithm assumes that the input words are sorted according to the alien dictionary's lexicographical order. If this assumption is violated, the result will be invalid.
Warning: If there is a cycle in the graph, it means that the input words are inconsistent and no valid order exists.

9. Reconstructing Sequence

Topological sorting can be used to reconstruct a sequence of tasks or items based on their dependencies. This is particularly useful in project management, build systems, and scheduling.

Step Description Action
1 Identify all nodes with in-degree 0 Start with tasks that have no prerequisites
2 Process nodes in order Add each node to the result sequence and reduce in-degrees of dependent nodes
3 Repeat until all nodes are processed Continue until no more nodes with in-degree 0 exist

Example: Reconstructing a Build Order

const tasks = [
  { id: 'A', dependencies: [] },
  { id: 'B', dependencies: ['A'] },
  { id: 'C', dependencies: ['A'] },
  { id: 'D', dependencies: ['B', 'C'] }
];

function reconstructSequence(tasks) {
  const inDegree = new Map();
  const graph = new Map();

  // Initialize in-degree and graph
  tasks.forEach(task => {
    inDegree.set(task.id, 0);
    graph.set(task.id, []);
  });

  tasks.forEach(task => {
    task.dependencies.forEach(dep => {
      if (graph.has(dep)) {
        graph.get(dep).push(task.id);
        inDegree.set(task.id, inDegree.get(task.id) + 1);
      }
    });
  });

  const queue = [];
  const result = [];

  // Find all nodes with in-degree 0
  inDegree.forEach((degree, node) => {
    if (degree === 0) queue.push(node);
  });

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

    const neighbors = graph.get(current) || [];
    neighbors.forEach(node => {
      inDegree.set(node, inDegree.get(node) - 1);
      if (inDegree.get(node) === 0) {
        queue.push(node);
      }
    });
  }

  return result;
}

console.log(reconstructSequence(tasks)); // ['A', 'B', 'C', 'D']
Note: If the result sequence does not contain all tasks, it indicates a cycle in dependencies.

Key Points

  • Topological sort is used to determine a valid order of tasks with dependencies
  • Reconstructing a sequence involves processing nodes with zero in-degree
  • Cycles in dependencies prevent a valid sequence from being constructed

10. Finding Valid Build Order

Property Description Usage
buildOrder Array of tasks in valid order to execute topologicalSort(tasks, dependencies)
dependencies Map of task to its prerequisites { task: [prereq1, prereq2] }

Example: Finding Valid Build Order

function topologicalSort(tasks, dependencies) {
  const inDegree = {};
  tasks.forEach(task => inDegree[task] = 0);
  
  Object.keys(dependencies).forEach(task => {
    dependencies[task].forEach(prereq => {
      inDegree[prereq] = (inDegree[prereq] || 0) + 1;
    });
  });

  const queue = [];
  const result = [];

  Object.keys(inDegree).forEach(task => {
    if (inDegree[task] === 0) queue.push(task);
  });

  while (queue.length > 0) {
    const task = queue.shift();
    result.push(task);
    
    if (dependencies[task]) {
      dependencies[task].forEach(prereq => {
        inDegree[prereq]--;
        if (inDegree[prereq] === 0) queue.push(prereq);
      });
    }
  }

  return result.length === tasks.length ? result : [];
}

const tasks = ['A', 'B', 'C', 'D'];
const dependencies = {
  'B': ['A'],
  'C': ['A'],
  'D': ['B', 'C']
};

console.log(topologicalSort(tasks, dependencies)); // ['A', 'B', 'C', 'D']
Note: If the build order includes a cycle, it's impossible to complete all tasks. The function returns an empty array in such cases.

Was this article helpful?

Related Cheat Sheets