Topological Sort

Find a linear ordering of vertices in a directed acyclic graph

Language Selection

Choose your preferred programming language

Showing: Python

Problem Statement

Given a directed acyclic graph (DAG) with n vertices labeled from 0 to n-1, find a topological ordering of the vertices. A topological ordering is a linear ordering of vertices such that for every directed edge (u, v), vertex u comes before v in the ordering.

Input:

  • Number of vertices n
  • List of directed edges as [from, to] pairs

Output:

  • Array representing a valid topological ordering
  • Empty array if the graph has a cycle (not a DAG)

Constraints:

  • 1 ≤ n ≤ 10^4
  • 0 ≤ edges.length ≤ min(10^4, n * (n-1))
  • All edges are unique
  • Graph may be disconnected

Examples:

Example 1:

Input: n = 4, edges = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: [3, 2, 1, 0] or [3, 1, 2, 0]
Explanation: Both orderings satisfy the constraints

Example 2:

Input: n = 6, edges = [[5, 2], [5, 0], [4, 0], [4, 1], [2, 3], [3, 1]]
Output: [5, 4, 2, 3, 1, 0] or [4, 5, 2, 3, 1, 0] or [5, 2, 4, 3, 1, 0]

Example 3 (Has Cycle):

Input: n = 3, edges = [[0, 1], [1, 2], [2, 0]]
Output: []
Explanation: Graph has a cycle, no valid topological ordering exists

Solutions

Approach 1: DFS-Based Topological Sort

Use DFS with a stack to collect vertices in reverse topological order.

Algorithm:

  1. Build adjacency list from edges
  2. Use DFS to visit all vertices
  3. After visiting all descendants, push vertex to stack
  4. Pop all elements from stack for topological order
  5. Detect cycles during DFS

Python:

def topologicalSort(n, edges):
    """
    DFS-based topological sort
    Time: O(V + E)
    Space: O(V)
    """
    import sys
    sys.setrecursionlimit(max(sys.getrecursionlimit(), n + 1000))
    
    # Build adjacency list
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
    
    # 0: White, 1: Gray, 2: Black
    color = [0] * n
    stack = []
    has_cycle = False
    
    def dfs(node):
        nonlocal has_cycle
        if color[node] == 1:  # Gray - cycle detected
            has_cycle = True
            return
        if color[node] == 2:  # Black - already processed
            return
        
        color[node] = 1  # Mark as Gray
        
        for neighbor in graph[node]:
            dfs(neighbor)
            if has_cycle:
                return
        
        color[node] = 2  # Mark as Black
        stack.append(node)  # Add to stack after processing all descendants
    
    # Visit all vertices
    for i in range(n):
        if color[i] == 0:
            dfs(i)
            if has_cycle:
                return []
    
    # Reverse stack to get topological order
    return stack[::-1]

def topologicalSortAll(n, edges):
    """
    Find all possible topological orderings (for small graphs)
    Time: O(V! * E) worst case
    Space: O(V)
    """
    import sys
    sys.setrecursionlimit(max(sys.getrecursionlimit(), n + 1000))
    
    graph = [[] for _ in range(n)]
    in_degree = [0] * n
    
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    def backtrack(path, remaining):
        if not remaining:
            results.append(path[:])
            return
        
        for node in list(remaining):
            if in_degree[node] == 0:
                # Choose node
                path.append(node)
                remaining.remove(node)
                
                # Update in-degrees
                for neighbor in graph[node]:
                    in_degree[neighbor] -= 1
                
                # Recurse
                backtrack(path, remaining)
                
                # Backtrack
                for neighbor in graph[node]:
                    in_degree[neighbor] += 1
                remaining.add(node)
                path.pop()
    
    results = []
    backtrack([], set(range(n)))
    return results

Java:

import java.util.*;

class Solution {
    private boolean hasCycle = false;
    
    /**
     * DFS-based topological sort
     * Time: O(V + E)
     * Space: O(V)
     */
    public int[] topologicalSort(int n, int[][] edges) {
        // Build adjacency list
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
        }
        
        // 0: White, 1: Gray, 2: Black
        int[] color = new int[n];
        Stack<Integer> stack = new Stack<>();
        hasCycle = false;
        
        // Visit all vertices
        for (int i = 0; i < n; i++) {
            if (color[i] == 0) {
                dfs(graph, i, color, stack);
                if (hasCycle) {
                    return new int[0];
                }
            }
        }
        
        // Convert stack to array
        int[] result = new int[n];
        int index = 0;
        while (!stack.isEmpty()) {
            result[index++] = stack.pop();
        }
        
        return result;
    }
    
    private void dfs(List<List<Integer>> graph, int node, int[] color, Stack<Integer> stack) {
        if (color[node] == 1) {  // Gray - cycle detected
            hasCycle = true;
            return;
        }
        if (color[node] == 2) {  // Black - already processed
            return;
        }
        
        color[node] = 1;  // Mark as Gray
        
        // Explicit DFS stack of {node, index of next neighbor to visit}
        Deque<int[]> work = new ArrayDeque<>();
        work.push(new int[]{node, 0});
        
        while (!work.isEmpty()) {
            int[] frame = work.peek();
            int current = frame[0];
            List<Integer> neighbors = graph.get(current);
            
            if (frame[1] < neighbors.size()) {
                int neighbor = neighbors.get(frame[1]++);
                if (color[neighbor] == 1) {  // Gray - cycle detected
                    hasCycle = true;
                    return;
                }
                if (color[neighbor] == 0) {
                    color[neighbor] = 1;  // Mark as Gray
                    work.push(new int[]{neighbor, 0});
                }
                // Black neighbors are already processed
            } else {
                work.pop();
                color[current] = 2;  // Mark as Black
                stack.push(current);
            }
        }
    }
    
    /**
     * Find all topological orderings
     * Time: O(V! * E) worst case
     * Space: O(V)
     */
    public List<List<Integer>> topologicalSortAll(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        int[] inDegree = new int[n];
        
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            inDegree[edge[1]]++;
        }
        
        List<List<Integer>> results = new ArrayList<>();
        Set<Integer> remaining = new HashSet<>();
        for (int i = 0; i < n; i++) {
            remaining.add(i);
        }
        
        backtrack(graph, new ArrayList<>(), remaining, inDegree, results);
        return results;
    }
    
    private void backtrack(List<List<Integer>> graph, List<Integer> path, 
                          Set<Integer> remaining, int[] inDegree, List<List<Integer>> results) {
        // Explicit stack of frames instead of recursion, so a chain of 10^4 vertices
        // cannot overflow the call stack. Each frame mirrors one recursive call:
        // the candidates found on entry and the index of the next one to try.
        Deque<List<Integer>> frames = new ArrayDeque<>();
        Deque<int[]> nextIndex = new ArrayDeque<>();
        boolean entering = true;
        
        while (true) {
            if (entering) {
                entering = false;
                if (remaining.isEmpty()) {
                    results.add(new ArrayList<>(path));
                } else {
                    List<Integer> candidates = new ArrayList<>();
                    for (int node : remaining) {
                        if (inDegree[node] == 0) {
                            candidates.add(node);
                        }
                    }
                    frames.push(candidates);
                    nextIndex.push(new int[]{0});
                }
            }
            if (frames.isEmpty()) {
                return;
            }
            
            List<Integer> candidates = frames.peek();
            int[] index = nextIndex.peek();
            
            if (index[0] > 0) {
                // Undo the candidate tried last (backtrack)
                int node = candidates.get(index[0] - 1);
                for (int neighbor : graph.get(node)) {
                    inDegree[neighbor]++;
                }
                remaining.add(node);
                path.remove(path.size() - 1);
            }
            
            if (index[0] < candidates.size()) {
                int node = candidates.get(index[0]++);
                path.add(node);
                remaining.remove(node);
                
                for (int neighbor : graph.get(node)) {
                    inDegree[neighbor]--;
                }
                
                entering = true;  // Descend, as the recursive call did
            } else {
                frames.pop();
                nextIndex.pop();
            }
        }
    }
}

Go:

// topologicalSort - DFS-based topological sort
// Time: O(V + E)
// Space: O(V)
func topologicalSort(n int, edges [][]int) []int {
    // Build adjacency list
    graph := make([][]int, n)
    for _, edge := range edges {
        graph[edge[0]] = append(graph[edge[0]], edge[1])
    }
    
    // 0: White, 1: Gray, 2: Black
    color := make([]int, n)
    stack := []int{}
    hasCycle := false
    
    var dfs func(node int)
    dfs = func(node int) {
        if color[node] == 1 {  // Gray - cycle detected
            hasCycle = true
            return
        }
        if color[node] == 2 {  // Black - already processed
            return
        }
        
        color[node] = 1  // Mark as Gray
        
        for _, neighbor := range graph[node] {
            dfs(neighbor)
            if hasCycle {
                return
            }
        }
        
        color[node] = 2  // Mark as Black
        stack = append(stack, node)
    }
    
    // Visit all vertices
    for i := 0; i < n; i++ {
        if color[i] == 0 {
            dfs(i)
            if hasCycle {
                return []int{}
            }
        }
    }
    
    // Reverse stack
    result := make([]int, n)
    for i := 0; i < n; i++ {
        result[i] = stack[n-1-i]
    }
    
    return result
}

// topologicalSortAll - Find all topological orderings
// Time: O(V! * E) worst case
// Space: O(V)
func topologicalSortAll(n int, edges [][]int) [][]int {
    graph := make([][]int, n)
    inDegree := make([]int, n)
    
    for _, edge := range edges {
        graph[edge[0]] = append(graph[edge[0]], edge[1])
        inDegree[edge[1]]++
    }
    
    results := [][]int{}
    
    var backtrack func(path []int, remaining map[int]bool)
    backtrack = func(path []int, remaining map[int]bool) {
        if len(remaining) == 0 {
            result := make([]int, len(path))
            copy(result, path)
            results = append(results, result)
            return
        }
        
        // Snapshot the keys first: the loop deletes and re-adds entries of remaining
        // (also inside the recursion), and Go leaves map iteration unspecified then
        nodes := make([]int, 0, len(remaining))
        for node := range remaining {
            nodes = append(nodes, node)
        }

        for _, node := range nodes {
            if inDegree[node] == 0 {
                // Choose node
                path = append(path, node)
                delete(remaining, node)
                
                // Update in-degrees
                for _, neighbor := range graph[node] {
                    inDegree[neighbor]--
                }
                
                // Recurse
                backtrack(path, remaining)
                
                // Backtrack
                for _, neighbor := range graph[node] {
                    inDegree[neighbor]++
                }
                remaining[node] = true
                path = path[:len(path)-1]
            }
        }
    }
    
    remaining := make(map[int]bool)
    for i := 0; i < n; i++ {
        remaining[i] = true
    }
    
    backtrack([]int{}, remaining)
    return results
}

JavaScript:

/**
 * DFS-based topological sort
 * Time: O(V + E)
 * Space: O(V)
 */
function topologicalSort(n, edges) {
    // Build adjacency list
    const graph = Array(n).fill().map(() => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
    }
    
    // 0: White, 1: Gray, 2: Black
    const color = new Array(n).fill(0);
    const stack = [];
    let hasCycle = false;
    
    function dfs(node) {
        if (color[node] === 1) {  // Gray - cycle detected
            hasCycle = true;
            return;
        }
        if (color[node] === 2) {  // Black - already processed
            return;
        }
        
        color[node] = 1;  // Mark as Gray
        
        // Explicit DFS stack of [node, index of next neighbor to visit]
        const work = [[node, 0]];
        
        while (work.length > 0) {
            const frame = work[work.length - 1];
            const current = frame[0];
            
            if (frame[1] < graph[current].length) {
                const neighbor = graph[current][frame[1]++];
                if (color[neighbor] === 1) {  // Gray - cycle detected
                    hasCycle = true;
                    return;
                }
                if (color[neighbor] === 0) {
                    color[neighbor] = 1;  // Mark as Gray
                    work.push([neighbor, 0]);
                }
                // Black neighbors are already processed
            } else {
                work.pop();
                color[current] = 2;  // Mark as Black
                stack.push(current);
            }
        }
    }
    
    // Visit all vertices
    for (let i = 0; i < n; i++) {
        if (color[i] === 0) {
            dfs(i);
            if (hasCycle) {
                return [];
            }
        }
    }
    
    // Reverse stack
    return stack.reverse();
}

/**
 * Find all topological orderings
 * Time: O(V! * E) worst case
 * Space: O(V)
 */
function topologicalSortAll(n, edges) {
    const graph = Array(n).fill().map(() => []);
    const inDegree = new Array(n).fill(0);
    
    for (const [u, v] of edges) {
        graph[u].push(v);
        inDegree[v]++;
    }
    
    const results = [];
    
    function backtrack(path, remaining) {
        // Explicit stack of frames instead of recursion, so a chain of 10^4 vertices
        // cannot overflow the call stack. Each frame mirrors one recursive call:
        // the nodes with in-degree 0 on entry (in the same Set order as before),
        // the index of the next one to try, and the node currently chosen.
        const frames = [];
        let entering = true;
        
        while (true) {
            if (entering) {
                entering = false;
                if (remaining.size === 0) {
                    results.push([...path]);
                } else {
                    const candidates = [...remaining].filter(node => inDegree[node] === 0);
                    frames.push({ candidates, next: 0, chosen: null });
                }
            }
            if (frames.length === 0) {
                return;
            }
            
            const frame = frames[frames.length - 1];
            
            if (frame.chosen !== null) {
                // Backtrack
                const node = frame.chosen;
                for (const neighbor of graph[node]) {
                    inDegree[neighbor]++;
                }
                remaining.add(node);
                path.pop();
                frame.chosen = null;
            }
            
            if (frame.next < frame.candidates.length) {
                // Choose node
                const node = frame.candidates[frame.next++];
                path.push(node);
                remaining.delete(node);
                
                // Update in-degrees
                for (const neighbor of graph[node]) {
                    inDegree[neighbor]--;
                }
                
                frame.chosen = node;
                entering = true;  // Recurse
            } else {
                frames.pop();
            }
        }
    }
    
    const remaining = new Set();
    for (let i = 0; i < n; i++) {
        remaining.add(i);
    }
    
    backtrack([], remaining);
    return results;
}

C#:

using System;
using System.Collections.Generic;

public class Solution {
    private bool hasCycle = false;
    
    /// <summary>
    /// DFS-based topological sort
    /// Time: O(V + E)
    /// Space: O(V)
    /// </summary>
    public int[] TopologicalSort(int n, int[][] edges) {
        // Build adjacency list
        List<int>[] graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
        }
        
        // 0: White, 1: Gray, 2: Black
        int[] color = new int[n];
        Stack<int> stack = new Stack<int>();
        hasCycle = false;
        
        // Visit all vertices
        for (int i = 0; i < n; i++) {
            if (color[i] == 0) {
                Dfs(graph, i, color, stack);
                if (hasCycle) {
                    return new int[0];
                }
            }
        }
        
        // Convert stack to array
        int[] result = new int[n];
        int index = 0;
        while (stack.Count > 0) {
            result[index++] = stack.Pop();
        }
        
        return result;
    }
    
    private void Dfs(List<int>[] graph, int node, int[] color, Stack<int> stack) {
        // Explicit stack instead of recursion: (vertex, next neighbor index),
        // where index -1 means the vertex is being entered
        Stack<(int vertex, int next)> work = new Stack<(int vertex, int next)>();
        work.Push((node, -1));
        
        while (work.Count > 0) {
            var (u, i) = work.Pop();
            
            if (i == -1) {
                if (color[u] == 1) {  // Gray - cycle detected
                    hasCycle = true;
                    return;
                }
                if (color[u] == 2) {  // Black - already processed
                    continue;
                }
                
                color[u] = 1;  // Mark as Gray
                work.Push((u, 0));
            } else if (i < graph[u].Count) {
                work.Push((u, i + 1));
                work.Push((graph[u][i], -1));
            } else {
                color[u] = 2;  // Mark as Black
                stack.Push(u);
            }
        }
    }
    
    /// <summary>
    /// Find all topological orderings
    /// Time: O(V! * E) worst case
    /// Space: O(V)
    /// </summary>
    public List<List<int>> TopologicalSortAll(int n, int[][] edges) {
        List<int>[] graph = new List<int>[n];
        int[] inDegree = new int[n];
        
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            inDegree[edge[1]]++;
        }
        
        List<List<int>> results = new List<List<int>>();
        HashSet<int> remaining = new HashSet<int>();
        for (int i = 0; i < n; i++) {
            remaining.Add(i);
        }
        
        Backtrack(graph, new List<int>(), remaining, inDegree, results);
        return results;
    }
    
    private void Backtrack(List<int>[] graph, List<int> path, HashSet<int> remaining,
                          int[] inDegree, List<List<int>> results) {
        // Explicit stack of frames instead of recursion: each frame holds the candidates
        // of one level and the index of the next candidate to try
        List<List<int>> candidateStack = new List<List<int>>();
        List<int> nextStack = new List<int>();
        bool entering = true;
        
        while (true) {
            if (entering) {
                entering = false;
                if (remaining.Count == 0) {
                    results.Add(new List<int>(path));
                } else {
                    List<int> candidates = new List<int>();
                    foreach (int node in remaining) {
                        if (inDegree[node] == 0) {
                            candidates.Add(node);
                        }
                    }
                    candidateStack.Add(candidates);
                    nextStack.Add(0);
                }
            }
            
            if (candidateStack.Count == 0) break;
            
            int top = candidateStack.Count - 1;
            List<int> level = candidateStack[top];
            int i = nextStack[top];
            
            // Undo the candidate whose subtree just finished
            if (i > 0) {
                int prev = level[i - 1];
                foreach (int neighbor in graph[prev]) {
                    inDegree[neighbor]++;
                }
                remaining.Add(prev);
                path.RemoveAt(path.Count - 1);
            }
            
            if (i < level.Count) {
                int node = level[i];
                path.Add(node);
                remaining.Remove(node);
                
                foreach (int neighbor in graph[node]) {
                    inDegree[neighbor]--;
                }
                
                nextStack[top] = i + 1;
                entering = true;
            } else {
                candidateStack.RemoveAt(top);
                nextStack.RemoveAt(top);
            }
        }
    }
}

Approach 2: Kahn’s Algorithm (BFS-Based)

Use BFS with in-degree tracking to find topological ordering.

Python:

from collections import deque

def topologicalSortKahn(n, edges):
    """
    Kahn's algorithm for topological sort
    Time: O(V + E)
    Space: O(V)
    """
    graph = [[] for _ in range(n)]
    in_degree = [0] * n
    
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    # Start with vertices having no incoming edges
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        # Remove this vertex from graph by reducing in-degrees
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # If all vertices are included, we have a valid topological sort
    return result if len(result) == n else []

Java:

public int[] topologicalSortKahn(int n, int[][] edges) {
    /**
     * Kahn's algorithm for topological sort
     * Time: O(V + E)
     * Space: O(V)
     */
    List<List<Integer>> graph = new ArrayList<>();
    int[] inDegree = new int[n];
    
    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }
    
    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
        inDegree[edge[1]]++;
    }
    
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }
    
    int[] result = new int[n];
    int index = 0;
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        result[index++] = node;
        
        for (int neighbor : graph.get(node)) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                queue.offer(neighbor);
            }
        }
    }
    
    return index == n ? result : new int[0];
}

Go:

// topologicalSortKahn - Kahn's algorithm for topological sort
// Time: O(V + E)
// Space: O(V)
func topologicalSortKahn(n int, edges [][]int) []int {
    graph := make([][]int, n)
    inDegree := make([]int, n)
    
    for _, edge := range edges {
        graph[edge[0]] = append(graph[edge[0]], edge[1])
        inDegree[edge[1]]++
    }
    
    queue := []int{}
    for i := 0; i < n; i++ {
        if inDegree[i] == 0 {
            queue = append(queue, i)
        }
    }
    
    result := []int{}
    
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        result = append(result, node)
        
        for _, neighbor := range graph[node] {
            inDegree[neighbor]--
            if inDegree[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
        }
    }
    
    if len(result) == n {
        return result
    }
    return []int{}
}

JavaScript:

/**
 * Kahn's algorithm for topological sort
 * Time: O(V + E)
 * Space: O(V)
 */
function topologicalSortKahn(n, edges) {
    const graph = Array(n).fill().map(() => []);
    const inDegree = new Array(n).fill(0);
    
    for (const [u, v] of edges) {
        graph[u].push(v);
        inDegree[v]++;
    }
    
    const queue = [];
    for (let i = 0; i < n; 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 graph[node]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] === 0) {
                queue.push(neighbor);
            }
        }
    }
    
    return result.length === n ? result : [];
}

C#:

public int[] TopologicalSortKahn(int n, int[][] edges) {
    /// <summary>
    /// Kahn's algorithm for topological sort
    /// Time: O(V + E)
    /// Space: O(V)
    /// </summary>
    List<int>[] graph = new List<int>[n];
    int[] inDegree = new int[n];
    
    for (int i = 0; i < n; i++) {
        graph[i] = new List<int>();
    }
    
    foreach (var edge in edges) {
        graph[edge[0]].Add(edge[1]);
        inDegree[edge[1]]++;
    }
    
    Queue<int> queue = new Queue<int>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            queue.Enqueue(i);
        }
    }
    
    int[] result = new int[n];
    int index = 0;
    
    while (queue.Count > 0) {
        int node = queue.Dequeue();
        result[index++] = node;
        
        foreach (int neighbor in graph[node]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                queue.Enqueue(neighbor);
            }
        }
    }
    
    return index == n ? result : new int[0];
}

Key Insights

  1. DAG Requirement: Topological sort only exists for directed acyclic graphs
  2. Multiple Valid Orders: Many valid topological orderings may exist
  3. DFS vs BFS: DFS uses recursion stack, BFS uses in-degree queue
  4. Cycle Detection: Both approaches naturally detect cycles

Edge Cases

  1. Empty graph: Return vertices in any order
  2. No edges: Any permutation is valid
  3. Cycle present: Return empty array
  4. Disconnected graph: Process all components
  5. Self-loop: Immediate cycle detection

Common Mistakes

  1. Forgetting cycle detection: Not handling graphs with cycles
  2. Wrong order in DFS: Adding to result before processing descendants
  3. In-degree initialization: Missing edges when building graph
  4. Not handling disconnected components: Missing isolated vertices

Follow-up Questions

  1. Lexicographically smallest: Find the lexicographically smallest topological order
  2. Count all orderings: How many valid topological orderings exist?
  3. Parallel scheduling: Maximum number of vertices that can be processed in parallel
  4. Critical path: Find the longest path in the DAG
  5. Minimum edges to add: Make the graph strongly connected with minimum edges