ADA Program 5

 5. Topological Sorting (Kahn’s Method)

#include <stdio.h>

#define MAX 10

void fnTopological(int a[MAX][MAX], int n);

int main(int argc, char **argv) {
    int graph[MAX][MAX],n;
    int i,j;
    printf("Topological Sorting Algorithm\n");
    printf("\n Enter the number of vertices : ");
    scanf("%d",&n);
    printf("Enter the adjacency matrix (graph should be a DAG) \n");
    for (i=0; i<n; i++)
        for (j=0; j<n; j++)
            scanf("%d",&graph[i][j]);
    fnTopological(graph,n);
    printf("\n");
    return 0;
}

void fnTopological(int graph[MAX][MAX], int n) {
    int in[MAX], out[MAX], stack[MAX], top=-1;
    int i,j,k=0;
    
    for (i=0;i<n;i++) {
        in[i] = 0;
        for (j=0; j<n; j++)
            if (graph[j][i] == 1)
                in[i]=in[i]+1;
    }
    
    while(1) {
        for (i=0;i<n;i++) {
            if (in[i] == 0) {
                stack[++top] = i;
                in[i] = -1;
            }
        }
        if (top == -1)
            break;
        
        out[k] = stack[top--];
        for(i=0;i<n;i++) {
            if (graph[out[k]][i] == 1)
                in[i]--;
        }
        k++;
    }
    printf("Topological Sorting (JOB SEQUENCE) is:-\n");
    for (i=0;i<k;i++)
        printf("%d\t", out[i] + 1);
    printf("\n");
}

Output
Enter the number of vertices :
5
Enter the adjacency matrix -
0 0 1 0 0
0 0 1 0 0
0 0 0 1 1
0 0 0 0 1
0 0 0 0 0
Topological Sorting (JOB SEQUENCE) is:-
2 1 3 4 5