Mastering Topological Sort: A Comprehensive Guide with C Implementation

Introduction

Topological Sort is an essential concept in computer science and graph theory, primarily used in scenarios where we need to order tasks or events based on their dependencies. It applies to Directed Acyclic Graphs (DAGs) and provides a linear ordering of vertices such that for every directed edge UV, vertex U comes before V in the ordering. This ordering is crucial in various applications, including scheduling tasks, resolving symbol dependencies in linkers, and more. In this blog, we will delve into the intricacies of Topological Sort, explain its algorithms step-by-step, provide pseudo code, and walk you through its implementation in C. By the end of this article, you will have a solid understanding of Topological Sort and its practical applications.

Algorithm Details

There are two primary methods to perform a Topological Sort: using Depth-First Search (DFS) and using Kahn’s Algorithm (BFS). We will cover both methods, explain their logic, and provide pseudo code for each.

DFS-based Topological Sort

This approach leverages the Depth-First Search technique to perform the Topological Sort.

Step-by-Step Explanation

1. Initialization: Initialize a stack to store the topologically sorted order and a visited array to keep track of visited nodes.
2. Recursive DFS: Perform DFS on each unvisited node. In the DFS function, mark the current node as visited.
3. Process Node: For each adjacent vertex of the current node, if it is not visited, recursively call the DFS function.
4. Push to Stack: Once all adjacent vertices are processed, push the current node onto the stack.
5. Retrieve Order: After the DFS completes for all nodes, the stack will contain the topologically sorted order.

Pseudo Code

function topologicalSort(Graph):
    stack ← empty stack
    visited ← array of false values

    for each vertex in Graph:
        if vertex is not visited:
            DFS(vertex, visited, stack)

    while stack is not empty:
        print(stack.pop())

function DFS(vertex, visited, stack):
    visited[vertex] ← true

    for each neighbor of vertex:
        if neighbor is not visited:
            DFS(neighbor, visited, stack)

    stack.push(vertex)

Kahn’s Algorithm (BFS-based)

Kahn’s Algorithm uses BFS and an in-degree array to perform the Topological Sort.

Step-by-Step Explanation

1. Calculate In-Degree: Compute the in-degree (number of incoming edges) for each vertex.
2. Initialize Queue: Initialize a queue and enqueue all vertices with in-degree 0.
3. Process Queue: While the queue is not empty, dequeue a vertex and add it to the topological order.
4. Update In-Degree: For each adjacent vertex, reduce its in-degree by 1. If the in-degree becomes 0, enqueue the vertex.
5. Check for Cycles: If the topological order contains all the vertices, a valid topological sort is found. Otherwise, the graph contains a cycle.

Pseudo Code

function topologicalSort(Graph):
    inDegree ← array of 0s
    queue ← empty queue
    topoOrder ← empty list

    for each vertex in Graph:
        for each neighbor of vertex:
            inDegree[neighbor] += 1

    for each vertex in Graph:
        if inDegree[vertex] == 0:
            queue.enqueue(vertex)

    while queue is not empty:
        vertex ← queue.dequeue()
        topoOrder.append(vertex)

        for each neighbor of vertex:
            inDegree[neighbor] -= 1
            if inDegree[neighbor] == 0:
                queue.enqueue(neighbor)

    if length of topoOrder != number of vertices in Graph:
        return "Graph has a cycle"
    else:
        return topoOrder

Implementation in C

Here, we will implement the DFS-based Topological Sort in C.

Code

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

#define MAX 100

int adj[MAX][MAX], visited[MAX], stack[MAX], top = -1;
int n;

void push(int v) {
    stack[++top] = v;
}

int pop() {
    return stack[top--];
}

void DFS(int v) {
    visited[v] = 1;

    for (int i = 0; i < n; i++) {
        if (adj[v][i] && !visited[i]) {
            DFS(i);
        }
    }
    push(v);
}

void topologicalSort() {
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
    }

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

    printf("Topological Sort:\n");
    while (top != -1) {
        printf("%d ", pop());
    }
    printf("\n");
}

int main() {
    int e, u, v;
    printf("Enter the number of vertices:\n");
    scanf("%d", &n);

    printf("Enter the number of edges:\n");
    scanf("%d", &e);

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

    topologicalSort();

    return 0;
}

Explanation of C Code

1. Graph Representation: The graph is represented using an adjacency matrix adj[MAX][MAX].
2. Visited Array: The visited array keeps track of visited nodes during the DFS traversal.
3. Stack: The stack array is used to store the nodes in topologically sorted order.
4. DFS Function: The DFS function recursively visits all adjacent vertices and pushes the node onto the stack after visiting all its neighbors.
5. Topological Sort Function: The topologicalSort function initializes the visited array, performs DFS on all unvisited nodes, and prints the nodes in topologically sorted order.
6. Main Function: The main function takes input for the number of vertices and edges, reads the edges, and calls the topologicalSort function to compute and print the topological order.

Time and Space Complexity

Time Complexity

• DFS-based Topological Sort: The time complexity is O(V+E), where V is the number of vertices and E is the number of edges. This is because each vertex and edge is processed once.
• Kahn’s Algorithm: The time complexity is also O(V+E) due to the processing of vertices and edges.

Space Complexity

• DFS-based Topological Sort: The space complexity is O(V) for the stack and visited array.
• Kahn’s Algorithm: The space complexity is O(V) for the in-degree array, queue, and topological order list.

Usage

Topological Sort has various practical applications:

• Task Scheduling: Ordering tasks with dependencies in project management.
• Course Prerequisites: Determining the order in which courses should be taken based on prerequisites.
• Compiler Design: Resolving symbol dependencies during compilation.
• Package Management: Determining the order of package installations based on dependencies.

Conclusion

Topological Sort is a powerful tool for ordering tasks or events based on their dependencies. By understanding and implementing both DFS-based and Kahn’s Algorithm for Topological Sort, you can solve various real-world problems efficiently. We hope this guide has provided you with a comprehensive understanding of Topological Sort and its applications.

If you found this blog helpful or have any suggestions for improving it, please leave your feedback or suggestions in the comments. Your input is valuable in helping me create better and more informative content for you!