Advanced Graph Algorithms in C: Topological Sort, SCC (Kosaraju & Tarjan) & Ford-Fulkerson Max Flow

1. What is Topological Sort?

Topological Sort is an ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge (u → v), vertex u appears before vertex v in the ordering. It’s used in scheduling tasks with dependencies.

2. How does Topological Sort work?

• DFS Approach: Perform DFS, pushing vertices to a stack after exploring all their neighbors. The stack’s reverse order is the topological sort.
• Kahn’s Algorithm: Use in-degree of vertices, repeatedly removing vertices with in-degree 0 and updating in-degrees.

3. Can you give an example of Topological Sort using DFS in C?

Example: Topological sort for a DAG with 6 vertices and edges (5→2, 5→0, 4→0, 4→1, 2→3, 3→1).

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

#define V 6

struct Node {
    int vertex;
    struct Node* next;
};

struct Graph {
    struct Node* adjList[V];
    int visited[V];
};

void initGraph(struct Graph* g) {
    for (int i = 0; i < V; i++) {
        g->adjList[i] = NULL;
        g->visited[i] = 0;
    }
}

void addEdge(struct Graph* g, int src, int dest) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->vertex = dest;
    newNode->next = g->adjList[src];
    g->adjList[src] = newNode;
}

void freeGraph(struct Graph* g) {
    for (int i = 0; i < V; i++) {
        struct Node* temp = g->adjList[i];
        while (temp) {
            struct Node* next = temp->next;
            free(temp);
            temp = next;
        }
    }
}

void dfsTopo(struct Graph* g, int v, int* stack, int* stackIndex) {
    g->visited[v] = 1;
    struct Node* temp = g->adjList[v];
    while (temp) {
        if (!g->visited[temp->vertex]) {
            dfsTopo(g, temp->vertex, stack, stackIndex);
        }
        temp = temp->next;
    }
    stack[(*stackIndex)++] = v; // Push to stack after exploring neighbors
}

void topologicalSort(struct Graph* g) {
    int stack[V], stackIndex = 0;
    for (int i = 0; i < V; i++) {
        if (!g->visited[i]) {
            dfsTopo(g, i, stack, &stackIndex);
        }
    }
    printf("Topological Sort: ");
    for (int i = stackIndex - 1; i >= 0; i--) {
        printf("%d ", stack[i]); // Print in reverse order
    }
    printf("\n");
}

int main() {
    struct Graph g;
    initGraph(&g);
    addEdge(&g, 5, 2);
    addEdge(&g, 5, 0);
    addEdge(&g, 4, 0);
    addEdge(&g, 4, 1);
    addEdge(&g, 2, 3);
    addEdge(&g, 3, 1);
    topologicalSort(&g); // Output: Topological Sort: 5 4 2 3 1 0 (order may vary)
    freeGraph(&g); // Clean up memory
    return 0;
}
      

4. What are the time and space complexities of Topological Sort?

• Time Complexity: O(V + E) (V = vertices, E = edges).
• Space Complexity: O(V) (visited array and stack/recursion).

5. What are the applications of Topological Sort?

• Task scheduling with dependencies.
• Course prerequisite ordering.
• Build systems (e.g., make).
• Detecting cycles in a DAG (if topological sort fails, a cycle exists).

6. What is a Strongly Connected Component (SCC)?

An SCC in a directed graph is a maximal subgraph where there is a path from every vertex to every other vertex. SCCs are used to analyze connectivity in directed graphs.

7. What is Kosaraju’s Algorithm?

Kosaraju’s Algorithm finds all SCCs in a directed graph using two DFS passes: one on the original graph to get finishing times, and one on the transposed graph in reverse finishing order to identify SCCs.

8. Can you give an example of Kosaraju’s Algorithm in C?

Example: Finding SCCs in a directed graph with 5 vertices and edges (1→0, 0→2, 2→1, 0→3, 3→4).

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

#define V 5

struct Node {
    int vertex;
    struct Node* next;
};

struct Graph {
    struct Node* adjList[V];
    int visited[V];
};

void initGraph(struct Graph* g) {
    for (int i = 0; i < V; i++) {
        g->adjList[i] = NULL;
        g->visited[i] = 0;
    }
}

void addEdge(struct Graph* g, int src, int dest) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->vertex = dest;
    newNode->next = g->adjList[src];
    g->adjList[src] = newNode;
}

void freeGraph(struct Graph* g) {
    for (int i = 0; i < V; i++) {
        struct Node* temp = g->adjList[i];
        while (temp) {
            struct Node* next = temp->next;
            free(temp);
            temp = next;
        }
    }
}

void dfsFill(struct Graph* g, int v, int* stack, int* stackIndex) {
    g->visited[v] = 1;
    struct Node* temp = g->adjList[v];
    while (temp) {
        if (!g->visited[temp->vertex]) {
            dfsFill(g, temp->vertex, stack, stackIndex);
        }
        temp = temp->next;
    }
    stack[(*stackIndex)++] = v; // Push to stack after finishing
}

void dfsSCC(struct Graph* g, int v) {
    g->visited[v] = 1;
    printf("%d ", v);
    struct Node* temp = g->adjList[v];
    while (temp) {
        if (!g->visited[temp->vertex]) {
            dfsSCC(g, temp->vertex);
        }
        temp = temp->next;
    }
}

void kosaraju(struct Graph* g, struct Graph* gT) {
    int stack[V], stackIndex = 0;
    for (int i = 0; i < V; i++) g->visited[i] = 0;
    // First DFS: Fill stack with finishing times
    for (int i = 0; i < V; i++) {
        if (!g->visited[i]) {
            dfsFill(g, i, stack, &stackIndex);
        }
    }
    // Second DFS: Process transposed graph
    for (int i = 0; i < V; i++) gT->visited[i] = 0;
    printf("Strongly Connected Components:\n");
    for (int i = stackIndex - 1; i >= 0; i--) {
        if (!gT->visited[stack[i]]) {
            dfsSCC(gT, stack[i]);
            printf("\n");
        }
    }
}

int main() {
    struct Graph g, gT;
    initGraph(&g);
    initGraph(&gT);
    addEdge(&g, 1, 0); addEdge(&gT, 0, 1);
    addEdge(&g, 0, 2); addEdge(&gT, 2, 0);
    addEdge(&g, 2, 1); addEdge(&gT, 1, 2);
    addEdge(&g, 0, 3); addEdge(&gT, 3, 0);
    addEdge(&g, 3, 4); addEdge(&gT, 4, 3);
    kosaraju(&g, &gT); // Output: Strongly Connected Components: 0 1 2, 3, 4
    freeGraph(&g);
    freeGraph(&gT);
    return 0;
}
      

9. What are the time and space complexities of Kosaraju’s Algorithm?

• Time Complexity: O(V + E) (two DFS passes).
• Space Complexity: O(V) (stack and visited arrays).

10. What is Tarjan’s Algorithm for SCCs?

Tarjan’s Algorithm finds SCCs in a single DFS pass by maintaining a stack and tracking discovery times and low-link values to identify strongly connected components.

11. How does Tarjan’s Algorithm work?

• Perform DFS, maintaining a stack of vertices and assigning discovery and low-link values.
• Update low-link values based on neighbors and back edges.
• When a vertex’s discovery time equals its low-link value, pop vertices from the stack to form an SCC.

12. Can you give an example of Tarjan’s Algorithm in C?

Example: Finding SCCs in a directed graph with 5 vertices and edges (1→0, 0→2, 2→1, 0→3, 3→4).

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

#define V 5
#define min(a, b) ((a) < (b) ? (a) : (b))

struct Node {
    int vertex;
    struct Node* next;
};

struct Graph {
    struct Node* adjList[V];
    int visited[V];
};

void initGraph(struct Graph* g) {
    for (int i = 0; i < V; i++) {
        g->adjList[i] = NULL;
        g->visited[i] = 0;
    }
}

void addEdge(struct Graph* g, int src, int dest) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->vertex = dest;
    newNode->next = g->adjList[src];
    g->adjList[src] = newNode;
}

void freeGraph(struct Graph* g) {
    for (int i = 0; i < V; i++) {
        struct Node* temp = g->adjList[i];
        while (temp) {
            struct Node* next = temp->next;
            free(temp);
            temp = next;
        }
    }
}

void tarjanDFS(struct Graph* g, int v, int* disc, int* low, int* stack, int* stackIndex, int* time) {
    disc[v] = low[v] = ++(*time);
    stack[(*stackIndex)++] = v;
    g->visited[v] = 1;
    
    struct Node* temp = g->adjList[v];
    while (temp) {
        int u = temp->vertex;
        if (!disc[u]) {
            tarjanDFS(g, u, disc, low, stack, stackIndex, time);
            low[v] = min(low[v], low[u]);
        } else if (g->visited[u]) {
            low[v] = min(low[v], disc[u]);
        }
        temp = temp->next;
    }
    
    if (disc[v] == low[v]) {
        printf("SCC: ");
        while (*stackIndex > 0) {
            int w = stack[(*stackIndex) - 1];
            (*stackIndex)--;
            printf("%d ", w);
            g->visited[w] = 0;
            if (w == v) break;
        }
        printf("\n");
    }
}

void tarjan(struct Graph* g) {
    int disc[V] = {0}, low[V] = {0}, stack[V], stackIndex = 0, time = 0;
    for (int i = 0; i < V; i++) {
        if (!disc[i]) {
            tarjanDFS(g, i, disc, low, stack, &stackIndex, &time);
        }
    }
}

int main() {
    struct Graph g;
    initGraph(&g);
    addEdge(&g, 1, 0);
    addEdge(&g, 0, 2);
    addEdge(&g, 2, 1);
    addEdge(&g, 0, 3);
    addEdge(&g, 3, 4);
    printf("Strongly Connected Components:\n");
    tarjan(&g); // Output: SCC: 4, 3, 0 1 2 (order may vary)
    freeGraph(&g);
    return 0;
}
      

13. What are the time and space complexities of Tarjan’s Algorithm?

• Time Complexity: O(V + E) (single DFS pass).
• Space Complexity: O(V) (stack, discovery, and low-link arrays).

14. How do Kosaraju’s and Tarjan’s Algorithms compare?

• Kosaraju’s: Two DFS passes, needs transposed graph, simpler to understand.
• Tarjan’s: Single DFS pass, more space-efficient, more complex logic.

15. What are the applications of SCCs?

• Finding cycles in directed graphs.
• Analyzing network connectivity (e.g., social networks).
• Simplifying graphs for further processing (e.g., meta-graphs).

16. What is the Network Flow problem?

The Network Flow problem involves finding the maximum flow from a source to a sink in a directed graph with edge capacities, used in applications like traffic flow or matching.

17. What is the Ford-Fulkerson Algorithm?

Ford-Fulkerson finds the maximum flow by repeatedly finding augmenting paths (paths from source to sink with available capacity) and pushing flow until no such paths exist. It uses DFS or BFS (e.g., Edmonds-Karp with BFS).

18. Can you give an example of Ford-Fulkerson in C (using DFS)?

Example: Computing maximum flow in a flow network with 6 vertices and given capacities.

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define V 6
#define min(a, b) ((a) < (b) ? (a) : (b))

bool dfs(int residual[V][V], int s, int t, int parent[], int visited[]) {
    visited[s] = 1;
    if (s == t) return true;
    for (int v = 0; v < V; v++) {
        if (!visited[v] && residual[s][v] > 0) {
            parent[v] = s;
            if (dfs(residual, v, t, parent, visited)) return true;
        }
    }
    return false;
}

int fordFulkerson(int graph[V][V], int s, int t) {
    if (s < 0 || t < 0 || s >= V || t >= V) return -1; // Invalid source/sink
    int residual[V][V];
    memcpy(residual, graph, sizeof(residual)); // Copy graph
    int parent[V], max_flow = 0;
    
    while (true) {
        int visited[V] = {0};
        if (!dfs(residual, s, t, parent, visited)) break;
        
        int path_flow = 1000000; // Large number for min capacity
        for (int v = t; v != s; v = parent[v]) {
            int u = parent[v];
            path_flow = min(path_flow, residual[u][v]);
        }
        
        for (int v = t; v != s; v = parent[v]) {
            int u = parent[v];
            residual[u][v] -= path_flow; // Update forward edge
            residual[v][u] += path_flow; // Update reverse edge
        }
        max_flow += path_flow;
    }
    return max_flow;
}

int main() {
    int graph[V][V] = {
        {0, 16, 13, 0, 0, 0},
        {0, 0, 10, 12, 0, 0},
        {0, 4, 0, 0, 14, 0},
        {0, 0, 9, 0, 0, 20},
        {0, 0, 0, 7, 0, 4},
        {0, 0, 0, 0, 0, 0}
    };
    int result = fordFulkerson(graph, 0, 5);
    if (result == -1) {
        printf("Invalid input\n");
    } else {
        printf("Maximum Flow: %d\n", result); // Output: Maximum Flow: 23
    }
    return 0;
}
      

19. What are the time and space complexities of Ford-Fulkerson?

• Time Complexity:
  • With DFS: O(E * |f|) (E = edges, |f| = max flow, can be slow).
  • With BFS (Edmonds-Karp): O(V * E²).
• Space Complexity: O(V + E) (residual graph and parent array).

20. What are the applications of Ford-Fulkerson?

• Maximum flow in networks (e.g., traffic, water flow).
• Bipartite matching.
• Minimum cut analysis.

21. What are the advantages and disadvantages of Ford-Fulkerson?

• Advantages: Versatile, works for any flow network.
• Disadvantages: Slow with DFS for large flows; use Edmonds-Karp for better performance.