Topological Sort

Generated on 2025-07-10 01:57:35 Algorithm Cheatsheet for Technical Interviews

---

Topological Sort Cheatsheet

1. Quick Overview

• What is it? 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’s a way to sequence tasks or dependencies.

• When to use it?

  • Scheduling tasks with dependencies.
  • Dependency resolution in software packages.
  • Course scheduling.
  • Detecting cycles in a directed graph (if a topological sort is impossible, a cycle exists).

2. Time & Space Complexity

Algorithm	Time Complexity	Space Complexity
DFS-based	O(V + E)	O(V + E)
Kahn’s Algorithm (BFS)	O(V + E)	O(V + E)

• V: Number of vertices
• E: Number of edges

3. Implementation

Here are implementations using DFS and Kahn’s Algorithm in Python, Java, and C++.

Python (DFS):

from collections import defaultdict

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

    Args:
        graph (dict): Adjacency list representation of the graph
                      (e.g., {0: [1, 2], 1: [3], 2: [3], 3: []})

    Returns:
        list: A topological ordering of the vertices, or None if a cycle exists.
    """
    visited = set()
    stack = []  # Store the topological order

    def dfs(node):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor in visited:
                return False  # Cycle detected
            if neighbor not in visited:
                if not dfs(neighbor):
                    return False
        stack.append(node)
        return True

    for node in graph:
        if node not in visited:
            if not dfs(node):
                return None  # Cycle detected

    return stack[::-1]  # Reverse the stack to get the correct order

# Example usage:
graph = {0: [1, 2], 1: [3], 2: [3], 3: []}
result = topological_sort_dfs(graph)
print(f"Topological Sort (DFS): {result}") # Output: [0, 2, 1, 3]

Python (Kahn’s Algorithm - BFS):

from collections import defaultdict, deque

def topological_sort_kahn(graph):
    """
    Topological Sort using Kahn's Algorithm (BFS).

    Args:
        graph (dict): Adjacency list representation of the graph
                      (e.g., {0: [1, 2], 1: [3], 2: [3], 3: []})

    Returns:
        list: A topological ordering of the vertices, or None if a cycle exists.
    """

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

    queue = deque([node for node in graph if in_degree[node] == 0])
    result = []
    count = 0 # Track number of elements added. if not equal to total vertices, cycle exists.

    while queue:
        node = queue.popleft()
        result.append(node)
        count += 1

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

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


# Example usage:
graph = {0: [1, 2], 1: [3], 2: [3], 3: []}
result = topological_sort_kahn(graph)
print(f"Topological Sort (Kahn's): {result}") # Output: [0, 1, 2, 3]

Java (DFS):

import java.util.*;

class TopologicalSortDFS {

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

        for (Integer node : graph.keySet()) {
            if (!visited.contains(node)) {
                if (!dfs(graph, node, visited, stack)) {
                    return null; // Cycle detected
                }
            }
        }

        while (!stack.isEmpty()) {
            result.add(stack.pop());
        }

        return result;
    }

    private static boolean dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited, Stack<Integer> stack) {
        visited.add(node);

        List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
        for (int neighbor : neighbors) {
            if (visited.contains(neighbor)) {
                return false; // Cycle detected
            }
            if (!visited.contains(neighbor)) {
                if (!dfs(graph, neighbor, visited, stack)) {
                    return false;
                }
            }
        }

        stack.push(node);
        return true;
    }

    public static void main(String[] args) {
        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> result = topologicalSort(graph);
        System.out.println("Topological Sort (DFS): " + result); // Output: [0, 2, 1, 3]
    }
}

Java (Kahn’s Algorithm - BFS):

import java.util.*;

class TopologicalSortKahn {

    public static List<Integer> topologicalSort(Map<Integer, List<Integer>> graph) {
        Map<Integer, Integer> inDegree = new HashMap<>();
        for (Integer node : graph.keySet()) {
            inDegree.put(node, 0);
        }
        for (Integer node : graph.keySet()) {
            for (Integer neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                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()) {
            int node = queue.poll();
            result.add(node);
            count++;

            for (Integer neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                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 void main(String[] args) {
        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> result = topologicalSort(graph);
        System.out.println("Topological Sort (Kahn's): " + result); // Output: [0, 1, 2, 3]
    }
}

C++ (DFS):

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>
#include <unordered_set>

using namespace std;

vector<int> topologicalSortDFS(unordered_map<int, vector<int>>& graph) {
    unordered_set<int> visited;
    stack<int> s;
    vector<int> result;

    function<bool(int)> dfs = [&](int node) {
        visited.insert(node);
        for (int neighbor : graph[node]) {
            if (visited.count(neighbor)) return false; // Cycle
            if (!visited.count(neighbor)) {
                if (!dfs(neighbor)) return false;
            }
        }
        s.push(node);
        return true;
    };

    for (auto const& [node, neighbors] : graph) {
        if (!visited.count(node)) {
            if (!dfs(node)) return {}; // Cycle found. Return empty vector
        }
    }

    while (!s.empty()) {
        result.push_back(s.top());
        s.pop();
    }

    return result;
}

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

    vector<int> result = topologicalSortDFS(graph);

    cout << "Topological Sort (DFS): ";
    for (int node : result) {
        cout << node << " ";
    }
    cout << endl; // Output: Topological Sort (DFS): 0 2 1 3
    return 0;
}

C++ (Kahn’s Algorithm - BFS):

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

vector<int> topologicalSortKahn(unordered_map<int, vector<int>>& graph) {
    unordered_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
    }

    return result;
}

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

    vector<int> result = topologicalSortKahn(graph);

    cout << "Topological Sort (Kahn's): ";
    for (int node : result) {
        cout << node << " ";
    }
    cout << endl; // Output: Topological Sort (Kahn's): 0 1 2 3
    return 0;
}

4. Common Patterns

• Dependency Resolution: Solving build order problems.
• Course Scheduling: Finding a valid order to take courses with prerequisites.
• Compiler Design: Ordering compilation steps.
• Data Serialization: Ensuring objects are serialized in the correct order based on dependencies.
• Cycle Detection: If a topological sort is impossible (returns null or empty list), the graph contains a cycle.

5. Pro Tips

• DFS vs. Kahn’s Algorithm:
  • DFS is recursive and might be easier to understand conceptually.
  • Kahn’s Algorithm (BFS) is iterative and can be more memory-efficient, especially for large graphs.
• Cycle Detection is Key: Always check for cycles when dealing with dependency graphs. If a cycle exists, a topological sort is not possible.
• Graph Representation: Use adjacency lists for efficient neighbor lookups.
• Early Exit: If a cycle is detected during DFS, terminate the search early to save time.
• Handling Disconnected Graphs: Make sure to iterate through all nodes in the graph to ensure all connected components are processed.

6. Practice Problems

1. Course Schedule II (LeetCode 210): Given the number of courses and a list of prerequisites, return the ordering of courses you should take to finish all courses. Return an empty array if it is impossible to finish all courses.
2. Alien Dictionary (LeetCode 269): Given a sorted list of words in an alien language, derive the order of the letters in the alphabet.
3. Task Scheduler (LeetCode 621): Although not a direct topological sort, understanding dependencies between tasks and scheduling them efficiently is relevant.

7. Templates

Here are code templates for each language that you can quickly copy and paste and modify.

C++ Template

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>

using namespace std;

// DFS based topological sort
vector<int> topologicalSortDFS(unordered_map<int, vector<int>>& graph) {
    unordered_set<int> visited;
    stack<int> s;
    vector<int> result;

    function<bool(int)> dfs = [&](int node) {
        visited.insert(node);
        for (int neighbor : graph[node]) {
            if (visited.count(neighbor)) return false; // Cycle
            if (!visited.count(neighbor)) {
                if (!dfs(neighbor)) return false;
            }
        }
        s.push(node);
        return true;
    };

    for (auto const& [node, neighbors] : graph) {
        if (!visited.count(node)) {
            if (!dfs(node)) return {}; // Cycle found. Return empty vector
        }
    }

    while (!s.empty()) {
        result.push_back(s.top());
        s.pop();
    }

    return result;
}

// Kahn's Algorithm (BFS) based topological sort
vector<int> topologicalSortKahn(unordered_map<int, vector<int>>& graph) {
    unordered_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
    }

    return result;
}


int main() {
    // Example usage
    unordered_map<int, vector<int>> graph = {
        {0, {1, 2}},
        {1, {3}},
        {2, {3}},
        {3, {}}
    };

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

    vector<int> resultKahn = topologicalSortKahn(graph);
    cout << "Topological Sort (Kahn's): ";
    for (int node : resultKahn) {
        cout << node << " ";
    }
    cout << endl;

    return 0;
}

Python Template

from collections import defaultdict, deque

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

    Args:
        graph (dict): Adjacency list representation of the graph
                      (e.g., {0: [1, 2], 1: [3], 2: [3], 3: []})

    Returns:
        list: A topological ordering of the vertices, or None if a cycle exists.
    """
    visited = set()
    stack = []  # Store the topological order

    def dfs(node):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor in visited:
                return False  # Cycle detected
            if neighbor not in visited:
                if not dfs(neighbor):
                    return False
        stack.append(node)
        return True

    for node in graph:
        if node not in visited:
            if not dfs(node):
                return None  # Cycle detected

    return stack[::-1]  # Reverse the stack to get the correct order

def topological_sort_kahn(graph):
    """
    Topological Sort using Kahn's Algorithm (BFS).

    Args:
        graph (dict): Adjacency list representation of the graph
                      (e.g., {0: [1, 2], 1: [3], 2: [3], 3: []})

    Returns:
        list: A topological ordering of the vertices, or None if a cycle exists.
    """

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

    queue = deque([node for node in graph if in_degree[node] == 0])
    result = []
    count = 0 # Track number of elements added. if not equal to total vertices, cycle exists.

    while queue:
        node = queue.popleft()
        result.append(node)
        count += 1

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

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

# Example usage:
if __name__ == "__main__":
    graph = {0: [1, 2], 1: [3], 2: [3], 3: []}

    result_dfs = topological_sort_dfs(graph)
    print(f"Topological Sort (DFS): {result_dfs}")

    result_kahn = topological_sort_kahn(graph)
    print(f"Topological Sort (Kahn's): {result_kahn}")

Java Template

import java.util.*;

class TopologicalSort {

    // DFS based topological sort
    public static List<Integer> topologicalSortDFS(Map<Integer, List<Integer>> graph) {
        Set<Integer> visited = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        List<Integer> result = new ArrayList<>();

        for (Integer node : graph.keySet()) {
            if (!visited.contains(node)) {
                if (!dfs(graph, node, visited, stack)) {
                    return null; // Cycle detected
                }
            }
        }

        while (!stack.isEmpty()) {
            result.add(stack.pop());
        }

        return result;
    }

    private static boolean dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited, Stack<Integer> stack) {
        visited.add(node);

        List<Integer> neighbors = graph.getOrDefault(node, new ArrayList<>());
        for (int neighbor : neighbors) {
            if (visited.contains(neighbor)) {
                return false; // Cycle detected
            }
            if (!visited.contains(neighbor)) {
                if (!dfs(graph, neighbor, visited, stack)) {
                    return false;
                }
            }
        }

        stack.push(node);
        return true;
    }

    // Kahn's Algorithm (BFS) based topological sort
    public static List<Integer> topologicalSortKahn(Map<Integer, List<Integer>> graph) {
        Map<Integer, Integer> inDegree = new HashMap<>();
        for (Integer node : graph.keySet()) {
            inDegree.put(node, 0);
        }
        for (Integer node : graph.keySet()) {
            for (Integer neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                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()) {
            int node = queue.poll();
            result.add(node);
            count++;

            for (Integer neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                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 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> resultDFS = topologicalSortDFS(graph);
        System.out.println("Topological Sort (DFS): " + resultDFS);

        List<Integer> resultKahn = topologicalSortKahn(graph);
        System.out.println("Topological Sort (Kahn's): " + resultKahn);
    }
}