What is topological sort?

Topological sort is a sorting technique that sets up a hierarchy in a process. In this technique, when a directed network has nodes connected by arrows, the root node is placed before the successor node.

A root node is the one from which arrows arise. The nodes to which the arrows point are called successor nodes. Based on this root-first principle, topological sorting is done. The algorithms written for the topological sort are known as topological sort algorithms.

The topological sort algorithm returns an array of nodes for a directed graph. The node that has the minimum number of arrows comes first. The order in which nodes appear in topological sort is called topological ordering.

What is topological sort for Directed Acyclic Graph?

Topological sort produces an array of nodes or vertices in descending order of the number of arrows directed towards nodes. Hence, topological sorting is possible only for acyclic graphs as the first node of the array should have an in-degree zero. A graph having at least one vertex with in-degree zero is called a Directed Acyclic Graph (DAG).

Consider the directed acyclic graph given below.

The graph “5 4 2 3 1 0” is a topological sort. As both 4 and 5 are in in-degree zero, another possible topological sort is “4 5 2 3 1 0”.

Note that an in-degree zero vertex has no incoming arrows or edges.

Let’s understand it better through the following example:

Vertex 1 is in in-degree zero, so it appears first in the array. Vertex 1 is followed by vertices 2, 3, 4, and then 5. Thus, the topological order of the given graph is as shown below:

There can be two topological orders for the system—[1, 2, 3, 4, 5] and [1, 3, 2, 4, 5].

Note:

• You need a DAG for topological sorting.
• For a DAG, more than one topological sort is possible.
• A vertex that has in-degree zero comes first in the topological order.

Cyclic graphs

A directed graph in which a cycle appears, or there is only one node with both incoming and outgoing edges, is called a cyclic graph.

• A graph that does not contain a cycle is called an acyclic graph.
• A cyclic graph with exactly one unidirectional cycle is called a unicyclic graph.
• A cyclic graph does not have a valid topological order.

Directed Acyclic Graph (DAG): Topological Ordering

The nodes or vertices of a directed graph are connected through arrows called edges. These edges run from one vertex to another. A directed graph that does not have a cycle is called a directed acyclic graph. No node in a directed acyclic path contains both incoming and outgoing edges.

The following is the representation of directed graphs with and without cycles.

• Directed graph with cycles

• Directed graph without cycles

Note: Directed graphs without cycles are called DAGs.

Depth-First Search (DFS)

Depth-First Search (DFS) is an uninformed search technique that allows backtracking. It uses a recursive algorithm. DFS starts with the first node of the tree and moves ahead. And if the node is not required according to the current path, it can go back, which is called backtracking.

While moving backward to find nodes for the next path, it touches all the nodes of the current path till it traverses all the untouched ones. This process helps to select the next path.

Using stacks, you can implement the recursive nature of DFS. The basic idea of the stack is as follows:

• Select the in-degree zero node, and keep all the remaining nodes in a stack.
• Pick the next node in the array of order while keeping the rest in the stack.
• Repeat the process until all the nodes are picked from the stack.

Topological Sorting vs Depth-First Search (DFS):   

Let’s discuss the basic differences between topological sort and depth-first search.

Let us consider the below graph:

The topological ordering of the graph is [5 4 2 3 1 0] whereas the DFS will return [5 2 3 1 0 4].

Algorithm to find Topological Sorting

The steps to produce the topological order for any directed graph are listed below:

• The first node in topological ordering is always an in-degree zero node. So, you need to find a node that has no edges coming into it.
• Remove the node chosen in the topological order and its outgoing edges  from the graph.
• Add the next in-degree zero node in the topological order.
• Remove the node and the outgoing edges, and repeat the process until you reach the last node.

Consider the following graph:

• Look for an in-degree zero node and add it to the order. Here, B is the in-degree zero vertex. It will come first in the topological order array.

• Remove the graph of B and its outgoing edges to get the next in-degree zero node.

• Similarly, E and C are in-degree zeros. As there can be more than one topological order for a graph, choose any of E and C.

• Repeat the process to get the next in-degree zero vertex.

• Pick the next node and repeat the process.

• Repeat the process until you reach the last node.

Hence, the topological order of the graph is [B E A C D].

Time and space complexity

For obtaining an optimal algorithm, you should consider time and space complexity. There are various ways to design an algorithm. However, the most efficient ones are those that take less time to execute and occupy minimum space. In this section, you’ll understand time and space complexity one by one. 

Time complexity

The time complexity of an algorithm is its execution time as a function. For huge input sizes and worst-case scenarios, the time complexity is examined. The time taken by an algorithm can be controlled by following the given points while writing the algorithm.

• For each node in the graph, the in-degree zero is determined. The time taken in the process is referred to as the O(E) time. Here, E represents the number of edges.
• The process of determining the in-degree zero requires going through each node. The time taken for this is referred to as the V(N) time. Here, N represents the number of nodes.
• The time complexity is the sum of the time taken in passing through each node and path. It is represented as O(E) + V(N).

Space complexity

Space complexity is the space or memory occupied by the process in the system when it is executed as a function. The space occupied depends on the number of vertices in the graph. If there are N nodes and each takes one unit space, then O(N) is the space complexity of the graph system.

Applications of topological sort

Topological sort is used in

• scheduling tasks for jobs,
• designing hierarchy for systems,
• determining the priority list of files, and
• serializing data.

Common Mistakes

Remember the following points while doing topological sort of a graph:

• Make sure that the graph provided is not cyclic.
• In the case of more than one topological sort, do not get confused; it is possible.

Formulas

• Time complexity is O(M+N), where M is the number of nodes and N is the number of edges in the graph.
• The complexity of space is O(N), where N denotes the number of nodes.

Context and Applications

This topic is significant in the professional exams for both graduate and postgraduate courses,
especially for

Bachelor in Computer Science

Bachelor in Computer Application

Bachelor of Technology in Computer Science and Engineering

Master in Computer Application

Master of Technology in Computer Science and Engineering

Related Concepts

Selection Sort

Bubble Sort

Insertion Sort

Merge Sort

Practice Problems

Q. 1 Topological sort is applicable on:

(A) Direct Cyclic Graph

(B) Directed Acyclic Graph

(C) Both A and B

(D) None of the above

Correct Option: (B)

Q. 2 Topological sort finds:

(A) In-degree zero vertex

(B) In-degree one vertex

(C) Aligned vertex

(D) None of the above

Correct Option: (A)

Q. 3 Which of the following is not a sorting type in the database management system?

(A) Topological Sort

(B) Quick Sort

(C) Bubble Sort

(D) First Sort

Correct Option: (D)

Q. 4 A cyclic graph having exactly one unidirectional cycle is called a/an:

(A) Acyclic graph

(B) Unicyclic graph

(C) First cycle graph

(D) None of the above

Correct Option: (B)

Q. 5 Topological sort returns:

(A) An array

(B) A word

(C) A string

(D) A file

Correct Option: (A)