# Topological Sort

Key points of topological sorting algorithm
- Topological sort runs on a Directed Acyclic Graph (DAG) and returns a sequence of vertices. Each vertex in the topological sorting order comes prior to the vertices that it points to.

- For a given Directed Acyclic Graph (DAG) there could be atleast 1 topological sorting order

- 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.
Topological sorting using Depth First Search (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.

Applications of Topological Sorting:
- Many job scheduling applications use Topological Sorting for scheduling jobs that have dependencies on other jobs.
- Many complex build systems use Topological Sorting for resolving the build dependencies.

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

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.stack  = deque()

def AddEdge(self, src : int, dst : int) :

def TopologicalSort(self, src : int) :

self.visited[src] = True

# Check if there is an outgoing edge for a node in the adjacency list
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.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;
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

``````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;
boolean[] visited;
Stack<Integer> stack_topological_order;

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

void AddEdge (Integer src, Integer dst) {
}

void TopologicalSort (Integer src) {
visited[src] = true;
}
}
/* 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.

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

Output

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