Graph Algorithms VTU BCSL40A

Topological Sorting

Topological Sort linearly orders vertices of a Directed Acyclic Graph (DAG) such that for every directed edge u→v, vertex u comes before v.

Time Complexity

O(V + E)

Space Complexity

O(V)

Paradigm

Graph Algorithms

Introduction

Topological Sorting produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u → v, vertex u appears before vertex v. It is only possible for DAGs — graphs with no directed cycles. The algorithm is fundamental in scheduling problems, build systems, and dependency resolution.

Problem Statement

Given a Directed Acyclic Graph (DAG) G = (V, E), find a linear ordering of vertices such that for every edge (u, v), u comes before v in the ordering. If a cycle exists, report that no topological ordering is possible.

Real World Applications

→ Build systems (Make, Maven) — determine compilation order
→ Course prerequisite scheduling
→ Task scheduling with dependencies
→ Package manager dependency resolution
→ Data pipeline processing order

Algorithm Explanation

This implementation uses an iterative approach based on in-degree. It repeatedly finds vertices with in-degree 0 (no incoming edges), adds them to the topological order, then removes their outgoing edges (setting them to 0). This is equivalent to Kahn's algorithm. If all vertices are ordered, a valid topological ordering exists; otherwise, a cycle is present.

Step-by-Step Procedure

1 Read the adjacency matrix of the directed graph.
2 Repeat until all vertices are ordered or no vertex with in-degree 0 is found:
3 Find a vertex i with no incoming edges (no column j has ad[j][i] = 1).
4 If found, add it to the topological order.
5 Remove all outgoing edges from vertex i (set ad[i][k] = 0).
6 If all n vertices are ordered, print the topological order.
7 Otherwise, print 'No topological ordering possible' (cycle detected).

Complete C Program

Topological.c

View on GitHub ↗

#include<stdio.h>
#define MAX 10

void top(int ad[MAX][MAX], int n) {
    int f, count = 0, flag = 1, i, j, k;
    int torder[100], in = 1;
    while(flag) {
        count++;
        for(i = 1; i <= n; i++) {
            f = 0;
            for(j = 1; j <= n; j++) {
                if(ad[j][i] != 0 || torder[j] == i) {
                    f = 1;
                    break;
                }
            }
            if(f != 1) {
                torder[in++] = i;
                for(k = 1; k <= n; k++)
                    ad[i][k] = 0;
            }
        }
        if(count == n || in > n) flag = 0;
    }
    if(in <= n)
        printf("No Topological Ordering Possible (cycle detected)\n");
    else {
        printf("Topological Order:\n");
        for(i = 1; i <= n; i++)
            printf("%d\t", torder[i]);
        printf("\n");
    }
}

int main() {
    int ad[MAX][MAX], n;
    printf("Enter the Number of Vertices: ");
    scanf("%d", &n);
    printf("Enter the Adjacency Matrix of the Digraph:\n");
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            scanf("%d", &ad[i][j]);
    top(ad, n);
    return 0;
}

Sample Input & Output

Sample Input

6
0 1 1 0 0 0
0 0 0 1 1 0
0 0 0 0 1 0
0 0 0 0 0 1
0 0 0 0 0 1
0 0 0 0 0 0

Expected Output

Topological Order:
1   2   3   4   5   6

Dry Run / Trace

6 vertices. Edges: 1→2,1→3, 2→4,2→5, 3→5, 4→6, 5→6.
Iter 1: Vertex 1 has no incoming edges → order[1]=1. Remove 1's edges.
Iter 2: Vertex 2 has no incoming edges → order[2]=2. Vertex 3 has no incoming → order[3]=3.
Iter 3: Vertex 4 and 5 get ordered. Iter 4: Vertex 6 gets ordered.
Final: 1 2 3 4 5 6

Advantages & Disadvantages

✓ Advantages

+ Detects cycle in directed graphs
+ Foundation of many dependency solving algorithms
+ Linear time O(V+E) with adjacency list
+ Multiple valid orderings possible (flexibility)

✗ Disadvantages

− Only applicable to Directed Acyclic Graphs (DAGs)
− This implementation is O(V²) with adjacency matrix
− Does not produce unique ordering

Viva Questions & Answers

Q1. When is topological sorting not possible?

When the graph contains a directed cycle. Topological sort is only defined for Directed Acyclic Graphs (DAGs).

Q2. Can a graph have more than one valid topological ordering?

Yes. Multiple valid topological orderings can exist for the same DAG.

Q3. What is Kahn's algorithm for topological sort?

Kahn's algorithm maintains a queue of vertices with in-degree 0. It repeatedly removes a vertex, adds to order, and decrements in-degrees of neighbors.

Q4. How is topological sort related to DFS?

DFS-based topological sort adds each vertex to a stack when its DFS finishes. Popping the stack gives the topological order.

Q5. What is the in-degree of a vertex?

The number of incoming directed edges to a vertex. A vertex with in-degree 0 has no prerequisites and can appear first in topological order.