AIM : To obtain the Topological ordering of vertices in a given digraph.

DESCRIPTION :

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering.Topological Sorting for a graph is not possible if the graph is not a DAG. Input parameters: int a[MAX][MAX] - adjacency matrix of the input graph int n - no of vertices in the graph

ALGORITHM :

L Empty list that will contain the sorted elements S Set of all nodes with no incoming edges while S is non-empty do remove a node n from S add n to tail of L for each node m with an edge e from n to m do remove edge e from the graph if m has no other incoming edges then insert m into S if graph has edges then return error (graph has at least one cycle) else return L (a topologically sorted order)

CODE :

#include <stdio.h>

const int MAX = 10;
void fnTopological(int a[MAX][MAX], int n);
int main(void)
{
    int a[MAX][MAX],n;
    int i,j;

    printf("Topological Sorting Algorithm -\n");
    printf("\nEnter the number of vertices : ");
     scanf("%d",&n);

    printf("Enter the adjacency matrix -\n");
    for (i=0; i<n; i++) 
        for (j=0; j<n; j++)
            scanf("%d",&a[i][j]);

    fnTopological(a,n);
    printf("\n");
    return 0;
}

void fnTopological(int a[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 (a[j][i] == 1)
                in[i]++;
    }

    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 (a[out[k]][i] == 1)
                in[i]--;
        }
        k++;
    }

    printf("Topological Sorting (JOB SEQUENCE) is:- \n");
    for (i=0;i<k;i++)
        printf("%d ",out[i] + 1);
}

OUTPUT

Input Graph : 5 vertices 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