A Topological sort of a Directed-Acyclic graph G is a linear ordering of all its vertices such that if G contains an edge E (u, v), then u appears before v in the ordering. And if the graph is not acyclic, then no linear ordering is possible.
A topological sort of a graph can be viewed as an ordering of its vertices along a horizontal line so that all directed edges go from left to right. For instance:
Topological sort of above DAG is:
Required topological sort: 1 2 3 4 5 6
Pseudocode
Topological Sort (G)
1. Call DFS(G) for each vertex v
2. As each vertex is visited and finished (recursion finishes), insert the vertex onto front of a stack
3. Return the stack of vertices ie topological sorting of verticesCode Implementation
//
// main.cpp
// Topological Sort
//
// Created by Himanshu on 10/09/21.
//
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
void printStack (stack<int> st) {
while(!st.empty()) {
cout<<st.top()<<" ";
st.pop();
}
cout<<endl;
}
//n = number of nodes in graph
void topologicalSort (int x, int n, vector<int> graph[], int vis[], stack<int> &st) {
vis[x] = 1;
for (int i=0; i<graph[x].size(); i++) {
int j = graph[x][i];
if (vis[j] == 0) {
topologicalSort(j, n, graph, vis, st);
}
}
st.push(x);
}
int main() {
int s = 1, n = 6;
vector<int> graph[n+1];
int vis[n+1];
stack<int> st;
graph[1].push_back(2);
graph[2].push_back(3);
graph[2].push_back(4);
graph[3].push_back(4);
graph[4].push_back(6);
graph[4].push_back(5);
for (int i=1; i<=n; i++) {
vis[i] = 0;
}
cout<<"Graph:"<<endl;
for (int i=1; i<=n; i++) {
if (graph[i].size() > 0) {
cout<<i<<": ";
}
for (int j=0; j<graph[i].size(); j++) {
cout<<graph[i][j]<<" ";
}
if (graph[i].size() > 0) {
cout<<endl;
}
}
cout<<endl<<"Topological Sort:"<<endl;
topologicalSort(s, n, graph, vis, st);
printStack(st);
return 0;
}
Output
Graph: 1: 2 2: 3 4 3: 4 4: 6 5 Topological Sort: 1 2 3 4 5 6
A quick tip: Topological Sort is similar to DFS (Depth-First search), however here, we are saving the visited nodes in a stack in the reverse order they are visited ie from last to the first node.
Here’s a working example: Topological sort
Practice Problems
You could try implementing Topological sort in below problems from Hackerearth:
One thought on “Topological Sort [Hackerearth]”