Topological Sort Algorithm C Program

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.

Must Read: C Program To Implement Depth First Search Algorithm

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.

Must Read: C Program For Queue Data Structure using Array

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.

Implementation of Topological Sorting Algorithm in C Programming for Directed Acyclic Graph

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.

Must Read: C Program For Prim’s Algorithm

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

Must Read: C Program To Find Shortest Path using Bellman Ford Algorithm


C Program For Topological Sort Algorithm For Directed Acyclic Graphs using Adjacency Matrix

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.

Tushar Soni

I am Tushar Soni, Co - Founder of CodingAlpha. I am a computer science student from India and passionate about Web Development and Programming. Connect with me on Facebook | LinkedIn | Google Plus

4 thoughts on “Topological Sort Algorithm C Program

  • October 1, 2016 at 8:01 pm

    What are the real world applications of Topological Sort Algorithm?

    • October 1, 2016 at 8:05 pm

      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

  • October 1, 2016 at 11:40 pm

    Thanks for this Topological Sorting Algorithm C Program.

  • October 2, 2016 at 7:23 pm

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


Join The Discussion