C Topological Sort 🎯

Welcome to your comprehensive guide on C Topological Sort! This lesson is designed to be beginner-friendly, yet packed with enough depth for intermediates. Let's dive into the world of Graph Theory and learn how to apply it in C programming.

What is Topological Sort? 📝

Topological Sort is a popular algorithm used to linearly order the vertices of a Directed Acyclic Graph (DAG) in such a way that for every directed edge u v, vertex u comes before vertex v in the order.

Why is it important? Topological Sort has a wide range of applications, from scheduling tasks in a project to resolving dependencies in a build system.

Prerequisites 💡

Basic understanding of C programming
Familiarity with data structures such as arrays and linked lists
Knowledge of Graph Theory basics (nodes, edges, adjacency lists)

Topological Sort Algorithm 🎯

The Topological Sort algorithm works by initializing a count for the number of incoming edges for each node (using a technique called Kahn's algorithm). Once we have nodes with zero incoming edges, we remove them from the graph and repeat the process until all nodes are processed.

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

#define MAX_VERTICES 100

// Function to add an edge from src to dest in the adjacency list representation
void addEdge(int graph[][MAX_VERTICES], int src, int dest) {
    graph[src][dest] = 1;
}

// Function to perform topological sort using Kahn's algorithm
void topologicalSort(int vertices, int graph[][MAX_VERTICES]) {
    int indegree[MAX_VERTICES] = {0};
    int visited[MAX_VERTICES] = {0};
    int stack[MAX_VERTICES];
    int count = 0;

    // Initialize indegrees and mark all vertices as unvisited
    for (int i = 0; i < vertices; i++) {
        indegree[i] = 0;
        visited[i] = 0;
    }

    // Calculate indegrees of vertices
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            if (graph[j][i]) indegree[i]++;
        }
    }

    // Find all vertices with 0 indegree and enqueue them
    int queueFront = 0;
    for (int i = 0; i < vertices; i++) {
        if (indegree[i] == 0) {
            stack[count++] = i;
        }
    }

    // Perform topological sort
    while (count > 0) {
        int u = stack[--count];
        visited[u] = 1;

        // Print vertex u
        printf("%d ", u);

        // Update indegree of vertices that have an edge from vertex u
        for (int v = 0; v < vertices; v++) {
            if (graph[u][v] && !visited[v]) {
                indegree[v]--;
                if (indegree[v] == 0) {
                    stack[count++] = v;
                }
            }
        }
    }

    // If there are still some vertices left unvisited, the graph is cyclic
    if (count != vertices) printf("The graph is cyclic.\n");
}

// Main function to test topological sort
int main() {
    int vertices = 6;
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {0, 0, 1, 1, 0, 0},
        {0, 0, 0, 0, 1, 0},
        {0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0, 0}
    };

    topologicalSort(vertices, graph);
    return 0;
}

Let's create another example with a cyclic graph to understand when the graph is cyclic.

int main() {
    int vertices = 5;
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {0, 1, 0, 1, 1},
        {0, 0, 0, 0, 0},
        {0, 0, 0, 1, 0},
        {0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0}
    };

    topologicalSort(vertices, graph);
    return 0;
}

That's all for this lesson on C Topological Sort! As you practice, you'll find numerous real-world applications for this essential algorithm. Happy coding! 👩‍💻👨‍💻