Design and implement C/C++ Program to obtain the Topological ordering of vertices in a given digraph
#include<stdio.h>
int temp[10], k = 0; // Global array to store the topologically sorted nodes and a counter
void sort(int a[][10], int id[], int n)
{
int i, j;
for (i = 1; i <= n; i++) {
if (id[i] == 0) { // Find nodes with no incoming edges
id[i] = -1; // Mark node as visited
temp[++k] = i; // Add node to the sorted list
for (j = 1; j <= n; j++) {
if (a[i][j] == 1 && id[j] != -1)
id[j]--; // Decrease the incoming edge count for adjacent nodes
}
i = 0; // Reset i to 0 to start from the beginning of the graph again
}
}
}
void main() {
int a[10][10], id[10], n, i, j;
printf("\nEnter the n value: ");
scanf("%d", &n);
for (i = 1; i <= n; i++)
id[i] = 0; // Initialize incoming edge count for all nodes to 0
printf("\nEnter the graph data (1 for connected, 0 for not connected):\n");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++) {
scanf("%d", &a[i][j]);
if (a[i][j] == 1)
id[j]++; // Increment incoming edge count for node j
}
sort(a, id, n); // Perform topological sorting
if (k != n)
printf("\nTopological ordering not possible");
else {
printf("\nTopological ordering is: ");
for (i = 1; i <= k; i++)
printf("%d ", temp[i]); // Print the sorted nodes
}
}
OUTPUT
Enter the n value: 5
Enter the graph data (1 for connected, 0 for not connected):
0 1 0 0 0
0 0 1 0 1
0 0 0 1 0
0 0 0 0 1
0 0 0 0 0
Topological ordering is: 1 2 3 4 5