Topological Sort

topological-sort: The Ultimate Cheatsheet

1. Detailed Explanation

• What is topological-sort? Topological sort is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u -> v, vertex u comes before vertex v in the ordering. Essentially, it provides a sequence of nodes that respects the dependencies between them.

• Why is it important and what kind of problems does it solve? Topological sort is crucial for solving problems involving dependencies, scheduling, and task ordering. It’s used in scenarios where the order of execution or completion is critical. Common applications include:

  • Course scheduling: Determining the order in which courses must be taken, given prerequisites.
  • Task scheduling: Ordering tasks in a project based on dependencies.
  • Dependency resolution: Resolving dependencies between software packages.
  • Data serialization: Determining the order in which data objects should be serialized based on their dependencies.
  • Instruction scheduling: Optimizing the order of instructions in a compiler.

• Core concepts, underlying principles, and key terminology.

  • Directed Acyclic Graph (DAG): A directed graph with no cycles. Topological sort is only possible on DAGs.
  • Dependencies: A relationship between two nodes where one node depends on the other. Represented by directed edges.
  • In-degree: The number of incoming edges to a vertex.
  • Out-degree: The number of outgoing edges from a vertex.
  • Source Node: A node with an in-degree of 0. Topological sort usually starts with source nodes.
  • Khan’s Algorithm: A common algorithm for topological sort that uses in-degrees and a queue.
  • Depth-First Search (DFS): Another algorithm for topological sort, which relies on recursively exploring nodes and adding them to the sorted list in reverse order of completion.

2. When to Use topological-sort (and When Not To)

• Identify problem patterns that suggest topological-sort is a good fit.

  • The problem involves a set of tasks or items with dependencies between them.
  • The problem requires determining a valid order for performing these tasks or items, respecting the dependencies.
  • The problem explicitly mentions prerequisites or dependencies.
  • The problem can be modeled as a directed graph.
  • The graph is guaranteed to be acyclic (or the problem requires detecting cycles).

• Discuss scenarios where a different data structure or algorithm would be more appropriate.

  • Cyclic graph: If the graph contains cycles, topological sort is not possible. Cycle detection algorithms (e.g., using DFS) are needed first.
  • Undirected graph: Topological sort is specifically for directed graphs. For undirected graphs, other graph traversal algorithms like Breadth-First Search (BFS) or Depth-First Search (DFS) might be more appropriate, depending on the specific problem.
  • No dependencies: If there are no dependencies between the elements, any order is valid, and topological sort is unnecessary. A simple sorting algorithm may suffice if a specific order is required based on some other criteria.
  • Finding shortest paths: If the goal is to find the shortest path between two nodes, algorithms like Dijkstra’s or Bellman-Ford are more appropriate.
  • Finding minimum spanning tree: If the goal is to find the minimum spanning tree of a graph, algorithms like Kruskal’s or Prim’s are more appropriate.

3. Core Algorithm / Data Structure Template

Khan’s Algorithm (using in-degrees and a queue):

1. Calculate In-degrees: Calculate the in-degree of each node in the graph.
2. Initialize Queue: Add all nodes with an in-degree of 0 to a queue. These are the source nodes.
3. Process Queue: While the queue is not empty: a. Dequeue a node u. b. Add u to the topological sorted list. c. For each neighbor v of u: i. Decrement the in-degree of v. ii. If the in-degree of v becomes 0, add v to the queue.
4. Check for Cycles: If the number of nodes in the topological sorted list is not equal to the total number of nodes in the graph, then the graph contains a cycle, and a topological sort is not possible.

DFS Algorithm (using recursion):

1. Initialization: Create a visited set and an empty result list.
2. Iterate through nodes: For each node in the graph, if it hasn’t been visited, call the DFS function.
3. DFS Function: a. Mark the current node as visited. b. For each neighbor of the current node: i. If the neighbor hasn’t been visited, recursively call the DFS function on the neighbor. c. Append the current node to the beginning of the result list (post-order traversal).
4. Reverse: Reverse the result list to get the topological order.

4. Code Implementations (Python, Java, C++)

Python

from collections import defaultdict, deque

def topological_sort_khan(graph):
    """
    Topological sort using Khan's algorithm.

    Args:
        graph: A dictionary representing the graph, where keys are nodes and values are lists of neighbors.

    Returns:
        A list representing the topological sorted order, or None if a cycle exists.
    """

    in_degree = defaultdict(int)
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    queue = deque([node for node in graph if in_degree[node] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(result) != len(graph):
        return None  # Cycle detected
    else:
        return result

def topological_sort_dfs(graph):
    """
    Topological sort using Depth-First Search.

    Args:
        graph: A dictionary representing the graph, where keys are nodes and values are lists of neighbors.

    Returns:
        A list representing the topological sorted order, or None if a cycle exists (implicitly detected via recursion depth in real implementations).
    """
    visited = set()
    result = []

    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        result.insert(0, node)  # Prepend to build reverse topological order

    for node in graph:
        if node not in visited:
            dfs(node)

    return result

Java

import java.util.*;

public class TopologicalSort {

    public static List<Integer> topologicalSortKhan(Map<Integer, List<Integer>> graph) {
        Map<Integer, Integer> inDegree = new HashMap<>();
        for (Integer node : graph.keySet()) {
            inDegree.put(node, 0); // Initialize in-degree
        }

        for (Integer node : graph.keySet()) {
            for (Integer neighbor : graph.get(node)) {
                inDegree.put(neighbor, inDegree.get(neighbor) + 1);
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (Integer node : inDegree.keySet()) {
            if (inDegree.get(node) == 0) {
                queue.offer(node);
            }
        }

        List<Integer> result = new ArrayList<>();
        int count = 0;

        while (!queue.isEmpty()) {
            Integer node = queue.poll();
            result.add(node);
            count++;

            for (Integer neighbor : graph.get(node)) {
                inDegree.put(neighbor, inDegree.get(neighbor) - 1);
                if (inDegree.get(neighbor) == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        if (count != graph.size()) {
            return null; // Cycle detected
        } else {
            return result;
        }
    }

    public static List<Integer> topologicalSortDFS(Map<Integer, List<Integer>> graph) {
        Set<Integer> visited = new HashSet<>();
        List<Integer> result = new ArrayList<>();

        for (Integer node : graph.keySet()) {
            if (!visited.contains(node)) {
                dfs(graph, node, visited, result);
            }
        }

        Collections.reverse(result);
        return result;
    }

    private static void dfs(Map<Integer, List<Integer>> graph, Integer node, Set<Integer> visited, List<Integer> result) {
        visited.add(node);

        for (Integer neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                dfs(graph, neighbor, visited, result);
            }
        }

        result.add(node);
    }

    public static void main(String[] args) {
        // Example Usage
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(3));
        graph.put(2, Arrays.asList(3));
        graph.put(3, new ArrayList<>());

        List<Integer> sortedList = topologicalSortKhan(graph);
        if (sortedList != null) {
            System.out.println("Topological Sort (Khan's): " + sortedList);
        } else {
            System.out.println("Cycle detected");
        }

        sortedList = topologicalSortDFS(graph);
        System.out.println("Topological Sort (DFS): " + sortedList);
    }
}

C++

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

vector<int> topologicalSortKhan(map<int, vector<int>>& graph) {
    map<int, int> inDegree;
    for (auto const& [node, neighbors] : graph) {
        inDegree[node] = 0;
    }

    for (auto const& [node, neighbors] : graph) {
        for (int neighbor : neighbors) {
            inDegree[neighbor]++;
        }
    }

    queue<int> q;
    for (auto const& [node, degree] : inDegree) {
        if (degree == 0) {
            q.push(node);
        }
    }

    vector<int> result;
    int count = 0;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        result.push_back(node);
        count++;

        for (int neighbor : graph[node]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    if (count != graph.size()) {
        return {}; // Cycle detected, return empty vector
    } else {
        return result;
    }
}

void topologicalSortDFSUtil(int node, map<int, vector<int>>& graph, vector<bool>& visited, vector<int>& result) {
    visited[node] = true;

    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            topologicalSortDFSUtil(neighbor, graph, visited, result);
        }
    }

    result.push_back(node);
}

vector<int> topologicalSortDFS(map<int, vector<int>>& graph) {
    int numNodes = graph.size();
    vector<bool> visited(numNodes, false);
    vector<int> result;

    for (auto const& [node, neighbors] : graph) {
      if (!visited[node]) {
        topologicalSortDFSUtil(node, graph, visited, result);
      }
    }

    reverse(result.begin(), result.end());
    return result;
}

int main() {
    map<int, vector<int>> graph = {
        {0, {1, 2}},
        {1, {3}},
        {2, {3}},
        {3, {}}
    };

    vector<int> sortedList = topologicalSortKhan(graph);
    cout << "Topological Sort (Khan's): ";
    if (sortedList.empty()) {
        cout << "Cycle detected" << endl;
    } else {
        for (int node : sortedList) {
            cout << node << " ";
        }
        cout << endl;
    }

    sortedList = topologicalSortDFS(graph);
    cout << "Topological Sort (DFS): ";
        for (int node : sortedList) {
            cout << node << " ";
        }
        cout << endl;


    return 0;
}

5. Complexity Analysis

Operation	Time Complexity	Space Complexity	Notes
Khan’s Algorithm	O(V + E)	O(V)	V = Number of vertices, E = Number of edges. Space is dominated by the queue and in-degree map.
DFS Algorithm	O(V + E)	O(V)	V = Number of vertices, E = Number of edges. Space is dominated by the recursion stack and visited set.

Best Case: For both algorithms, the best-case scenario is when the graph is sparse (few edges). The time complexity remains O(V + E).

Average Case: The average case complexity is also O(V + E).

Worst Case: The worst-case scenario is when the graph is dense (many edges). The time complexity remains O(V + E).

6. Pro Tips, Tricks, and Common Pitfalls

• Cycle Detection: Topological sort is only possible on DAGs. If you encounter a cycle, the algorithm will not produce a valid ordering. Khan’s algorithm detects cycles by comparing the number of visited nodes to the total number of nodes. DFS can detect cycles, but requires more careful implementation using three states (unvisited, visiting, visited) to track nodes during the recursive calls.
• Multiple Valid Orderings: For a given DAG, there may be multiple valid topological orderings. The specific ordering produced by an algorithm may depend on the order in which nodes are processed.
• Handling Disconnected Graphs: If the graph is disconnected, you need to iterate through all the nodes and perform topological sort on each connected component separately.
• Starting Nodes: In Khan’s algorithm, ensure that you correctly identify all source nodes (nodes with an in-degree of 0) at the beginning. Missing a source node can lead to an incomplete topological sort.
• Data Structures: Using appropriate data structures (e.g., a queue for Khan’s algorithm, a set for visited nodes) can significantly improve the performance and readability of your code.
• Memory Management (C++): Be mindful of memory management, especially when dealing with large graphs in C++. Avoid memory leaks by properly allocating and deallocating memory.

7. Classic Problem Examples

Example: Course Schedule

Description: There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. Return true if you can finish all courses. Otherwise, return false.

High-Level Approach:

1. Build the Graph: Represent the courses and prerequisites as a directed graph. Each course is a node, and a prerequisite [ai, bi] means there’s a directed edge from bi to ai.
2. Apply Topological Sort: Use either Khan’s algorithm or DFS to perform topological sort on the graph.
3. Check for Cycles: If the graph contains a cycle, it’s impossible to complete all courses. If the topological sort completes successfully, it means there’s no cycle, and it’s possible to finish all courses. In Khan’s algorithm, this is detected if the number of visited nodes is not equal to numCourses. In DFS, a more complex state tracking is needed to correctly identify cycles.
4. Return Result: Return true if the topological sort completes successfully (no cycle detected), and false otherwise.