Topological Sorting - Naukri Code 360

Introduction

Topological sorting is a fundamental algorithm in computer science used to sort directed acyclic graphs (DAGs) in a specific order. It is important in several domains, including software engineering, task scheduling, dependency resolution, and graph theory. This article will discuss an overview of topological Sorting, its implementation, and its applications. We will also compare topological sorting with other sorting algorithms. So fasten your seat belt, and let’s get started!

What is Topological Sorting?

Topological sorting is an algorithm that sorts the vertices of a directed acyclic graph (DAG) in a specific order to satisfy all dependencies. This algorithm is commonly used in several domains, such as task scheduling, software engineering, dependency resolution, and graph theory.

The implementation of topological sorting is based on the depth-first search technique. The algorithm requires a DAG as input. The output of the algorithm is a linear ordering of the vertices such that if there is an edge from vertex A to vertex E, then vertex A comes before vertex E in the ordering. See the above diagram. Topological sorting is only applicable to DAGs and cannot be used to sort cyclic graphs.

Topological Sort Example

Consider the following graph to understand the working of the topological sort algorithm.

As you can see from the above diagram, how we are removing edges from vertices to accomplish topological sort. We will start by selecting the vertex with no incoming edge. Now, we will delete all outgoing edges from it. Afterwards, we will check whether a vertex has associated edges. If there is, then we will select it and remove it. We will do these steps until we are left with only 1 vertex. At last, when we are left with 1 vertex, the path of removal we followed to achieve this state is one of the possible orders of the topological sort and hence the answer.

Algorithms for Topological Sorting

There are two algorithms to find the topological sorting order of the graph:-

Depth-first search algorithm
Kahn's Algorithm.

1. Depth-First Search Algorithm

Depth-First Search (DFS Algorithm) can be used for Topological Sort by visiting each node in the graph and recursively visiting its unvisited neighbours. The nodes are added to the output list in reverse order of their finishing times, which gives a valid topological ordering.

Here's the algorithm step by step:

The algorithm for Topological Sorting using Depth-First Search is as follows:

Create a Graph object with V vertices.
Add edges between vertices using the addEdge method.
Create a visited array of size V and initialise it to False.
Create an empty stack to store the topological sorting of the vertices.
For each vertex v in the graph:
1. If v is not visited, call the topologicalSortUtil method with v, visited, and stack.
In the topologicalSortUtil method:
1. Mark v as visited.
2. For each adjacent vertex i of v:
  1. If i is not visited, call topologicalSortUtil with i, visited, and stack.
3. Push v onto the stack.
Return the stack with the topological sorting of the vertices.

This algorithm performs a Depth-First Search on the graph and uses a stack to store the vertices in reverse order of finishing times. The topological sorting of the vertices is obtained by popping the vertices off the stack.

2. Kahn’s Algorithm

Kahn's topological sort algorithm finds vertices that have no inbound edges and removes all outgoing edges from these vertices.

Algorithm

Create a Graph class with a vector of adjacency lists and a vector to store the indegree of each vertex.
Initialize the adjacency list and indegree vector in the Graph constructor.
Implement a function TopologicalSort that takes a Graph object and returns a vector of integers representing the topological ordering of the vertices.
Inside the TopologicalSort function, create an empty vector L to hold the sorted vertices.
Get the total number of nodes in the graph n and the indegree vector from the input Graph object.
Create a set of all nodes with no incoming edges (indegree = 0) and add them to a vector S.
While the set S is not empty:
1. Remove a node n from the set S.
2. Add n to the tail of vector L.
3. For each node m that is adjacent to n in the graph:
  1. Remove the edge n -> m from the graph by decrementing the indegree of m.
  2. If the indegree of m is now zero, add m to the set S.
Check if there is a cycle in the graph by iterating over the indegree vector. If any element is non-zero, return an empty vector to indicate that the topological sorting is not possible.
Otherwise, return the vector L, which contains the topological ordering of the vertices.

Code Implementation of DFS Algorithm

C++ Implementation

C++

#include <bits/stdc++.h>
using namespace std;
class Graph {
    /*No. of vertices*/
    int V;
 
    /*adjacency list of the graph*/
    list<int>* adjacency;
    void topologicalSortmain(int v, bool visitedarray[],
                            stack<int>& Stack);
 
public:
    Graph(int V);
 
    /*adds an edge to the graph*/
    void addingEdge(int v, int w);
 
    /*gives us the topological sort of the graph*/
    void topologicalSort();
};
 
Graph::Graph(int V) /*making the graph*/
{
    this->V = V;
    adjacency = new list<int>[V];
}
 
void Graph::addingEdge(int v, int w)
{
    adjacency[v].push_back(w);
}
 
/*function used by topological sort*/
void Graph::topologicalSortmain(int vertex, bool visitedarray[],
                                stack<int>& Stack)
{ 
    visitedarray[vertex] = true;
 
    /*check for all vertices adjacent to this vertex*/
    list<int>::iterator k;
    for (k = adjacency[vertex].begin(); k != adjacency[vertex].end(); ++k)
        if (!visitedarray[*k])
            topologicalSortmain(*k, visitedarray, Stack);
 
    /*after reaching to this point,
    push the current vertex to stack*/
    Stack.push(vertex);
}
 
void Graph::topologicalSort()
{
    stack<int> Stack;
 
    /*initially mark all vertices as unvisited*/
    bool* visitedarray = new bool[V];
    for (int i = 0; i < V; i++)
        visitedarray[i] = false;
 
    for (int i = 0; i < V; i++)
        if (visitedarray[i] == false)
            topologicalSortmain(i, visitedarray, Stack);
 
    /*print the stack contents*/
    while (!Stack.empty()) {
        cout << Stack.top() << " ";
        Stack.pop();
    }
}
 
int main()
{
    // Create a graph given in the above diagram
    Graph g(6);
    g.addingEdge(1, 2);
    g.addingEdge(3, 2);
    g.addingEdge(1, 4);
    g.addingEdge(1, 0);
    g.addingEdge(3, 5);
    g.addingEdge(4, 5);
    cout << "Topological sort: ";
    g.topologicalSort();
 
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input:

Following is the input graph we used.

Output:

Python Implementation

Python

Python

from collections import defaultdict

class Graph:
    def __init__(self, totalvertices):
  #adjacency list
        self.graph = defaultdict(list)
  #total number of vertices
        self.V = totalvertices


    #adding edge to a graph
    def addingEdge(self, u, vertex):
        self.graph[u].append(vertex)

    def topologicalSortmain(self, vertex, visitedarray, stack):
#we’ll mark current array as visited 
        visitedarray[vertex] = True
        for k in self.graph[vertex]:
            if not visitedarray[k]:
                self.topologicalSortmain(k, visitedarray, stack)
        stack.insert(0, vertex)

    def topologicalSort(self):
        visitedarray = [False] * self.V
        stack = []
        for i in range(self.V):
            if not visitedarray[i]:
                self.topologicalSortmain(i, visitedarray, stack)
        stack.reverse()
        print(stack[::-1])

if __name__ == '__main__':
    # Example usage
    g = Graph(6)
    g.addingEdge(1, 2)
    g.addingEdge(3, 2)
    g.addingEdge(1, 4)
    g.addingEdge(1, 0)
    g.addingEdge(3, 5)
    g.addingEdge(4, 5)

    print("Topological Sort:")
    g.topologicalSort()

You can also try this code with Online Python Compiler

Run Code

Input:

Following is the input graph we used.

Output:

Explanation:

The Graph class contains an integer V that represents the number of vertices in the graph, a pointer to an adjacency list adjacency which stores the neighbours of each vertex, and three member functions: Graph(int V) which constructs a graph with V vertices, addingEdge(int v, int w) which adds an edge between vertices v and w, and topologicalSort() which performs the topological sort.

The Graph constructor initialises V and creates an adjacency list with V lists, one for each vertex. The addingEdge function adds an edge to the adjacency list of vertex v.

The topologicalSort function uses a stack to store the vertices in the order they are visited during the DFS. It first initialises a boolean visitedarray to mark all vertices as unvisited, then iterates over each vertex and calls the topologicalSortmain function on the vertex if it has not already been visited. The topologicalSortmain function performs the actual DFS and pushes the vertices onto the stack in reverse order, so the top of the stack will be the first vertex in the topological sort.

We are implementing stack using a list, it is because when a vertex is visited, and all its adjacent vertices are explored, the vertex is pushed onto the stack. However, the stack is implemented as a list, and items are added to the end of the list by default. In order to obtain the correct order of vertices, we need to insert the vertex at the beginning of the list so that the vertices with no incoming edges are at the top of the stack. Finally, the contents of the stack are printed in reverse order to obtain the topological sort.

The main function creates a Graph object with six vertices and adds edges between them. It then calls the topologicalSort function to obtain the topological sort, which is printed to the console.

Time Complexity

The algorithm performs a Depth-First Search on the graph, which takes O(V+E) time, where V is the number of vertices and E is the number of edges in the graph. In addition, the algorithm uses a stack to store the vertices in reverse order of finishing times, which takes O(V) time. Thus, the overall time complexity of the above algorithm is O(V+E).

Space Complexity

The algorithm uses a visited array of size V, a stack of size V, and a defaultdict to store the edges of the graph. Therefore, the overall space complexity of the above algorithm is O(V).

Code Implementation of Kahn's Algorithm

C++ Implementation

C++

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

// to store a graph edge
struct Edge {
  int source, destination;
};

class Graph {
  public:
    // a vector to represent an adjacency list
    vector < vector < int >> adjList;

  // to store indegree of a vertex
  vector < int > indegree;

  // Graph Constructor
  Graph(vector < Edge >
    const & edges, int n) {
    // resize the vector to hold `n` elements of type `vector<int>`
    adjList.resize(n);

    // initialize indegree
    vector < int > temp(n, 0);
    indegree = temp;

    // adding edges
    for (auto & edge: edges) {
      adjList[edge.source].pb(edge.destination);
      indegree[edge.destination]++;
    }
  }
};

// Function to perform a topological sort
vector < int > TopologicalSort(Graph
  const & graph) {
  vector < int > L;

  // get the total number of nodes in the graph
  int n = graph.adjList.size();

  vector < int > indegree = graph.indegree;

  // Set of all nodes with no incoming edges
  vector < int > S;
  for (int i = 0; i < n; i++) {
    if (!indegree[i]) {
      S.push_back(i);
    }
  }

  while (!S.empty()) {
    // removing node 
    int n = S.back();
    S.pop_back();

    // adding nodes at the tail
    L.pb(n);

    for (int m: graph.adjList[n]) {
      // remove an edge from the graph
      indegree[m] -= 1;
      if (!indegree[m]) {
        S.pb(m);
      }
    }
  }

  // to detect cycle
  for (int i = 0; i < n; i++) {
    if (indegree[i]) {
      return {};
    }
  }

  return L;
}

int main() {
  // vector of graph
  vector < Edge > edges = { {1, 2}, {3, 2}, {1, 4}, {1, 0}, {3, 5}, {4, 5} };

  // total number of nodes in the graph (labelled from 0 to 5)
  int n = 6;

  // building a graph from the edges
  Graph graph(edges, n);

  vector < int > L = TopologicalSort(graph);

  // print topological order
  cout << "Topological Sort: ";
  if (L.size()) {
    for (int i: L) {
      cout << i << " ";
    }
  } else {
    cout << "Graph has at least one cycle. Topological sorting is not possible";
  }

  return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input:

Following is the input graph we used.

Output:

Python Implementation

Python

Python

from collections import deque

class Graph:

	# to stores indegree of a vertex
	indegree = None

	# defining Constructor
	def __init__(self, edges, n):

		# A list to represent an adjacency list
		self.adjList = [[] for _ in range(n)]

		# initialize indegree 
		self.indegree = [0] * n

		# adding edges
		for (source, destination) in edges:

			self.adjList[source].append(destination)

			self.indegree[destination] = self.indegree[destination] + 1


# Function to do topological sort
def TopologicalSort(graph, n):

	L = []

	# getting indegree of the graph
	indegree = graph.indegree

	# Set of all nodes with no incoming edges
	S = deque([i for i in range(n) if indegree[i] == 0])

	while S:

		# removing nodes
		n = S.pop()

		# adding nodes at the tail
		L.append(n)

		for m in graph.adjList[n]:

			# remove an edge from the graph
			indegree[m] = indegree[m] - 1

			if indegree[m] == 0:
				S.append(m)

	# to detect cycle
	for i in range(n):
		if indegree[i]:
			return None

	return L


if __name__ == '__main__':

	# List of graph edges as per the above diagram
	edges = [(1, 2), (3, 2), (1, 4), (1, 0), (3, 5), (4, 5)]

	# total number of nodes in the graph (labelled from 0 to 5)
	n = 6

	# build a graph from the given edges
	graph = Graph(edges, n)

	# Perform topological sort
	L = TopologicalSort(graph, n)

	if L:
		print('Topological Sort: ',L)	# print topological order
	else:
		print('Graph has at least one cycle. Topological sorting is not possible.')

You can also try this code with Online Python Compiler

Run Code

Input:

Following is the input graph we used.

Output:

Explanation:

The code defines a struct Edge to store a graph edge consisting of a source and destination vertex. The Graph class has a vector of vectors to represent the adjacency list and another vector to store the indegree of each vertex. The constructor of the Graph class takes a vector of edges and the number of nodes in the graph. It initialises the adjacency list and calculates the indegree of each vertex. It then adds the edges to the adjacency list and increments the in-degree of the destination vertex.

The TopologicalSort function takes a constant reference to a Graph object and returns a vector of integers representing the topological sort order. It first initialises an empty list L to store the sorted vertices. It gets the total number of nodes in the graph and the in-degree vector from the graph. It initialises a set S with all the nodes with no incoming edges.

It then enters a loop while S is not empty. It removes a node n from S and appends it to the tail of L. It then iterates through all the vertices adjacent to n, removes the edge from the graph, decrements the in-degree of the destination vertex, and adds the destination vertex to S if its in-degree becomes zero.

After the loop, it checks if there are any nodes remaining with non-zero indegree. If yes, it means the graph has at least one cycle, and the function returns an empty vector. Otherwise, it returns the sorted list L.

The main function creates a vector of edges, defines the total number of nodes in the graph, creates a Graph object from the edges, calls the TopologicalSort function to get the sorted list, and prints it. If the sorted list is empty, it means there is at least one cycle in the graph, and it prints an error message.

Time Complexity

The time complexity of building the graph from the given edges is O(E), where E is the number of edges in the graph. The time complexity of performing the topological sort is O(V+E), where V is the number of vertices in the graph.

Space Complexity

The space complexity of the program is O(V+E). Here, V is the number of vertices in the graph, and E is the number of edges in the graph. The space complexity is due to the adjacency list representation of the graph, which requires O(V+E) space. The additional space used by the program is O(V) for storing the indegree of each vertex and O(V) for the temporary vector used to store the set of nodes with no incoming edges.

Advantages of Topological Sort

Following are some advantages of the topological sorting algorithms.

Identifying dependencies: Identifying the order in which tasks must be performed can help ensure that dependencies are satisfied before a task is executed, reducing the risk of errors and increasing efficiency.
Cycle detection: Topological sorting can be used to detect cycles in a graph. If a graph has a cycle, it cannot be topologically sorted. This can be useful for identifying issues in a system or process where circular dependencies may be causing problems.
Application in computer science: Topological sorting has applications in many areas of computer science, including compilers, operating systems, and scheduling algorithms.
Performance optimisation: By performing a topological sort on a directed acyclic graph, it is possible to optimise the performance of certain algorithms.
Efficient implementation: Topological sorting can be implemented efficiently using algorithms such as depth-first search or Kahn's algorithm, making it a practical and scalable technique for large graphs.

Disadvantages of Topological Sort

Following are some disadvantages of the topological sorting algorithms.

Limited to directed acyclic graphs: Topological sorting can only be used on directed acyclic graphs (DAGs). If a graph contains cycles, it cannot be topologically sorted.
Complexity: Although topological sorting has a linear time complexity in the number of vertices and edges in the input graph, the actual running time of the algorithm may still be high for very large graphs.
Dependency on the initial order: Topological sorting depends on the graph's initial order, which can affect the resulting topological order. This means that different initial orders may produce different topological orders.
Lack of uniqueness: Topological sorting may not always produce a unique solution, especially if the graph contains multiple sources or sinks. This can make it difficult to rely on topological sorting.
Limited to acyclic dependencies: Topological sorting is not effective for managing cyclic dependencies. Other approaches, such as feedback arc set algorithms or dynamic programming, may be more appropriate in situations with cyclic dependencies.

Topological Sort vs Other Sorts

Following is a comparison between topological sorting with other sorting algorithms.

Algorithm	Time Complexity	Space Complexity	Type of Sorting	Applications
Topological Sorting	O(V+E).	O(V).	Partial order sorting.	Dependency management, cycle detection, graph traversal, and task scheduling.
Bubble Sort	O(n^2).	O(1).	Comparison-based sorting.	Simple and easy to understand, useful for small datasets.
Insertion Sort	O(n^2).	O(1).	Comparison-based sorting.	Useful for small datasets, it can be efficient for partially sorted datasets.
Merge Sort	O(n log n).	O(n).	Comparison-based sorting.	Efficient for large datasets, stable sorting algorithm.
Quick Sort	O(n log n).	O(log n).	Comparison-based sorting.	Efficient for large datasets, unstable sorting algorithm.

Partial order sorting: Partial order sorting is a technique used to arrange a set of elements with a partial ordering relationship.

Comparison-based sorting: Comparison-based sorting is a sorting algorithm that compares elements pairwise to sort a data collection.

Stable Algorithm: A sorting algorithm is said to be stable if the relative order of equal elements is maintained after sorting.

Unstable Algorithm: A sorting algorithm is said to be unstable if the relative order of equal elements may not be maintained after sorting.

Applications of Topological Sort

Topological sorting has a wide range of applications in various fields. Following are some of the most common applications.

Dependency Management: Topological sorting is used to manage dependencies between software modules in computer science. For example, if module A depends on another module B, the topological order of the modules can be used to ensure that module B is built and loaded before module A.
Task Scheduling: In task scheduling, topological sorting can be used to determine the order in which tasks should be executed. For example, if task A must be completed before task B can begin, the topological order can be used to ensure that task A is executed before task B.
Cycle Detection: Topological sorting can also be used to detect cycles in a graph. If a graph contains cycles, it cannot be topologically sorted. Therefore, if the topological sort algorithm fails to produce a valid order, it indicates the presence of cycles in the graph.
Graph Traversal: Topological sorting can be used as a method of graph traversal. Visiting vertices in the order produced by the topological sort algorithm makes it possible to visit all vertices in a directed acyclic graph in a particular order.
Database Management: Topological sorting can be used in database management to enforce constraints on the order of data insertion. For example, if a table contains foreign key references to another table, the topological order can be used to ensure that the referenced table is populated before the referencing table.
Network Topology: Topological sorting can be used to determine the optimal order in which to transmit data across a network. Analysing the network topology and applying topological sorting makes it possible to optimise the order in which data is transmitted to reduce latency and improve performance.

Frequently Asked Questions

What is a topological sort?

Topological sort is an ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v.

What is the time complexity of topological sorting?

The time complexity of topological sorting is O(V + E), where V is the number of vertices and E is the number of edges in the graph.

What is the topological sort rule?

The topological sort rule states that for every directed edge (u, v), vertex u must appear before vertex v in the topologically sorted order of the graph.

Why is it called topological sort?

It's called topological sort because it orders the vertices of a directed acyclic graph (DAG) in a linear sequence that respects the graph's directional edges. This means if there is a directed edge from vertex A to vertex B, A appears before B in the sorted order, reflecting the graph's topological structure.

Conclusion

This article briefly discussed the topic of topological sorting in detail. We discussed all aspects, covering its algorithm, implementation, advantages, and disadvantages. We also compared topological sorting with other sorting algorithms. We hope that this blog has helped you understand the topological sort.

For further reading, refer to our articles on similar topics: