Topological Sorting

Last Updated : 07 Mar, 2024

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u-v, vertex u comes before v in the ordering.

Note: Topological Sorting for a graph is not possible if the graph is not a DAG.

Example:

Input: Graph :

Example

Output: 5 4 2 3 1 0
Explanation: The first vertex in topological sorting is always a vertex with an in-degree of 0 (a vertex with no incoming edges). A topological sorting of the following graph is “5 4 2 3 1 0”. There can be more than one topological sorting for a graph. Another topological sorting of the following graph is “4 5 2 3 1 0”.

Topological Sorting vs Depth First Traversal (DFS):

In DFS, we print a vertex and then recursively call DFS for its adjacent vertices. In topological sorting, we need to print a vertex before its adjacent vertices.

For example, In the above given graph, the vertex ‘5’ should be printed before vertex ‘0’, but unlike DFS, the vertex ‘4’ should also be printed before vertex ‘0’. So Topological sorting is different from DFS. For example, a DFS of the shown graph is “5 2 3 1 0 4”, but it is not a topological sorting.

Topological Sorting in Directed Acyclic Graphs (DAGs)

DAGs are a special type of graphs in which each edge is directed such that no cycle exists in the graph, before understanding why Topological sort only exists for DAGs, lets first answer two questions:

Why Topological Sort is not possible for graphs with undirected edges?

This is due to the fact that undirected edge between two vertices u and v means, there is an edge from u to v as well as from v to u. Because of this both the nodes u and v depend upon each other and none of them can appear before the other in the topological ordering without creating a contradiction.

Why Topological Sort is not possible for graphs having cycles?

Imagine a graph with 3 vertices and edges = {1 to 2 , 2 to 3, 3 to 1} forming a cycle. Now if we try to topologically sort this graph starting from any vertex, it will always create a contradiction to our definition. All the vertices in a cycle are indirectly dependent on each other hence topological sorting fails.

Hence, a Directed Acyclic Graph removes the contradiction created by above two questions, hence it is suitable for topological ordering. A DFS based solution to find a topological sort has already been discussed.

Topological order may not be Unique:

Topological sorting is a dependency problem in which completion of one task depends upon the completion of several other tasks whose order can vary. Let us understand this concept via an example:

Suppose our task is to reach our School and in order to reach there, first we need to get dressed. The dependencies to wear clothes is shown in the below dependency graph. For example you can not wear shoes before wearing socks.

From the above image you would have already realized that there exist multiple ways to get dressed, the below image shows some of those ways.

Can you list all the possible topological ordering of getting dressed for above dependency graph?

Algorithm for Topological Sorting using DFS:

Here’s a step-by-step algorithm for topological sorting using Depth First Search (DFS):

Create a graph with n vertices and m-directed edges.
Initialize a stack and a visited array of size n.
For each unvisited vertex in the graph, do the following:
- Call the DFS function with the vertex as the parameter.
- In the DFS function, mark the vertex as visited and recursively call the DFS function for all unvisited neighbors of the vertex.
- Once all the neighbors have been visited, push the vertex onto the stack.
After all, vertices have been visited, pop elements from the stack and append them to the output list until the stack is empty.
The resulting list is the topologically sorted order of the graph.

Illustration Topological Sorting Algorithm:

Below image is an illustration of the above approach:

Overall workflow of topological sorting

Step 1:

We start DFS from node 0 because it has zero incoming Nodes

We push node 0 in the stack and move to next node having minimum number of adjacent nodes i.e. node 1.

Step 2:

In this step , because there is no adjacent of this node so push the node 1 in the stack and move to next node.

Step 3:

In this step , We choose node 2 because it has minimum number of adjacent nodes after 0 and 1 .

We call DFS for node 2 and push all the nodes which comes in traversal from node 2 in reverse order.

So push 3 then push 2 .

Step 4:

We now call DFS for node 4

Because 0 and 1 already present in the stack so we just push node 4 in the stack and return.

Step 5:

In this step because all the adjacent nodes of 5 is already in the stack we push node 5 in the stack and return.

Step 6: This is the final step of the Topological sorting in which we pop all the element from the stack and print it in that order .

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to perform DFS and topological sorting
void topologicalSortUtil(int v, vector<vector<int> >& adj,
                         vector<bool>& visited,
                         stack<int>& Stack)
{
    // Mark the current node as visited
    visited[v] = true;
 
    // Recur for all adjacent vertices
    for (int i : adj[v]) {
        if (!visited[i])
            topologicalSortUtil(i, adj, visited, Stack);
    }
 
    // Push current vertex to stack which stores the result
    Stack.push(v);
}
 
// Function to perform Topological Sort
void topologicalSort(vector<vector<int> >& adj, int V)
{
    stack<int> Stack; // Stack to store the result
    vector<bool> visited(V, false);
 
    // Call the recursive helper function to store
    // Topological Sort starting from all vertices one by
    // one
    for (int i = 0; i < V; i++) {
        if (!visited[i])
            topologicalSortUtil(i, adj, visited, Stack);
    }
 
    // Print contents of stack
    while (!Stack.empty()) {
        cout << Stack.top() << " ";
        Stack.pop();
    }
}
 
int main()
{
 
    // Number of nodes
    int V = 4;
 
    // Edges
    vector<vector<int> > edges
        = { { 0, 1 }, { 1, 2 }, { 3, 1 }, { 3, 2 } };
 
    // Graph represented as an adjacency list
    vector<vector<int> > adj(V);
 
    for (auto i : edges) {
        adj[i[0]].push_back(i[1]);
    }
 
    cout << "Topological sorting of the graph: ";
    topologicalSort(adj, V);
 
    return 0;
}

Java

import java.util.*;
 
public class TopologicalSort {
 
    // Function to perform DFS and topological sorting
    static void
    topologicalSortUtil(int v, List<List<Integer> > adj,
                        boolean[] visited,
                        Stack<Integer> stack)
    {
        // Mark the current node as visited
        visited[v] = true;
 
        // Recur for all adjacent vertices
        for (int i : adj.get(v)) {
            if (!visited[i])
                topologicalSortUtil(i, adj, visited, stack);
        }
 
        // Push current vertex to stack which stores the
        // result
        stack.push(v);
    }
 
    // Function to perform Topological Sort
    static void topologicalSort(List<List<Integer> > adj,
                                int V)
    {
        // Stack to store the result
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[V];
 
        // Call the recursive helper function to store
        // Topological Sort starting from all vertices one
        // by one
        for (int i = 0; i < V; i++) {
            if (!visited[i])
                topologicalSortUtil(i, adj, visited, stack);
        }
 
        // Print contents of stack
        System.out.print(
            "Topological sorting of the graph: ");
        while (!stack.empty()) {
            System.out.print(stack.pop() + " ");
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Number of nodes
        int V = 4;
 
        // Edges
        List<List<Integer> > edges = new ArrayList<>();
        edges.add(Arrays.asList(0, 1));
        edges.add(Arrays.asList(1, 2));
        edges.add(Arrays.asList(3, 1));
        edges.add(Arrays.asList(3, 2));
 
        // Graph represented as an adjacency list
        List<List<Integer> > adj = new ArrayList<>(V);
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
 
        for (List<Integer> i : edges) {
            adj.get(i.get(0)).add(i.get(1));
        }
 
        topologicalSort(adj, V);
    }
}

C#

using System;
using System.Collections.Generic;
 
class Program {
    // Function to perform DFS and topological sorting
    static void TopologicalSortUtil(int v,
                                    List<List<int> > adj,
                                    bool[] visited,
                                    Stack<int> stack)
    {
        // Mark the current node as visited
        visited[v] = true;
 
        // Recur for all adjacent vertices
        foreach(int i in adj[v])
        {
            if (!visited[i])
                TopologicalSortUtil(i, adj, visited, stack);
        }
 
        // Push current vertex to stack which stores the
        // result
        stack.Push(v);
    }
 
    // Function to perform Topological Sort
    static void TopologicalSort(List<List<int> > adj, int V)
    {
        // Stack to store the result
        Stack<int> stack = new Stack<int>();
        bool[] visited = new bool[V];
 
        // Call the recursive helper function to store
        // Topological Sort starting from all vertices one
        // by one
        for (int i = 0; i < V; i++) {
            if (!visited[i])
                TopologicalSortUtil(i, adj, visited, stack);
        }
 
        // Print contents of stack
        Console.Write("Topological sorting of the graph: ");
        while (stack.Count > 0) {
            Console.Write(stack.Pop() + " ");
        }
    }
 
    // Driver code
    static void Main(string[] args)
    {
        // Number of nodes
        int V = 4;
 
        // Edges
        List<List<int> > edges = new List<List<int> >{
            new List<int>{ 0, 1 }, new List<int>{ 1, 2 },
            new List<int>{ 3, 1 }, new List<int>{ 3, 2 }
        };
 
        // Graph represented as an adjacency list
        List<List<int> > adj = new List<List<int> >();
        for (int i = 0; i < V; i++) {
            adj.Add(new List<int>());
        }
 
        foreach(List<int> i in edges)
        {
            adj[i[0]].Add(i[1]);
        }
 
        TopologicalSort(adj, V);
    }
}

Javascript

// Function to perform DFS and topological sorting
function topologicalSortUtil(v, adj, visited, stack) {
    // Mark the current node as visited
    visited[v] = true;
 
    // Recur for all adjacent vertices
    for (let i of adj[v]) {
        if (!visited[i])
            topologicalSortUtil(i, adj, visited, stack);
    }
 
    // Push current vertex to stack which stores the result
    stack.push(v);
}
 
// Function to perform Topological Sort
function topologicalSort(adj, V) {
    // Stack to store the result
    let stack = [];
    let visited = new Array(V).fill(false);
 
    // Call the recursive helper function to store
    // Topological Sort starting from all vertices one by
    // one
    for (let i = 0; i < V; i++) {
        if (!visited[i])
            topologicalSortUtil(i, adj, visited, stack);
    }
 
    // Print contents of stack
    console.log("Topological sorting of the graph: ");
    while (stack.length > 0) {
        console.log(stack.pop() + " ");
    }
}
 
// Driver code
(() => {
    // Number of nodes
    const V = 4;
 
    // Edges
    const edges = [[0, 1], [1, 2], [3, 1], [3, 2]];
 
    // Graph represented as an adjacency list
    const adj = Array.from({ length: V }, () => []);
 
    for (let i of edges) {
        adj[i[0]].push(i[1]);
    }
 
    topologicalSort(adj, V);
})();

Python3

def topologicalSortUtil(v, adj, visited, stack):
    # Mark the current node as visited
    visited[v] = True
 
    # Recur for all adjacent vertices
    for i in adj[v]:
        if not visited[i]:
            topologicalSortUtil(i, adj, visited, stack)
 
    # Push current vertex to stack which stores the result
    stack.append(v)
 
 
# Function to perform Topological Sort
def topologicalSort(adj, V):
    # Stack to store the result
    stack = []
 
    visited = [False] * V
 
    # Call the recursive helper function to store
    # Topological Sort starting from all vertices one by
    # one
    for i in range(V):
        if not visited[i]:
            topologicalSortUtil(i, adj, visited, stack)
 
    # Print contents of stack
    print("Topological sorting of the graph:", end=" ")
    while stack:
        print(stack.pop(), end=" ")
 
 
# Driver code
if __name__ == "__main__":
    # Number of nodes
    V = 4
 
    # Edges
    edges = [[0, 1], [1, 2], [3, 1], [3, 2]]
 
    # Graph represented as an adjacency list
    adj = [[] for _ in range(V)]
 
    for i in edges:
        adj[i[0]].append(i[1])
 
    topologicalSort(adj, V)

Output

Topological sorting of the graph: 3 0 1 2

Time Complexity: O(V+E). The above algorithm is simply DFS with an extra stack. So time complexity is the same as DFS
Auxiliary space: O(V). The extra space is needed for the stack

Note: Here, we can also use a array instead of the stack. If the array is used then print the elements in reverse order to get the topological sorting.

Advantages of Topological Sort:

Helps in scheduling tasks or events based on dependencies.
Detects cycles in a directed graph.
Efficient for solving problems with precedence constraints.

Disadvantages of Topological Sort:

Only applicable to directed acyclic graphs (DAGs), not suitable for cyclic graphs.
May not be unique, multiple valid topological orderings can exist.
Inefficient for large graphs with many nodes and edges.

Applications of Topological Sort:

Task scheduling and project management.
Dependency resolution in package management systems.
Determining the order of compilation in software build systems.
Deadlock detection in operating systems.
Course scheduling in universities.

Related Articles:

Suggest improvement

Reverse Delete Algorithm for Minimum Spanning Tree

All Topological Sorts of a Directed Acyclic Graph

Share your thoughts in the comments

BFS and DFS on Graph

Cycle in a Graph

Shortest Paths in Graph

Minimum Spanning Tree in Graph

Topological Sorting in Graph

Connectivity of Graph

Maximum flow in a Graph

Some must do problems on Graph