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.

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.

 

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

Output

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.

Sorting Algorithms
C Program For Quick Sort Algorithm
C Program For Shell Sort Algorithm
C Program For Address Calculation Sort Algorithm
C Program For Insertion Sort Algorithm
C Program For Selection Sort Algorithm
C Program To Find Shortest Path using Bellman Ford Algorithm
C Program For Bubble Sort Algorithm
C Program For Heap Sort Algorithm using Heapify
C Program For Prim’s Algorithm
C Program For Counting Sort Algorithm
C Program For Queue Data Structure using Array

4 thoughts on “Topological Sort Algorithm C Program

  1. Vishal Mehta

    What are the real world applications of Topological Sort Algorithm?

    Reply
    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

      Reply
  2. Vinayak Vashishth

    Thanks for this Topological Sorting Algorithm C Program.

    Reply
  3. Mahesh Ghadge

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

    Reply

Let's Discuss