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

Python : Topological Sorting implementation Python 3.7 using dataclass

Java

Java : Topological Sorting implementation Java 8

C++ : Topological Sorting implementation C++14

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

using namespace std;

class Graph{

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

public:
Graph () {
}

Graph (int nodes) {
visited.resize(nodes, false);
this->nodes = nodes;
}

~Graph(){
}

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

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

return 0;
}
``````

Output showing topological sorting of nodes in a graph

``````Topological Sorting Order: 1 6 3 0 5 2 4
``````