# Topological Sort Algorithm C Program

By | October 1, 2016

## 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

1. Choose a vertex in a graph without any predecessors. In other words, it is a vertex with Zero Indegree.
2. Delete this vertex and all the outgoing edges from it.
3. 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.

#### 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.

## 4 thoughts on “Topological Sort Algorithm C Program”

1. Vishal Mehta

What are the real world applications of Topological Sort Algorithm?

1. Rohan Singhania

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

2. Vinayak Vashishth

Thanks for this Topological Sorting Algorithm C Program.

3. Mahesh Ghadge

What is the difference between indegree and outdegree in a graph?