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
from dataclasses import dataclass, field
from collections import deque
@dataclass
class Graph :
nodes : int
visited : list = field(default_factory = list)
adjlist : dict = field(default_factory = dict)
stack : deque = field(default_factory = deque)
def AddEdge(self, src, dst) :
if src not in self.adjlist :
self.adjlist[src] = []
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.visited = [False] * 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 of topological sorting implemented in Python 3.7
Topological Sorting Order : 1 6 3 0 5 2 4
Java
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 of topological sorting implemented in Java
Topological Sorting Order: 1 6 3 0 5 2 4
C++ : Topological Sorting implementation C++14
#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 showing topological sorting of nodes in a graph
Topological Sorting Order: 1 6 3 0 5 2 4