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)

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

Example of topological sorting in a graph 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.


Python Program for Topological Sorting


Java Program for Topological Sorting

C++ Program for Topological Sorting


using namespace std;

class Graph{

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

        Graph () {

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

            delete [] adjlist;

        void AddEdge (int src, int 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 */

        void Traverse () {
            for(int i=0; i<nodes; i++) {
                if (!visited[i]) {
                   TopologicalSort (i);
            while (!stack_topological_order.empty()) {
                cout << << " ";
int main()
    Graph g(7);
    // Store the edges of the directed graph in adjacency list.

    cout << "Topological Sorting Order: "; 

    return 0;

Output showing topological sorting of nodes in a graph

Topological Sorting Order: 1 6 3 0 5 2 4
Copyright (c) 2019-2020,
All rights reserved.