Topological Sort in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
int g[10][10], vis[10], st[10], top = -1;
void dfs(int u, int n) {
    vis[u] = 1;
    for (int v = 0; v < n; v++)
        if (g[u][v] && !vis[v]) dfs(v, n);
    st[++top] = u;
}
int main() {
    int n = 4;
    g[0][1] = g[0][2] = 1;
    g[1][3] = g[2][3] = 1;
    for (int i = 0; i < n; i++) if (!vis[i]) dfs(i, n);
    while (top >= 0) printf("%d ", st[top--]);
}

C Output

Input:
Graph: 0→1, 0→2, 1→3, 2→3
Output:
Input: Edges: 0→1, 0→2, 1→3, 2→3
Output: 0 2 1 3

C++ Program

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> g;
vector<int> vis, st;
void dfs(int u) {
    vis[u] = 1;
    for (int v : g[u]) if (!vis[v]) dfs(v);
    st.push_back(u);
}
int main() {
    int n = 5;
    g = {{1, 2}, {3}, {3}, {4}, {}};
    vis = vector<int>(n);
    for (int i = 0; i < n; i++) if (!vis[i]) dfs(i);
    for (auto it = st.rbegin(); it != st.rend(); ++it) cout << *it << " ";
}

C++ Output

Input:
Graph: 0→1, 0→2, 1→3, 2→3, 3→4
Output:
Input: Edges: 0→1, 0→2, 1→3, 2→3, 3→4
Output: 0 2 1 3 4

JAVA Program

import java.util.*;
class Main {
    static List<List<Integer>> g = new ArrayList<>();
    static boolean[] vis;
    static Stack<Integer> st = new Stack<>();
    static void dfs(int u) {
        vis[u] = true;
        for (int v : g.get(u)) if (!vis[v]) dfs(v);
        st.push(u);
    }
    public static void main(String[] a) {
        int n = 4;
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        g.get(0).add(1); g.get(1).add(2); g.get(2).add(3);
        vis = new boolean[n];
        for (int i = 0; i < n; i++) if (!vis[i]) dfs(i);
        while (!st.isEmpty()) System.out.print(st.pop() + " ");
    }
}

JAVA Output

Input:
Graph: 0→1→2→3
Output:
Input: Chain DAG
Output: 0 1 2 3

Python Program

g = {0: [1, 2], 1: [3], 2: [3], 3: []}
vis, st = set(), []
def dfs(u):
    vis.add(u)
    for v in g[u]:
        if v not in vis: dfs(v)
    st.append(u)
for u in g:
    if u not in vis: dfs(u)
print(*reversed(st))

Python Output

Input:
Graph: 0→1, 0→2, 1→3, 2→3
Output:
Input: Edges: 0→1, 0→2, 1→3, 2→3
Output: 0 2 1 3

In-Depth Explanation

Example

Topological sorting places nodes in such a way that no node comes before its prerequisites.

In the C example:

0 → 1  

0 → 2  

1 → 3  

2 → 3

Valid order: 0 2 1 3

We can also have 0 1 2 3 based on DFS traversal order — there can be more than one valid output in topological sort.

Real-Life Analogy

Suppose you are planning a cooking recipe. You have to first:

Chop vegetables (0)

Boil water (1)

Cook pasta (2) is dependent on boiling water

Combine pasta and sauce (3) is dependent on steps 1 and 2

This ordering has to respect the dependency chain — just like topological sort does in directed graphs.

Why It Matters

Topological sort is crucial when:

Jobs have dependencies

You want to find the compilation, scheduling, or processing order

Planning projects, data pipes, or dependency resolution

It only applies to DAGs — directed graphs with no cycles. Cycles violate the "before/after" relationship assumption.

Learning Insights

You learn:

How DFS can be used to construct ordering from post-order

Why visited nodes need to be checked to prevent re-visit

Stack-based reasoning that reverses dependency relationships naturally

It also lays the ground for:

Kahn's algorithm (BFS-based topo sort)

Cycle detection in graphs

Task scheduling and dependency graphs

Interview & Real-World Use

It's often asked in:

Scheduling problems

Build systems (compiling code with dependencies)

Graph traversal + ordering combination

Cycle detection in course/prerequisite problems

Applied in:

Package managers (npm, pip)

Compilers for order of execution

Workflow engines and project planners

Database query optimizers

Topological Sort is an important algorithm applied in problem-solving where dependency resolution is involved. Whether you are constructing a software module, cooking in sequence, or controlling a task pipeline, it makes sure that each step comes after its prerequisite. As opposed to shortest path problems, this is concerned with task ordering, so it forms the basis of compilers, project schedulers, and job schedulers. The C, C++, Java, and Python examples show how elegant and straightforward this algorithm can be with DFS. You strengthen your algorithmic skills by learning this concept and prepare for actual dependency systems and interview rounds that really matter.