Example: DFS-based Topological Sort in C

// DFS-based Topological Sort
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTICES 100

// Adjacency list representation
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* adj[MAX_VERTICES];
int num_vertices;
bool visited[MAX_VERTICES];
int stack[MAX_VERTICES];
int stack_idx = 0;

void add_edge(int u, int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = adj[u];
    adj[u] = newNode;
}

void init_graph(int vertices) {
    num_vertices = vertices;
    for (int i = 0; i < num_vertices; i++) {
        adj[i] = NULL;
        visited[i] = false;
    }
    stack_idx = 0;
}

void dfs_topological_sort(int u) {
    visited[u] = true;

    Node* current = adj[u];
    while (current != NULL) {
        int v = current->vertex;
        if (!visited[v]) {
            dfs_topological_sort(v);
        }
        current = current->next;
    }

    // Push current vertex to stack after all its dependencies are visited
    stack[stack_idx++] = u;
}

void topological_sort() {
    for (int i = 0; i < num_vertices; i++) {
        if (!visited[i]) {
            dfs_topological_sort(i);
        }
    }

    printf("DFS-based Topological Sort Order: ");
    for (int i = stack_idx - 1; i >= 0; i--) { // Print in reverse order to get correct topological order
        printf("%d ", stack[i]);
    }
    printf("\n");
}

int main() {
    // Step 1: Initialize graph with 6 vertices (0-5)
    init_graph(6);

    // Step 2: Add edges for the example: A->C, B->C, B->D, C->E, D->E, E->F
    // Mapping: A=0, B=1, C=2, D=3, E=4, F=5
    add_edge(0, 2); // A -> C
    add_edge(1, 2); // B -> C
    add_edge(1, 3); // B -> D
    add_edge(2, 4); // C -> E
    add_edge(3, 4); // D -> E
    add_edge(4, 5); // E -> F

    // Step 3: Perform topological sort
    topological_sort();

    // Clean up allocated memory (optional for simple examples, good practice for larger programs)
    for (int i = 0; i < num_vertices; i++) {
        Node* current = adj[i];
        while (current != NULL) {
            Node* temp = current;
            current = current->next;
            free(temp);
        }
    }

    return 0;
}