Topological Sort Using DFS in DSA C

Mental Model

We visit each node and all its dependencies first, then add the node to the order. This way, nodes appear after all nodes they depend on.

Analogy: Imagine finishing homework assignments where some depend on others. You must complete the prerequisites first before the dependent tasks.

Graph:
A -> B -> C
↑
D

Topological order means: D before A, A before B, B before C

Dry Run Walkthrough

Input: Graph edges: D->A, A->B, B->C

Goal: Find an order to do tasks so all dependencies come before the task itself

Step 1: Start DFS at node D

Visited: D
Stack: []

Why: We begin with D which has no dependencies

Step 2: From D, visit A

Visited: D, A
Stack: []

Why: A depends on D, so we visit A after D

Step 3: From A, visit B

Visited: D, A, B
Stack: []

Why: B depends on A, so we visit B after A

Step 4: From B, visit C

Visited: D, A, B, C
Stack: []

Why: C depends on B, so we visit C after B

Step 5: C has no dependencies, add C to stack

Stack: [C]

Why: No more nodes to visit from C, so add it to order

Step 6: Back to B, add B to stack

Stack: [C, B]

Why: All dependencies of B visited, add B

Step 7: Back to A, add A to stack

Stack: [C, B, A]

Why: All dependencies of A visited, add A

Step 8: Back to D, add D to stack

Stack: [C, B, A, D]

Why: All dependencies of D visited, add D

Result:

Stack (reversed) gives topological order:
D -> A -> B -> C

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// Graph structure using adjacency list
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* graph[MAX];
int visited[MAX];
int stack[MAX];
int top = -1;
int numVertices = 0;

// Create a new adjacency list node
Node* createNode(int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// Add edge from src to dest
void addEdge(int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph[src];
    graph[src] = newNode;
}

// DFS function for topological sort
void dfs(int v) {
    visited[v] = 1; // mark current node visited
    Node* temp = graph[v];
    while (temp != NULL) {
        if (!visited[temp->vertex]) {
            dfs(temp->vertex); // visit dependencies first
        }
        temp = temp->next;
    }
    stack[++top] = v; // add node after visiting dependencies
}

// Topological sort driver
void topologicalSort(int vertices) {
    for (int i = 0; i < vertices; i++) {
        visited[i] = 0; // reset visited
    }
    top = -1;
    for (int i = 0; i < vertices; i++) {
        if (!visited[i]) {
            dfs(i); // visit all nodes
        }
    }
    // print stack in reverse order
    for (int i = top; i >= 0; i--) {
        printf("%c", 'A' + stack[i]);
        if (i > 0) printf(" -> ");
    }
    printf("\n");
}

int main() {
    numVertices = 4; // A=0, B=1, C=2, D=3
    for (int i = 0; i < numVertices; i++) {
        graph[i] = NULL;
    }
    addEdge(3, 0); // D->A
    addEdge(0, 1); // A->B
    addEdge(1, 2); // B->C

    topologicalSort(numVertices);
    return 0;
}

visited[v] = 1; // mark current node visited

mark node as visited to avoid revisiting

while (temp != NULL) { if (!visited[temp->vertex]) { dfs(temp->vertex); } temp = temp->next; }

visit all dependencies of current node first

stack[++top] = v; // add node after visiting dependencies

add node to stack after all dependencies processed

for (int i = 0; i < vertices; i++) { if (!visited[i]) { dfs(i); } }

start DFS from all unvisited nodes to cover entire graph

for (int i = top; i >= 0; i--) { printf("%c", 'A' + stack[i]); if (i > 0) printf(" -> "); }

print nodes in reverse order of finishing times for topological order

Output

D -> A -> B -> C

Complexity Analysis

Time: O(V + E) because we visit each vertex and edge once during DFS

Space: O(V + E) for adjacency list and recursion stack in worst case

vs Alternative: Compared to Kahn's algorithm which uses queue and in-degree, DFS uses recursion and stack but both have similar time complexity

Edge Cases

Empty graph (no vertices)

No output, function handles gracefully by skipping DFS

DSA C

for (int i = 0; i < vertices; i++) { if (!visited[i]) { dfs(i); } }

Graph with no edges (all independent nodes)

All nodes printed in any order since no dependencies

DSA C

while (temp != NULL) { if (!visited[temp->vertex]) { dfs(temp->vertex); } temp = temp->next; }

Graph with cycle (not a DAG)

Algorithm does not detect cycle; output is invalid topological order

DSA C

No explicit cycle detection in dfs function

When to Use This Pattern

When you need to order tasks with dependencies and the graph has no cycles, use DFS-based topological sort to get a valid order by visiting dependencies first.

Common Mistakes

Mistake: Adding the node to the order before visiting its dependencies
Fix: Add the node to the stack only after all its dependencies have been visited

Mistake: Not marking nodes as visited, causing infinite recursion
Fix: Mark nodes as visited at the start of DFS call to avoid revisiting

Mistake: Printing the stack in the order nodes were added instead of reversed
Fix: Print the stack from top to bottom to get correct topological order

Summary

It finds an order of nodes so that every node appears after all nodes it depends on.

Use it when you have tasks with dependencies and want to schedule them without conflicts.

The key is to visit all dependencies first before adding the node to the order.

Practice

1. What is the main purpose of using DFS in Topological Sort on a Directed Acyclic Graph (DAG)?

easy

A. To visit nodes in a way that all dependencies come before the node

B. To find the shortest path between two nodes

C. To detect cycles in an undirected graph

D. To count the number of connected components

Solution

1. Step 1: Understand DFS role in Topological Sort

   DFS visits nodes deeply, ensuring all nodes reachable from a node are visited before the node itself.

2. Step 2: Relate DFS to dependency order

   This ensures nodes appear after all their dependencies, which is the goal of topological sorting.

3. Final Answer:

   To visit nodes in a way that all dependencies come before the node -> Option A

4. Quick Check:

   DFS orders nodes respecting dependencies [OK]

Hint: DFS ensures dependencies come before nodes in topological order [OK]

Common Mistakes:

• Confusing topological sort with shortest path
• Thinking DFS detects cycles in undirected graphs here
• Mixing connected components with topological order

2. Which of the following is the correct way to mark a node as visited in a DFS-based topological sort in C?

easy

A. visited(node) = true;

B. visited[node] = 1;

C. visited[node] == true;

D. visited[node] = false;

Solution

1. Step 1: Understand C syntax for arrays

   In C, arrays use square brackets to access elements, so visited[node] is correct.

2. Step 2: Assigning visited status

   Assigning 1 marks the node as visited; '==' is comparison, not assignment; 'false' would mark unvisited.

3. Final Answer:

   visited[node] = 1; -> Option B

4. Quick Check:

   Use visited[node] = 1 to mark visited [OK]

Hint: Use visited[node] = 1 to mark visited in C arrays [OK]

Common Mistakes:

• Using parentheses instead of brackets for arrays
• Using '==' instead of '=' for assignment
• Assigning false instead of true/1 to mark visited

3. What is the output order of nodes after performing DFS-based topological sort on this graph?

Edges:
0 -> 1
0 -> 2
1 -> 3
2 -> 3

Assume nodes are pushed to stack after visiting all neighbors and stack is printed top to bottom.

medium

A. [0, 2, 1, 3]

B. [3, 2, 1, 0]

C. [0, 1, 2, 3]

D. [3, 1, 2, 0]

Solution

1. Step 1: Perform DFS starting from node 0

   Visit 0, then neighbors 1 then 2 (edge order). From 1 to 3, from 2 to 3 (visited).

2. Step 2: Push nodes to stack after visiting neighbors

   Push 3, then 1, then 3 already visited, then 2, then 0. Stack top to bottom: [3, 1, 2, 0].

3. Final Answer:

   [3, 1, 2, 0] -> Option D

4. Quick Check:

   Stack top to bottom after DFS = [3, 1, 2, 0] [OK]

Hint: Push nodes after neighbors; output is stack top to bottom [OK]

Common Mistakes:

• Pushing nodes before visiting neighbors
• Confusing order of neighbors visited
• Printing stack bottom to top instead of top to bottom

4. Identify the error in this DFS-based topological sort code snippet in C:

void dfs(int node) {
  visited[node] = 1;
  for (int i = 0; i < adj[node].size(); i++) {
    int nbr = adj[node][i];
    if (!visited[nbr])
      dfs(nbr);
  }
  stack.push(node);
}

medium

A. Stack push should be before recursive calls

B. Missing base case for cycle detection

C. Using adj[node].size() is invalid in C

D. visited array should be initialized to 2 instead of 1

Solution

1. Step 1: Check syntax for adjacency list size in C

   adj[node].size() is C++ syntax; C does not support .size() method on arrays.

2. Step 2: Identify correct way to get adjacency list size in C

   In C, adjacency lists are usually arrays with separate size variables; .size() causes compile error.

3. Final Answer:

   Using adj[node].size() is invalid in C -> Option C

4. Quick Check:

   adj[node].size() is C++ only, not C [OK]

Hint: Use array length variables in C, not .size() method [OK]

Common Mistakes:

• Confusing C and C++ syntax for containers
• Ignoring cycle detection in topological sort
• Pushing nodes before recursive calls

5. Given a graph with edges:

5 -> 2
5 -> 0
4 -> 0
4 -> 1
2 -> 3
3 -> 1

Which of the following is a valid topological order using DFS-based topological sort?

hard

A. [4, 5, 2, 3, 1, 0]

B. [4, 0, 5, 2, 3, 1]

C. [5, 0, 4, 2, 3, 1]

D. [5, 4, 3, 2, 1, 0]

Solution

1. Step 1: Analyze prerequisites from edges

   (u -> v means u before v): 5 before 2 and 0; 4 before 0 and 1; 2 before 3; 3 before 1.

2. Step 2: Check each option for prerequisite order

   [4, 5, 2, 3, 1, 0]: 4 before 0 and 1, 5 before 2 and 0, 2 before 3, 3 before 1, all correct.

3. Final Answer:

   [4, 5, 2, 3, 1, 0] -> Option A

4. Quick Check:

   All edges respected in order D [OK]

Hint: Check each edge u->v: u appears before v in order [OK]

Common Mistakes:

• Ignoring edge directions in order
• Placing dependent nodes before their prerequisites
• Assuming any order with all nodes is valid