# C Program to Create a Random Linear Extension for a DAG

«
»
This is a C Program to find topological sorting of a graph. For example:a1 < a0, a1 < a2 < a3. The problem is to determine a list of order, in which if ai < aj then ai will come before aj in the final sorted list. For example, our list could be : a1, a0, a2, a3 or a1, a2, a0, a3 or a1, a2, a3, a0 Any partial ordered list can be sorted topological. For a graph, a topological sort of a directed graph refers to an ordering of the vertices, that for every edge u,v, u comes before v in the ordering. Here is source code of the C Program to Create a Random Linear Extension for a DAG. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
1. `#include<stdio.h>`
2. `#include<math.h>`
3. `int main() {`
4. `    int i, j, k, n, a, indeg, flag, count = 0;`
5. `    printf("Enter the no of vertices:");`
6. `    scanf("%d", &n);`
7. `    printf("Enter the incidence matrix:");`
8. `    for (i = 0; i < n; i++)`
9. `        for (j = 0; j < n; j++)`
10. `            scanf("%d", &a[i][j]);`
11. ` `
12. `    for (i = 0; i < n; i++) {`
13. `        indeg[i] = 0;`
14. `        flag[i] = 0;`
15. `    }`
16. `    for (i = 0; i < n; i++)`
17. `        for (j = 0; j < n; j++)`
18. `            indeg[i] = indeg[i] + a[j][i];`
19. `    printf("The topological order is:");`
20. `    while (count < n) {`
21. `        for (k = 0; k < n; k++) {`
22. `            if ((indeg[k] == 0) && (flag[k] == 0)) {`
23. `                printf("%d ", (k + 1));`
24. `                flag[k] = 1;`
25. `            }`
26. `            for (i = 0; i < n; i++) {`
27. `                if (a[i][k] == 1)`
28. `                    indeg[k]--;`
29. `            }`
30. `        }`
31. `        count++;`
32. `    }`
33. `    return 0;`
34. `}`

Output:

```\$ gcc LinearExtensionOfDAG.c
\$ ./a.out

Enter the no of vertices:6
Enter the incidence matrix:
0 1 0 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 1 1
0 0 0 0 0 1
0 0 1 1 0 0
The topological order is:
1 2 3 4 5 6```

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data Structures and Algorithms. 