Topological Sorting Program with Explanation and Code

2025-11-19 topological sort graph algorithms directed acyclic graph DAG kahn algorithm dfs topological sort dependency resolution scheduling python topological sort c topological sort js topological sort php graph programs csharp topological sorting

Topological Sorting is used to order vertices of a Directed Acyclic Graph such that all dependencies come before dependents. This page explains the concept and includes complete implementations in Python, C, JavaScript, PHP, and C#. Ideal for graph algorithm learning and interview preparation.

Program Explanation

What is Topological Sorting?

Topological Sorting is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge U → V, vertex U comes before vertex V in the ordering. It is widely used in scheduling tasks, resolving dependencies, compiler design, and ordering course prerequisites.

Steps to Solve

  1. Ensure the graph is a Directed Acyclic Graph (DAG).
  2. Compute the in-degree (number of incoming edges) for each vertex.
  3. Insert all vertices with in-degree 0 into a queue.
  4. Remove (pop) a vertex from the queue and add it to the topological order list.
  5. Decrease the in-degree of all adjacent vertices by 1.
  6. If any adjacent vertex reaches in-degree 0, push it into the queue.
  7. Repeat until the queue becomes empty.
  8. If all vertices are processed → valid topological order.
  9. If not → graph contains a cycle; topological sorting is not possible.

Key Points

  • Works only on Directed Acyclic Graphs (DAG).
  • Common methods: Kahn’s Algorithm (BFS) and DFS-based approach.
  • Kahn’s Algorithm uses in-degree and queue.
  • DFS method uses recursion + stack.
  • Used for dependency resolution & scheduling.
  • Time complexity: O(V + E).

Program Code


from collections import deque

def topological_sort(V, graph):
    indegree = [0] * V
    
    for u in range(V):
        for v in graph[u]:
            indegree[v] += 1

    q = deque([i for i in range(V) if indegree[i] == 0])
    order = []

    while q:
        u = q.popleft()
        order.append(u)

        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                q.append(v)

    if len(order) != V:
        return "Graph contains a cycle!"

    return order

V = int(input("Enter number of vertices: "))
E = int(input("Enter number of edges: "))

graph = [[] for _ in range(V)]
print("Enter edges (u v):")

for _ in range(E):
    u, v = map(int, input().split())
    graph[u].append(v)

print("Topological Order:", topological_sort(V, graph))
      

#include <stdio.h>

int main() {
    int V, E;
    printf("Enter number of vertices: ");
    scanf("%d", &V);

    printf("Enter number of edges: ");
    scanf("%d", &E);

    int graph[V][V];
    int indegree[V];

    for (int i = 0; i < V; i++) {
        indegree[i] = 0;
        for (int j = 0; j < V; j++)
            graph[i][j] = 0;
    }

    printf("Enter edges (u v):\n");
    for (int i = 0; i < E; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u][v] = 1;
        indegree[v]++;
    }

    int queue[V], front = 0, rear = 0;

    for (int i = 0; i < V; i++)
        if (indegree[i] == 0)
            queue[rear++] = i;

    int count = 0;
    int order[V];

    while (front < rear) {
        int u = queue[front++];
        order[count++] = u;

        for (int v = 0; v < V; v++) {
            if (graph[u][v]) {
                indegree[v]--;
                if (indegree[v] == 0)
                    queue[rear++] = v;
            }
        }
    }

    if (count != V)
        printf("Graph contains a cycle!");
    else {
        printf("Topological Order: ");
        for (int i = 0; i < V; i++)
            printf("%d ", order[i]);
    }

    return 0;
}
      

function topologicalSort(V, graph) {
  let indegree = Array(V).fill(0);

  for (let u = 0; u < V; u++)
    for (let v of graph[u])
      indegree[v]++;

  let queue = [];
  for (let i = 0; i < V; i++)
    if (indegree[i] === 0) queue.push(i);

  let order = [];

  while (queue.length) {
    let u = queue.shift();
    order.push(u);

    for (let v of graph[u]) {
      indegree[v]--;
      if (indegree[v] === 0) queue.push(v);
    }
  }

  if (order.length !== V)
    return "Graph contains a cycle!";

  return order;
}

let V = parseInt(prompt("Enter number of vertices:"));
let E = parseInt(prompt("Enter number of edges:"));

let graph = Array.from({ length: V }, () => []);
for (let i = 0; i < E; i++) {
  let [u, v] = prompt("Enter edge (u v):").split(" ").map(Number);
  graph[u].push(v);
}

console.log("Topological Order:", topologicalSort(V, graph));
      

using System;
using System.Collections.Generic;

class Program {

    static List TopologicalSort(int V, List[] graph) {
        int[] indegree = new int[V];

        for (int u = 0; u < V; u++)
            foreach (int v in graph[u])
                indegree[v]++;

        Queue q = new Queue();
        for (int i = 0; i < V; i++)
            if (indegree[i] == 0)
                q.Enqueue(i);

        List order = new List();

        while (q.Count > 0) {
            int u = q.Dequeue();
            order.Add(u);

            foreach (int v in graph[u]) {
                indegree[v]--;
                if (indegree[v] == 0)
                    q.Enqueue(v);
            }
        }

        if (order.Count != V)
            return null;

        return order;
    }

    static void Main() {
        Console.Write("Enter number of vertices: ");
        int V = int.Parse(Console.ReadLine());

        Console.Write("Enter number of edges: ");
        int E = int.Parse(Console.ReadLine());

        List[] graph = new List[V];
        for (int i = 0; i < V; i++)
            graph[i] = new List();

        Console.WriteLine("Enter edges (u v):");
        for (int i = 0; i < E; i++) {
            var parts = Console.ReadLine().Split();
            int u = int.Parse(parts[0]);
            int v = int.Parse(parts[1]);
            graph[u].Add(v);
        }

        var result = TopologicalSort(V, graph);

        if (result == null)
            Console.WriteLine("Graph contains a cycle!");
        else
            Console.WriteLine("Topological Order: " + string.Join(" ", result));
    }
}
      

<?php

function topologicalSort($V, $graph) {
    $indegree = array_fill(0, $V, 0);

    for ($u = 0; $u < $V; $u++)
        foreach ($graph[$u] as $v)
            $indegree[$v]++;

    $queue = [];
    for ($i = 0; $i < $V; $i++)
        if ($indegree[$i] == 0)
            $queue[] = $i;

    $order = [];

    while ($queue) {
        $u = array_shift($queue);
        $order[] = $u;

        foreach ($graph[$u] as $v) {
            $indegree[$v]--;
            if ($indegree[$v] == 0)
                $queue[] = $v;
        }
    }

    if (count($order) != $V)
        return "Graph contains a cycle!";

    return implode(" ", $order);
}

$V = intval(readline("Enter number of vertices: "));
$E = intval(readline("Enter number of edges: "));

$graph = array_fill(0, $V, []);
echo "Enter edges (u v):\n";

for ($i = 0; $i < $E; $i++) {
    [$u, $v] = explode(" ", readline());
    $graph[$u][] = intval($v);
}

echo "Topological Order: " . topologicalSort($V, $graph);

?>
1