Program
#include <stdio.h>
#include<conio.h>
void findIndegree(int[10][10], int[10], int);
void topological(int, int[10][10]);
void main()
{
int a[10][10], i, j, n;
printf("*********************************************************");
printf("\n*********************************************************");
printf("\n** WAP to find topological sorting of a graph in C **");
printf("\n** Created by Sheetal Garg **");
printf("\n** Assistant Professor **");
printf("\n** Phone No:9467863365 **");
printf("\n*********************************************************");
printf("\n*********************************************************");
printf("\nEnter the number of nodes:");
scanf("%d", &n);
printf("\nEnter the adjacency matrix\n");
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
}
printf("\nThe adjacency matrix is:\n");
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
printf("%d\t", a[i][j]);
}
printf("\n");
}
topological(n, a);
getch();
}
void findIndegree(int a[10][10], int indegree[10], int n)
{
int i, j, sum;
for (j = 1; j <= n; j++)
{
sum = 0;
for (i = 1; i <= n; i++)
{
sum = sum + a[i][j];
}
indegree[j] = sum;
}
}
void topological(int n, int a[10][10])
{
int k, top, t[100], i, stack[20], u, v, indegree[20];
k = 1;
top = -1;
findIndegree(a, indegree, n);
for (i = 1; i <= n; i++)
{
if (indegree[i] == 0)
{
stack[++top] = i;
}
}
while (top != -1)
{
u = stack[top--];
t[k++] = u;
for (v = 1; v <= n; v++)
{
if (a[u][v] == 1)
{
indegree[v]--;
if (indegree[v] == 0)
{
stack[++top] = v;
}
}
}
}
printf("\nTopological sequence is\n");
for (i = 1; i <= n; i++)
printf("%d\t", t[i]);
}
Output 1
********************************************************* ********************************************************* ** WAP to find topological sorting of a graph in C ** ** Created by Sheetal Garg ** ** Assistant Professor ** ** Phone No:9467863365 ** ********************************************************* ********************************************************* Enter the number of nodes:4 Enter the adjacency matrix 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 The adjacency matrix is: 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 Topological sequence is 1 2 4 3