Data Structures and Algorithms in C (DSA)

📘 Chapter: Topological Sort (Kahn’s & DFS)

Imagine you have a list of tasks, and some tasks must be completed before others. How would you determine a valid order to perform all tasks? This is precisely what Topological Sort solves! It's a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge from vertex `u` to vertex `v`, `u` comes before `v` in the ordering. Crucially, a topological sort is only possible on a DAG; if the graph contains a cycle, no such linear ordering can exist.

🤔 What is a Directed Acyclic Graph (DAG)?

A Directed Acyclic Graph (DAG) is a directed graph that contains no cycles. This "acyclic" property is fundamental to topological sort, as a cycle would imply an impossible dependency (e.g., Task A depends on B, B depends on C, and C depends on A – a never-ending loop).

• Examples of DAGs: Course prerequisites, task scheduling, compilation dependencies, version control history.
• Examples of Non-DAGs: Road networks (can have cycles), social networks with mutual friendships (can imply cycles depending on definition).

📚 1. Kahn's Algorithm (BFS-based Topological Sort)

Kahn's algorithm is an iterative, BFS-like approach that builds the topological order by repeatedly finding nodes with no incoming edges (an in-degree of zero). These are the tasks that can be started first.

Kahn's Algorithm Steps:

1. Calculate the in-degree (number of incoming edges) for every vertex in the graph.
2. Initialize a queue and add all vertices with an in-degree of 0 to it. These are the starting points.
3. Initialize an empty list for the topological order and a `count` of visited nodes.
4. While the queue is not empty:
   • Dequeue a vertex `u`. Add `u` to the topological order list and increment `count`.
   • For each neighbor `v` of `u` (i.e., for every edge `(u, v)`):
     • Decrement the in-degree of `v`.
     • If the in-degree of `v` becomes 0, enqueue `v`.
5. After the loop, if `count` is not equal to the total number of vertices `V`, it means a cycle exists in the graph, and a topological sort is not possible.

// Conceptual C++ for Kahn's Algorithm
vector<int> topological_sort_kahn(int V, const vector<vector<int>>& adj) {
    vector<int> in_degree(V, 0);
    for (int i = 0; i < V; ++i) {
        for (int neighbor : adj[i]) {
            in_degree[neighbor]++;
        }
    }

    queue<int> q;
    for (int i = 0; i < V; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    vector<int> result;
    int count = 0;

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

        for (int v : adj[u]) {
            in_degree[v]--;
            if (in_degree[v] == 0) {
                q.push(v);
            }
        }
    }

    if (count != V) {
        // Graph has a cycle, topological sort not possible
        return {}; // Or throw an error
    }
    return result;
}
  

Time Complexity: $O(V + E)$ (similar to BFS, as each vertex and edge is processed constant number of times).
Space Complexity: $O(V)$ for the in-degree array and queue.

🌳 2. DFS-based Topological Sort

The DFS-based approach leverages the nature of Depth-First Search. When performing a DFS, a node is added to the topological sort list only after all its dependent nodes (i.e., all nodes reachable from it) have been processed and added. This is typically done by adding nodes to a stack or list *after* visiting all their children during the DFS recursion.

DFS-based Algorithm Steps:

1. Maintain a `visited` array (or set) to track visited nodes. Also, keep a `recursionStack` (or `onStack` array) to detect cycles.
2. Initialize an empty `stack` (or list) to store the topological order.
3. For each vertex `u` from `0` to `V-1`:
   • If `u` has not been visited, perform a DFS traversal starting from `u`.
4. During the DFS `dfs(u)`:
   • Mark `u` as visited and add it to the `recursionStack`.
   • For each neighbor `v` of `u`:
     • If `v` is not visited, recursively call `dfs(v)`. If the recursive call indicates a cycle, propagate it.
     • If `v` is already in the `recursionStack`, a cycle is detected. Return false (or throw error).
   • After all neighbors of `u` are processed, remove `u` from `recursionStack` and push `u` onto the topological `stack`.
5. The topological sort is obtained by popping elements from the `stack`.

// Conceptual C++ for DFS-based Topological Sort
// visited: 0 = unvisited, 1 = visiting (in recursion stack), 2 = visited (finished)
bool dfs_topo_util(int u, const vector<vector<int>>& adj, vector<int>& visited, stack<int>& st) {
    visited[u] = 1; // Mark as visiting (in recursion stack)

    for (int v : adj[u]) {
        if (visited[v] == 1) { // Cycle detected (back-edge)
            return false;
        }
        if (visited[v] == 0) { // Not visited
            if (!dfs_topo_util(v, adj, visited, st)) {
                return false; // Propagate cycle detection
            }
        }
    }
    visited[u] = 2; // Mark as visited (finished processing descendants)
    st.push(u); // Push to stack after all descendants are processed
    return true;
}

vector<int> topological_sort_dfs(int V, const vector<vector<int>>& adj) {
    vector<int> visited(V, 0); // 0: unvisited, 1: visiting, 2: visited
    stack<int> st;
    vector<int> result;

    for (int i = 0; i < V; ++i) {
        if (visited[i] == 0) {
            if (!dfs_topo_util(i, adj, visited, st)) {
                // Cycle detected
                return {}; // Or throw error
            }
        }
    }

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

Time Complexity: $O(V + E)$ (standard DFS traversal).
Space Complexity: $O(V)$ for the recursion stack and visited array.

🔄 Cycle Detection in Topological Sort

Both algorithms can be used to detect cycles in a directed graph:

• Kahn's Algorithm: If, after the algorithm finishes, the number of vertices added to the topological sort list is less than the total number of vertices ($V$), it implies that the remaining vertices are part of a cycle (they never reached in-degree 0).
• DFS-based Algorithm: During DFS, if you encounter a vertex that is already in the current recursion stack (i.e., it's "visiting" but not yet "visited" in terms of its subtree being fully explored), you've found a back-edge, which indicates a cycle.

📌 Real-Life Example (UdaanPath)

Topological Sort is an extremely practical algorithm for ordering dependent tasks. On a platform like UdaanPath, it can be directly applied in several scenarios:

• Course & Module Prerequisite Ordering: This is the quintessential example. If Course A is a prerequisite for Course B, and Course B for C, a topological sort determines a valid sequence in which a student can take these courses (e.g., A -> B -> C). It can also flag if a curriculum has impossible circular dependencies.
• Learning Path Generation: For personalized learning paths, where certain skills or topics build upon others, topological sort can arrange them in an optimal learning sequence for a user.
• Assignment/Project Task Scheduling: If a complex project is broken down into tasks with dependencies (e.g., "design database" before "implement backend"), topological sort provides a valid order for completing these tasks, useful for project management tools.
• Content Release Sequencing: If certain premium content or features are unlocked after others, a topological sort can define the unlock order to ensure dependencies are met.
• Build Systems (Internal): In a software development environment like UdaanPath's backend, if different modules or microservices need to be compiled or deployed in a specific order due to dependencies, a topological sort dictates that order.

✅ Summary: Ordering in a Directed World

• Topological Sort provides a linear ordering of vertices in a Directed Acyclic Graph (DAG).
• For every directed edge `(u, v)`, `u` always appears before `v` in the sorted order.
• Two main algorithms:
  • Kahn's Algorithm (BFS-based): Uses in-degrees and a queue. Iteratively adds nodes with 0 in-degree.
  • DFS-based Algorithm: Uses recursion and a stack. Adds nodes to result after all their dependents are processed.
• Both algorithms have $O(V + E)$ time complexity and can detect cycles.
• Essential for task scheduling, dependency resolution, and prerequisite systems.

📤 Coming Next: Shortest Path Algorithms (Dijkstra, Bellman-Ford)

Our journey through graphs continues! Having learned how to traverse and order them, the next logical step is to find optimal paths. The next chapter will introduce you to two cornerstone algorithms for finding the shortest paths in graphs: Dijkstra's Algorithm (for non-negative weights) and Bellman-Ford Algorithm (for handling negative weights).