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.