C Program to Apply DFS to Perform the Topological Sorting of a Directed Acyclic Graph

This is a C Program to perform Topological Sorting. Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge pq, vertex p comes before q in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

Here is source code of the C Program to Apply DFS to Perform the Topological Sorting of a Directed Acyclic Graph. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<stdio.h>
```
```
#include<stdlib.h>
```
```
 
```

int s[100], j, res[100]; /*GLOBAL VARIABLES */

```
 
```

void AdjacencyMatrix(int a[][100], int n) { //To generate adjacency matrix for given nodes

```
 
```
```
    int i, j;
```
```
    for (i = 0; i < n; i++) {
```
```
        for (j = 0; j <= n; j++) {
```
```
            a[i][j] = 0;
```
```
        }
```
```
    }
```
```
    for (i = 1; i < n; i++) {
```
```
        for (j = 0; j < i; j++) {
```
```
            a[i][j] = rand() % 2;
```
```
            a[j][i] = 0;
```
```
        }
```
```
    }
```
```
}
```
```
 
```

void dfs(int u, int n, int a[][100]) { /* DFS */

```
 
```
```
    int v;
```
```
    s[u] = 1;
```
```
    for (v = 0; v < n - 1; v++) {
```

        if (a[u][v] == 1 && s[v] == 0) {

```
            dfs(v, n, a);
```
```
        }
```
```
    }
```
```
    j += 1;
```
```
    res[j] = u;
```
```
}
```
```
 
```

void topological_order(int n, int a[][100]) { /* TO FIND TOPOLOGICAL ORDER*/

```
 
```
```
    int i, u;
```
```
    for (i = 0; i < n; i++) {
```
```
        s[i] = 0;
```
```
    }
```
```
    j = 0;
```
```
    for (u = 0; u < n; u++) {
```
```
        if (s[u] == 0) {
```
```
            dfs(u, n, a);
```
```
        }
```
```
    }
```
```
    return;
```
```
}
```
```
int main() {
```
```
    int a[100][100], n, i, j;
```
```
 
```

    printf("Enter number of vertices\n"); /* READ NUMBER OF VERTICES */

```
    scanf("%d", &n);
```
```
 
```

    AdjacencyMatrix(a, n); /*GENERATE ADJACENCY MATRIX */

```
 
```

    printf("\t\tAdjacency Matrix of the graph\n"); /* PRINT ADJACENCY MATRIX */

```
    for (i = 0; i < n; i++) {
```
```
        for (j = 0; j < n; j++) {
```
```
            printf("\t%d", a[i][j]);
```
```
        }
```
```
        printf("\n");
```
```
    }
```
```
    printf("\nTopological order:\n");
```
```
 
```
```
    topological_order(n, a);
```
```
 
```
```
    for (i = n; i >= 1; i--) {
```
```
        printf("-->%d", res[i]);
```
```
    }
```
```
    return 0;
```
```
}
```

Output:

$ gcc TopologicalSorting.c
$ ./a.out
 
Enter number of vertices: 6
 
Adjacency Matrix of the graph
	0	0	0	0	0	0
	1	0	0	0	0	0
	1	0	0	0	0	0
	0	1	0	0	0	0
	0	0	0	0	0	0
	1	1	1	1	1	0
 
Topological order:
-->5-->4-->3-->2-->1-->0

Sanfoundry Global Education & Learning Series – 1000 C Programs.

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

« Prev - C Program to Find Shortest Path using Dijkstra’s Algorithm

» Next - C Program to Find the Vertex Connectivity of a Graph

Related Posts:

Recommended Articles: