Topological sorting is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u → v, vertex u comes before v in the ordering. This is useful in scenarios like task scheduling where certain tasks must be completed before others.

Program Structure

The following C program implements topological sorting using Kahn’s algorithm, which relies on the concept of in-degree of vertices. The program consists of the following parts:

• Graph Representation: We represent the graph using an adjacency list.
• In-degree Calculation: We calculate the in-degrees of all vertices.
• Topological Sort Function: We implement the main logic to perform the topological sort.
• Main Function: It initializes the graph and calls the topological sort function.

C Program

#include 
#include 

#define MAX_VERTICES 100

typedef struct {
    int adj[MAX_VERTICES][MAX_VERTICES];
    int num_vertices;
} Graph;

void initialize_graph(Graph* g, int vertices) {
    g->num_vertices = vertices;
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) { g->adj[i][j] = 0;
        }
    }
}

void add_edge(Graph* g, int start, int end) {
    g->adj[start][end] = 1;
}

void topological_sort(Graph* g) {
    int in_degree[MAX_VERTICES] = {0};
    int sorted[MAX_VERTICES];
    int index = 0;

    // Calculate in-degrees
    for (int i = 0; i < g->num_vertices; i++) {
        for (int j = 0; j < g->num_vertices; j++) {
            if (g->adj[j][i]) {
                in_degree[i]++;
            }
        }
    }

    // Queue to manage vertices with zero in-degree
    int queue[MAX_VERTICES], front = 0, rear = 0;

    for (int i = 0; i < g->num_vertices; i++) {
        if (in_degree[i] == 0) {
            queue[rear++] = i;
        }
    }

    while (front < rear) {
        int current = queue[front++];

        // Add current vertex to sorted array
        sorted[index++] = current;

        for (int i = 0; i < g->num_vertices; i++) {
            if (g->adj[current][i]) {
                in_degree[i]--;
                if (in_degree[i] == 0) {
                    queue[rear++] = i;
                }
            }
        }
    }

    // Print sorted vertices
    printf("Topological Sort Order: ");
    for (int i = 0; i < index; i++) {
        printf("%d ", sorted[i]);
    }
    printf("\n");
}

int main() {
    Graph g;
    initialize_graph(&g, 6);

    add_edge(&g, 5, 2);
    add_edge(&g, 5, 0);
    add_edge(&g, 4, 0);
    add_edge(&g, 4, 1);
    add_edge(&g, 2, 3);
    add_edge(&g, 3, 1);

    topological_sort(&g);
    
    return 0;
}

How to Compile and Run

To compile and run the program:

1. Save the code in a file named topological_sort.c.
2. Open a terminal and navigate to the directory containing the file.
3. Compile the program using gcc topological_sort.c -o topological_sort.
4. Run the program using ./topological_sort.

Conclusion

This program provides a straightforward implementation of topological sorting using Kahn’s algorithm. Understanding how to manipulate graph data structures is essential for solving complex problems in computer science.