Topological Sort (DAGs)

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

Topological sorting is only possible if the graph has no cycles.

What Is a DAG?

A Directed Acyclic Graph (DAG) is a directed graph that contains no cycles.

Example:

A → B → D
 \      ↑
  → C ---

This graph is directed and acyclic, so a topological ordering exists.

Why Topological Sort Matters

Topological sort is used in problems involving dependencies, such as:

• Task scheduling
• Build systems and compilers
• Course prerequisites
• Package dependency resolution
• Workflow execution

It answers the question: “In what order should tasks be performed?”

Key Property

If a graph contains a cycle:

A → B → C → A

Then no valid topological ordering exists.

This is why cycle detection is often performed before topological sorting.

Two Common Approaches

Topological sort can be implemented using:

1. DFS-based approach
2. Kahn’s Algorithm (BFS-based, in-degree method)

Both run in linear time.

Approach 1: DFS-Based Topological Sort

Idea

1. Perform DFS on each unvisited node
2. After visiting all neighbors, add the node to a stack
3. Reverse the stack to get the topological order

This works because a node is added after all its dependencies.

Rust Implementation (DFS-Based)

use std::collections::{HashMap, HashSet};

type Graph = HashMap<i32, Vec<i32>>;

pub fn topological_sort_dfs(graph: &Graph) -> Option<Vec<i32>> {
    let mut visited = HashSet::new();
    let mut visiting = HashSet::new();
    let mut stack = Vec::new();

    for &node in graph.keys() {
        if !visited.contains(&node) {
            if !dfs(graph, node, &mut visited, &mut visiting, &mut stack) {
                return None; // cycle detected
            }
        }
    }

    stack.reverse();
    Some(stack)
}

fn dfs(
    graph: &Graph,
    node: i32,
    visited: &mut HashSet<i32>,
    visiting: &mut HashSet<i32>,
    stack: &mut Vec<i32>,
) -> bool {
    if visiting.contains(&node) {
        return false; // cycle
    }

    if visited.contains(&node) {
        return true;
    }

    visiting.insert(node);

    if let Some(neighbors) = graph.get(&node) {
        for &neighbor in neighbors {
            if !dfs(graph, neighbor, visited, visiting, stack) {
                return false;
            }
        }
    }

    visiting.remove(&node);
    visited.insert(node);
    stack.push(node);

    true
}

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

Idea

1. Compute in-degree (number of incoming edges) for each vertex

2. Add all vertices with in-degree 0 to a queue

3. Repeatedly:

   • Remove a vertex from the queue
   • Add it to the ordering
   • Reduce in-degree of its neighbors

4. If all vertices are processed → valid DAG

5. Otherwise → graph contains a cycle

Example Usage

fn main() {
    let mut graph: Graph = HashMap::new();

    graph.insert(1, vec![2, 3]);
    graph.insert(2, vec![4]);
    graph.insert(3, vec![4]);
    graph.insert(4, vec![]);

    match topological_sort_dfs(&graph) {
        Some(order) => println!("Topological order: {:?}", order),
        None => println!("Graph contains a cycle"),
    }
}

Rust Implementation (Kahn’s Algorithm)

use std::collections::{HashMap, VecDeque};

type Graph = HashMap<i32, Vec<i32>>;

pub fn topological_sort_kahn(graph: &Graph) -> Option<Vec<i32>> {
    let mut in_degree = HashMap::new();

    // Initialize in-degrees
    for &node in graph.keys() {
        in_degree.entry(node).or_insert(0);
        for &neighbor in &graph[&node] {
            *in_degree.entry(neighbor).or_insert(0) += 1;
        }
    }

    let mut queue = VecDeque::new();
    for (&node, &deg) in &in_degree {
        if deg == 0 {
            queue.push_back(node);
        }
    }

    let mut order = Vec::new();

    while let Some(node) = queue.pop_front() {
        order.push(node);

        if let Some(neighbors) = graph.get(&node) {
            for &neighbor in neighbors {
                let deg = in_degree.get_mut(&neighbor).unwrap();
                *deg -= 1;
                if *deg == 0 {
                    queue.push_back(neighbor);
                }
            }
        }
    }

    if order.len() == in_degree.len() {
        Some(order)
    } else {
        None // cycle detected
    }
}

Example Usage

fn main() {
    let mut graph: Graph = HashMap::new();

    graph.insert(1, vec![2, 3]);
    graph.insert(2, vec![4]);
    graph.insert(3, vec![4]);
    graph.insert(4, vec![]);

    let order = topological_sort_kahn(&graph);

    match order {
        Some(o) => println!("Topological order: {:?}", o),
        None => println!("Graph contains a cycle"),
    }
}

Possible output:

Topological order: [1, 2, 3, 4]

(Other valid orders may exist.)

Time and Space Complexity

Time Complexity

Space Complexity

DFS vs Kahn’s Algorithm

Summary

• Topological sort works only on DAGs
• Multiple valid orderings may exist
• DFS uses postorder stacking
• Kahn’s algorithm uses in-degree tracking
• Both run in linear time

Playground Links

Rust - DFS-Based Topological Sort

Rust - Topological Sort - Kahn’s Algorithm