Topological Sort

Key points of topological sorting algorithm
- Topological sort represents a linear ordering of vertices in a Directed Acyclic Graph (DAG) meeting some prerequisite rules.

- Rule for topological sorting : Vertex with no incoming edges is accessed first followed by the vertices on the outgoing paths.
      Example 1 : In the below graph vertex 1 has no incoming edges and can be reached before 3, 6, 0, 5, 2 and 4.
      Example 2 : In the below graph vertex 0 has no incoming edges and can be reached before 5, 2, 1, 3, 6 and 4. Example
Topological sorting using DFS
- A topologically sorted order could be found by doing a DFS on the graph. While doing a DFS, a stack is maintained to store the nodes in a reverse topologically sorted order. A node is pushed into the stack only after all the adjacent nodes on its outgoing edges are visited. When the DFS ends, the nodes are popped off the stack to get a topologically sorted order.

Algorithm : Topological Sort ( Graph G, Source_Vertex S )

  1.     Mark the source vertex S as visited.
  2.     For every vertex V adjacent to the source vertex S.
  3.         If the vertex V is not visited, then
  4.               Topological Sort ( Graph G, Source_Vertex V )
  5.     Push the source vertex S into the stack STK.

Printing the topological sorting order

  1.     While the stack STK is not empty.
  2.         Print the vertex V at the stack ( STK ) top.
  3.         Pop the vertex V at the stack ( STK ) top.

Topological traversal example Topological_Search_Graph_Image

Data structure used for storing graph: Adjacency list
Data structure used for DFS: Stack

Time complexity of topological sort : O ( V + E ) for an adjacency list implementation of a graph. ‘V’ is the number of vertices and ‘E’ is the number of edges in a graph.

Topological Sort implementation

from collections import deque, defaultdict

class Graph :

    def __init__(self, arg_nodes : int) :
        self.nodes = arg_nodes
        self.visited = [False] * self.nodes
        # The default dictionary would create an empty list as a default (value) 
        # for the nonexistent keys.
        self.adjlist = defaultdict(list)
        self.stack  = deque()

    def AddEdge(self, src : int, dst : int) :
        self.adjlist[src].append(dst)

    def TopologicalSort(self, src : int) :

        self.visited[src] = True

        # Check if there is an outgoing edge for a node in the adjacency list
        if src in self.adjlist :
            for node in self.adjlist[src] :
                if self.visited[node] == False :
                    self.TopologicalSort(node)

        # Only after all the nodes on the outgoing edges are visited push the
        # source node in the stack
        self.stack.appendleft(src)

    def Traverse(self) :
        for node in range(self.nodes) :
            if self.visited[node] == False :
               self.TopologicalSort(node)

        print("Topological Sorting Order : ", end = ' ')
        while self.stack :
            print(self.stack.popleft(),end=' ')

def main() :

    node_cnt = 7
    g = Graph(node_cnt)

    g.AddEdge(0,2)
    g.AddEdge(0,5)
    g.AddEdge(1,3)
    g.AddEdge(1,6)
    g.AddEdge(2,4)
    g.AddEdge(3,5)
    g.AddEdge(5,2)
    g.AddEdge(5,4)
    g.AddEdge(6,2)

    g.Traverse()

if __name__ == "__main__" :
    main()

Output

Topological Sorting Order :  1 6 3 0 5 2 4

#include<iostream>
#include<list>
#include<vector>
#include<stack>

using namespace std;

class Graph{

    private:
        int nodes;
        list<int> *adjlist;
        vector<bool> visited;
        stack<int> stack_topological_order;

    public:
        Graph () {
        }

        Graph (int nodes) {
            adjlist = new list<int> [nodes];
            visited.resize(nodes, false);
            this->nodes = nodes;
        }

        ~Graph(){ 
            delete [] adjlist;
        }

        void AddEdge (int src, int dst) {
            adjlist[src].push_back(dst);
        }
    
        void TopologicalSort (int src) {
            visited[src] = true;
            for (auto& itr : adjlist[src]) {
                if (!visited[itr]) {
                    TopologicalSort (itr);
                }   
            }   
            /* Only after all the outgoing edges are visited push the 
               source node in the stack */
            stack_topological_order.push(src);
        }  

        void Traverse () {
            for(int i=0; i<nodes; i++) {
                if (!visited[i]) {
                   TopologicalSort (i);
                }   
            }  
            while (!stack_topological_order.empty()) {
                cout << stack_topological_order.top() << " ";
                stack_topological_order.pop();
            }
        }
};
   
int main() 
{
    Graph g(7);
    // Store the edges of the directed graph in adjacency list.
    g.AddEdge(0,2);
    g.AddEdge(0,5);
    g.AddEdge(1,3);
    g.AddEdge(1,6);
    g.AddEdge(2,4);
    g.AddEdge(3,5);
    g.AddEdge(5,2);
    g.AddEdge(5,4);
    g.AddEdge(6,2);

    cout << "Topological Sorting Order: "; 
    g.Traverse();

    return 0;
}

Output

Topological Sorting Order: 1 6 3 0 5 2 4

import java.util.List;
import java.util.ArrayList;
import java.util.Stack;
import java.util.Arrays;

class Graph {

        Integer nodes;
        List<List<Integer>> adjlist;
        boolean[] visited;
        Stack<Integer> stack_topological_order;

        Graph (Integer arg_nodes) {
            nodes = arg_nodes;
            adjlist = new ArrayList<>(nodes);
            for (int i=0; i<nodes; i++)
                adjlist.add(new ArrayList<>());
            visited = new boolean[nodes];
            stack_topological_order = new Stack<Integer>();
        }

        void AddEdge (Integer src, Integer dst) {
            adjlist.get(src).add(dst);
        }

        void TopologicalSort (Integer src) {
            visited[src] = true;
            for (Integer adj_node : adjlist.get(src)) {
                if (!visited[adj_node]) {
                    TopologicalSort (adj_node);
                }
            }
            /* Only after all the outgoing edges are visited push the 
               source node in the stack */
            stack_topological_order.push(src);
        }

        void Traverse () {
            for(int i=0; i<nodes; i++) {
                if (!visited[i]) {
                   TopologicalSort (i);
                }
            }
            while (!stack_topological_order.empty()) {
                System.out.print(stack_topological_order.peek() + " ");
                stack_topological_order.pop();
            }
        }

        public static void main (String[] args) {

            Graph g = new Graph(7);

            // Store the edges of the directed graph in adjacency list.
            g.AddEdge(0,2);
            g.AddEdge(0,5);
            g.AddEdge(1,3);
            g.AddEdge(1,6);
            g.AddEdge(2,4);
            g.AddEdge(3,5);
            g.AddEdge(5,2);
            g.AddEdge(5,4);
            g.AddEdge(6,2);

            System.out.print("Topological Sorting Order: ");
            g.Traverse();
        }
}

Output

Topological Sorting Order: 1 6 3 0 5 2 4

Copyright (c) 2019-2022, Algotree.org.
All rights reserved.