C Program To Implement Topological Sort Algorithm
Learn How To Implement Topological Sort Algorithm in C Programming Language. This Topological Sort Algorithm for Directed Acyclic Graphs is developed using Adjacency Matrix and Queue. This algorithm follows greedy algorithm approach.
What is a Directed Acyclic Graph?
A Directed Acyclic Graph is also famously known as DAG. It does not contain any cycles in it. It is, therefore, a finite directed graph without any directed cycles. A DAG consists of many Edges and Vertices where each edge is directed from one vertex to another vertex.
What is Topological Sorting Algorithm?
The topological sorting algorithm is basically linear ordering of the vertices of the graph in a way that for every edge ab from vertex a to b, the vertex a comes before the vertex b in the topological ordering. In other words, the topological sorting of a Directed Acyclic Graph is linear ordering of all of its vertices.
The sequence of vertices in linear ordering is known as topological sequence or topological order. There may be more than one topological sequences for a given graph.
Topological Sort is also sometimes known as Topological Ordering. The topological sorting is possible only if the graph does not have any directed cycle. In other words, a topological ordering is possible only in acyclic graphs.
Algorithm For Topological Sorting Sequence
- Choose a vertex in a graph without any predecessors. In other words, it is a vertex with Zero Indegree.
- Delete this vertex and all the outgoing edges from it.
- Repeat the above process till all the vertices are not deleted from the DAG.
Initially, calculate the indegree of all the vertices in the graph and the add the vertex with zero indegree vertices into the empty queue. When a vertex from the queue is deleted then it is copied into the topological_sort array. The outgoing edges are then deleted and the indegrees of its successors are decreased by 1. A vertex is pushed into the queue through front as soon as its indegree becomes 0. Now, this process continues till all the vertices in the graph are not deleted.
If in between the topological sort algorithm process, a situation occurs where no vertex is left with zero indegree and all the vertices in the graph have predecessors, then it indicates that the graph is cyclic.
C Program To Implement Topological Sort Algorithm using Directed Acyclic Graphs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 | #include<stdio.h> #include<stdlib.h> #define MAX 100 void create_graph(); void add(int vertex); int del(); int isEmpty(); int find_indegree_of_vertex(int vertex); int total_vertices; int adjacent_matrix[MAX][MAX]; int queue[MAX]; int front = -1; int rear = -1; int main() { int i, vertex, count, topological_sort[MAX], indegree[MAX]; create_graph(); for(i = 0; i < total_vertices; i++) { indegree[i] = find_indegree_of_vertex(i); if(indegree[i] == 0) { add(i); } } count = 0; while(!isEmpty() && count < total_vertices) { vertex = del(); topological_sort[++count] = vertex; for(i = 0; i < total_vertices; i++) { if(adjacent_matrix[vertex][i] == 1) { adjacent_matrix[vertex][i] = 0; indegree[i] = indegree[i] - 1; if(indegree[i] == 0) { add(i); } } } } if(count < total_vertices) { printf("Graph is Cyclic. Therefore, Topological Ordering Not Possible\n"); exit(1); } printf("Topological Order of Vertices\n"); for(i = 1; i <= count; i++) { printf("%3d", topological_sort[i]); } printf("\n"); return 0; } void add(int vertex) { if(rear == MAX - 1) { printf("Queue Overflow\n"); } else { if(front == -1) { front = 0; } rear = rear + 1; queue[rear] = vertex ; } } int isEmpty() { if(front == -1 || front > rear) { return 1; } else { return 0; } } int del() { int element; if(front == -1 || front > rear) { printf("Queue Underflow\n"); exit(1); } else { element = queue[front]; front = front + 1; return element; } } int find_indegree_of_vertex(int vertex) { int count, total_indegree = 0; for(count = 0; count < total_vertices; count++) { if(adjacent_matrix[count][vertex] == 1) { total_indegree++; } } return total_indegree; } void create_graph() { int count, maximum_edges, origin_vertex, destination_vertex; printf("Enter number of vertices:\t"); scanf("%d", &total_vertices); maximum_edges = total_vertices * (total_vertices - 1); for(count = 1; count <= maximum_edges; count++) { printf("Enter Edge [%d] co-ordinates (-1 -1 to quit)\n", count); printf("Enter Origin Vertex:\t"); scanf("%d", &origin_vertex); printf("Enter Destination Vertex:\t"); scanf("%d", &destination_vertex); if((origin_vertex == -1) && (destination_vertex == -1)) { break; } if(origin_vertex >= total_vertices || destination_vertex >= total_vertices || origin_vertex < 0 || destination_vertex < 0) { printf("Edge Co-ordinates are Invalid\n"); count--; } else adjacent_matrix[origin_vertex][destination_vertex] = 1; } } |
Output
In case you get any Compilation Errors or any doubts in this code for Topological Sorting Algorithm in C Programming, let us know about it in the Comment Section below. Find more about Topological Sorting on GeeksForGeeks.
What are the real world applications of Topological Sort Algorithm?
Some of its real world applications may be:
1. Maven Dependency Resolution
2. Data Serialization
3. Graph Drawing Solutions
4. Job Scheduling
5. Resolving Dependencies
Thanks for this Topological Sorting Algorithm C Program.
What is the difference between indegree and outdegree in a graph?