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