Topological Sorting

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:

#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;
}

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);
    }
}

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)

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);
    }
}

// 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);
})();

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

Topological Sorting Using BFS:

#include <iostream>
#include <list>
#include <queue>
using namespace std;

// Class to represent a graph
class Graph {
    int V; // No. of vertices
    list<int>* adj; // Pointer to an array containing
                    // adjacency lists

public:
    Graph(int V); // Constructor
    void addEdge(int v,
                 int w); // Function to add an edge to graph
    void topologicalSort(); // prints a Topological Sort of
                            // the complete graph
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}

// Function to perform Topological Sort
void Graph::topologicalSort()
{
    // Create a vector to store in-degree of all vertices
    vector<int> in_degree(V, 0);

    // Traverse adjacency lists to fill in_degree of
    // vertices
    for (int v = 0; v < V; ++v) {
        for (auto const& w : adj[v])
            in_degree[w]++;
    }

    // Create a queue and enqueue all vertices with
    // in-degree 0
    queue<int> q;
    for (int i = 0; i < V; ++i) {
        if (in_degree[i] == 0)
            q.push(i);
    }

    // Initialize count of visited vertices
    int count = 0;

    // Create a vector to store topological order
    vector<int> top_order;

    // One by one dequeue vertices from queue and enqueue
    // adjacent vertices if in-degree of adjacent becomes 0
    while (!q.empty()) {
        // Extract front of queue (or perform dequeue)
        // and add it to topological order
        int u = q.front();
        q.pop();
        top_order.push_back(u);

        // Iterate through all its neighbouring nodes
        // of dequeued node u and decrease their in-degree
        // by 1
        list<int>::iterator itr;
        for (itr = adj[u].begin(); itr != adj[u].end();
             ++itr)
            // If in-degree becomes zero, add it to queue
            if (--in_degree[*itr] == 0)
                q.push(*itr);

        count++;
    }

    // Check if there was a cycle
    if (count != V) {
        cout << "Graph contains cycle\n";
        return;
    }

    // Print topological order
    for (int i : top_order)
        cout << i << " ";
}

// Driver code
int main()
{
    // Create a graph given in the above diagram
    Graph g(6);
    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);

    cout << "Following is a Topological Sort of the given "
            "graph\n";
    g.topologicalSort();

    return 0;
}

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

// Class to represent a graph
class Graph {
    private int V; // No. of vertices
    private ArrayList<Integer>[] adj; // Adjacency list
                                      // representation of
                                      // the graph

    // Constructor
    Graph(int V)
    {
        this.V = V;
        adj = new ArrayList[V];
        for (int i = 0; i < V; ++i)
            adj[i] = new ArrayList<>();
    }

    // Function to add an edge to the graph
    void addEdge(int v, int w)
    {
        adj[v].add(w); // Add w to v’s list.
    }

    // Function to perform Topological Sort
    void topologicalSort()
    {
        // Create an array to store in-degree of all
        // vertices
        int[] inDegree = new int[V];

        // Calculate in-degree of each vertex
        for (int v = 0; v < V; ++v) {
            for (int w : adj[v]) {
                inDegree[w]++;
            }
        }

        // Create a queue and enqueue all vertices with
        // in-degree 0
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < V; ++i) {
            if (inDegree[i] == 0)
                q.add(i);
        }

        // Initialize count of visited vertices
        int count = 0;

        // Create an ArrayList to store topological order
        ArrayList<Integer> topOrder = new ArrayList<>();

        // One by one dequeue vertices from queue and
        // enqueue adjacent vertices if in-degree of
        // adjacent becomes 0
        while (!q.isEmpty()) {
            // Extract front of queue and add it to
            // topological order
            int u = q.poll();
            topOrder.add(u);
            count++;

            // Iterate through all its neighboring nodes of
            // dequeued node u and decrease their in-degree
            // by 1
            for (int w : adj[u]) {
                // If in-degree becomes zero, add it to
                // queue
                if (--inDegree[w] == 0)
                    q.add(w);
            }
        }

        // Check if there was a cycle
        if (count != V) {
            System.out.println("Graph contains cycle");
            return;
        }

        // Print topological order
        for (int i : topOrder)
            System.out.print(i + " ");
    }
}

// Driver code
public class Main {
    public static void main(String[] args)
    {
        // Create a graph given in the above diagram
        Graph g = new Graph(6);
        g.addEdge(5, 2);
        g.addEdge(5, 0);
        g.addEdge(4, 0);
        g.addEdge(4, 1);
        g.addEdge(2, 3);
        g.addEdge(3, 1);

        System.out.println(
            "Following is a Topological Sort of the given graph");
        g.topologicalSort();
    }
}

from collections import defaultdict


class Graph:
    def __init__(self, vertices):
        # Number of vertices
        self.V = vertices  
        # Dictionary to store adjacency lists
        self.adj = defaultdict(list)  

    def addEdge(self, u, v):
        # Function to add an edge to the graph
        self.adj[u].append(v)

    def topologicalSort(self):
        # Function to perform Topological Sort
        # Create a list to store in-degree of all vertices
        in_degree = [0] * self.V

        # Traverse adjacency lists to fill in_degree of vertices
        for i in range(self.V):
            for j in self.adj[i]:
                in_degree[j] += 1

        # Create a queue and enqueue all vertices with in-degree 0
        q = []
        for i in range(self.V):
            if in_degree[i] == 0:
                q.append(i)

        # Initialize count of visited vertices
        count = 0

        # Create a list to store topological order
        top_order = []

        # One by one dequeue vertices from queue and enqueue
        # adjacent vertices if in-degree of adjacent becomes 0
        while q:
            # Extract front of queue (or perform dequeue)
            # and add it to topological order
            u = q.pop(0)
            top_order.append(u)

            # Iterate through all its neighbouring nodes
            # of dequeued node u and decrease their in-degree
            # by 1
            for node in self.adj[u]:
                # If in-degree becomes zero, add it to queue
                in_degree[node] -= 1
                if in_degree[node] == 0:
                    q.append(node)

            count += 1

        # Check if there was a cycle
        if count != self.V:
            print("Graph contains cycle")
            return

        # Print topological order
        print("Topological Sort:", top_order)


# Driver code
if __name__ == "__main__":
    # Create a graph given in the above diagram
    g = Graph(6)
    g.addEdge(5, 2)
    g.addEdge(5, 0)
    g.addEdge(4, 0)
    g.addEdge(4, 1)
    g.addEdge(2, 3)
    g.addEdge(3, 1)

    print("Following is a Topological Sort of the given graph")
    g.topologicalSort()

// Class to represent a graph
class Graph {
    constructor(V) {
        this.V = V; // No. of vertices
        this.adj = new Array(V); // Array containing adjacency lists
        for (let i = 0; i < V; i++) {
            this.adj[i] = [];
        }
    }

    // Function to add an edge to the graph
    addEdge(v, w) {
        this.adj[v].push(w); // Add w to v’s list.
    }

    // Function to perform Topological Sort
    topologicalSort() {
        // Create a array to store in-degree of all vertices
        let inDegree = new Array(this.V).fill(0);

        // Traverse adjacency lists to fill inDegree of vertices
        for (let v = 0; v < this.V; v++) {
            for (let w of this.adj[v]) {
                inDegree[w]++;
            }
        }

        // Create a queue and enqueue all vertices with in-degree 0
        let queue = [];
        for (let i = 0; i < this.V; i++) {
            if (inDegree[i] === 0) {
                queue.push(i);
            }
        }

        // Initialize count of visited vertices
        let count = 0;

        // Create an array to store topological order
        let topOrder = [];

        // One by one dequeue vertices from queue and enqueue
        // adjacent vertices if in-degree of adjacent becomes 0
        while (queue.length !== 0) {
            // Extract front of queue and add it to topological order
            let u = queue.shift();
            topOrder.push(u);

            // Iterate through all its neighboring nodes
            // of dequeued node u and decrease their in-degree by 1
            for (let w of this.adj[u]) {
                // If in-degree becomes zero, add it to queue
                if (--inDegree[w] === 0) {
                    queue.push(w);
                }
            }

            count++;
        }

        // Check if there was a cycle
        if (count !== this.V) {
            console.log("Graph contains cycle");
            return;
        }

        // Print topological order
        console.log("Topological Sort of the given graph:");
        console.log(topOrder.join(" "));
    }
}

// Driver code
// Create a graph given in the above diagram
let g = new Graph(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);

console.log("Following is a Topological Sort of the given graph:");
g.topologicalSort();
//This code is contributed by Utkarsh

Following is a Topological Sort of the given graph
4 5 2 0 3 1 

Time Complexity:

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

The time complexity for performing topological sorting using BFS is also O(V + E), where V is the number of vertices and E is the number of edges. This is because each vertex and each edge is visited once during the BFS traversal.

Space Complexity:

The space complexity for storing the graph using an adjacency list is O(V + E), where V is the number of vertices and E is the number of edges.

Additional space is used for storing the in-degree of vertices, which requires O(V) space.

A queue is used for BFS traversal, which can contain at most V vertices. Thus, the space complexity for the queue is O(V).

Overall, the space complexity of the algorithm is O(V + E) due to the storage of the graph, in-degree array, and the queue.

In summary, the time complexity of the provided implementation is O(V + E), and the space complexity is also O(V + E).

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: 

• Kahn’s algorithm for Topological Sorting
• All Topological Sorts of a Directed Acyclic Graph

GeeksforGeeks

Improve