Algotree > Algorithms > Tree & Graph Traversal > Topological Sort

Topological Sort

Topological sorting of a Directed Acyclic Graph (DAG)

Criteria 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.

Algorithm : Topological Sort ( Graph G, Source_Vertex S )

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

Printing the topological sorting order

While the stack STK is not empty.
Print the vertex V at the stack ( STK ) top.
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) :
        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, dst) :
        self.adjlist[src].append(dst)

    def TopologicalSort(self, src) :

        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