Example: Topological Sort using DFS-based Algorithm in C

// Topological Sort using DFS-based Algorithm
#include <stdio.h>
#include <stdlib.h> // For malloc, free
#include <stdbool.h> // For bool

#define MAX_NODES 100

// Structure for an adjacency list node
struct AdjNode {
    int dest;
    struct AdjNode* next;
};

// Structure for the graph
struct GraphDFS {
    int numVertices;
    struct AdjNode** adjLists; // Array of linked lists
    int* visited;              // 0: unvisited, 1: visiting (in recursion stack), 2: visited
};

// Structure for a stack
struct Stack {
    int* arr;
    int top;
    int capacity;
};

// Function to create an adjacency list node
struct AdjNode* createAdjNodeDFS(int dest) {
    struct AdjNode* newNode = (struct AdjNode*)malloc(sizeof(struct AdjNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// Function to create a graph of 'vertices' number of nodes
struct GraphDFS* createGraphDFS(int vertices) {
    struct GraphDFS* graph = (struct GraphDFS*)malloc(sizeof(struct GraphDFS));
    graph->numVertices = vertices;

    graph->adjLists = (struct AdjNode**)malloc(vertices * sizeof(struct AdjNode*));
    graph->visited = (int*)calloc(vertices, sizeof(int)); // Initialize all to 0 (unvisited)

    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }
    return graph;
}

// Function to add an edge from src to dest
void addEdgeDFS(struct GraphDFS* graph, int src, int dest) {
    struct AdjNode* newNode = createAdjNodeDFS(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
}

// Stack functions
struct Stack* createStack(int capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->arr = (int*)malloc(capacity * sizeof(int));
    return stack;
}

bool isEmpty(struct Stack* stack) {
    return stack->top == -1;
}

void push(struct Stack* stack, int item) {
    if (stack->top == stack->capacity - 1) {
        // Stack overflow, for simplicity in tutorial, we assume enough capacity
        return;
    }
    stack->arr[++stack->top] = item;
}

int pop(struct Stack* stack) {
    if (isEmpty(stack)) {
        // Stack underflow
        return -1; // Or handle error appropriately
    }
    return stack->arr[stack->top--];
}

// Recursive DFS function for topological sort
bool dfsTopologicalSort(struct GraphDFS* graph, int u, struct Stack* stack, bool* hasCycle) {
    graph->visited[u] = 1; // Mark as visiting (GRAY)

    struct AdjNode* temp = graph->adjLists[u];
    while (temp != NULL) {
        int v = temp->dest;
        if (graph->visited[v] == 1) { // If neighbor is currently visiting, it's a back-edge (cycle)
            *hasCycle = true;
            return false; // Cycle detected
        }
        if (graph->visited[v] == 0) { // If neighbor is unvisited (WHITE)
            if (!dfsTopologicalSort(graph, v, stack, hasCycle)) {
                return false; // Propagate cycle detection
            }
        }
        temp = temp->next;
    }

    graph->visited[u] = 2; // Mark as visited (BLACK) - finished processing this node and its descendants
    push(stack, u);       // Push to stack after all descendants are processed
    return true;
}

// Function to perform topological sort using DFS-based algorithm
void topologicalSortDFS(struct GraphDFS* graph) {
    struct Stack* stack = createStack(graph->numVertices);
    bool hasCycle = false;

    for (int i = 0; i < graph->numVertices; i++) {
        if (graph->visited[i] == 0) { // If unvisited
            if (!dfsTopologicalSort(graph, i, stack, &hasCycle)) {
                break; // Cycle detected, no need to continue
            }
        }
    }

    if (hasCycle) {
        printf("Graph contains a cycle. Topological Sort not possible.\n");
    } else {
        printf("Topological Sort (DFS-based Algorithm): ");
        while (!isEmpty(stack)) {
            printf("%d ", pop(stack));
        }
        printf("\n");
    }

    free(stack->arr);
    free(stack);
}

// Function to free graph memory
void freeGraphDFS(struct GraphDFS* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        struct AdjNode* temp = graph->adjLists[i];
        while (temp != NULL) {
            struct AdjNode* toFree = temp;
            temp = temp->next;
            free(toFree);
        }
    }
    free(graph->adjLists);
    free(graph->visited);
    free(graph);
}

int main() {
    // Example 1: Graph with 6 vertices and 6 edges
    // Dependencies: A->B, A->C, B->D, C->D, E->F (using 0-indexed: 0->1, 0->2, 1->3, 2->3, 4->5)
    int numVertices1 = 6;
    struct GraphDFS* graph1 = createGraphDFS(numVertices1);
    addEdgeDFS(graph1, 0, 1); // A -> B
    addEdgeDFS(graph1, 0, 2); // A -> C
    addEdgeDFS(graph1, 1, 3); // B -> D
    addEdgeDFS(graph1, 2, 3); // C -> D
    addEdgeDFS(graph1, 4, 5); // E -> F

    topologicalSortDFS(graph1); // Expected: 4 0 2 1 3 5 or 4 0 1 2 3 5 etc.

    freeGraphDFS(graph1);

    printf("\n");

    // Example 2: Graph with a cycle (0->1, 1->2, 2->0)
    int numVertices2 = 3;
    struct GraphDFS* graph2 = createGraphDFS(numVertices2);
    addEdgeDFS(graph2, 0, 1);
    addEdgeDFS(graph2, 1, 2);
    addEdgeDFS(graph2, 2, 0); // Creates a cycle

    topologicalSortDFS(graph2); // Expected: "Graph contains a cycle..."

    freeGraphDFS(graph2);

    return 0;
}