Topological Sorting
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u-v, vertex u comes before v in the ordering.
Note: Topological Sorting for a graph is not possible if the graph is not a DAG.
Example:
Input: Graph :
Example
Output: 5 4 2 3 1 0
Explanation: The first vertex in topological sorting is always a vertex with an in-degree of 0 (a vertex with no incoming edges). A topological sorting of the following graph is “5 4 2 3 1 0”. There can be more than one topological sorting for a graph. Another topological sorting of the following graph is “4 5 2 3 1 0”.
Topological Sorting vs Depth First Traversal (DFS):
In DFS, we print a vertex and then recursively call DFS for its adjacent vertices. In topological sorting, we need to print a vertex before its adjacent vertices.
For example, In the above given graph, the vertex ‘5’ should be printed before vertex ‘0’, but unlike DFS, the vertex ‘4’ should also be printed before vertex ‘0’. So Topological sorting is different from DFS. For example, a DFS of the shown graph is “5 2 3 1 0 4”, but it is not a topological sorting.
Topological Sorting in Directed Acyclic Graphs (DAGs)
DAGs are a special type of graphs in which each edge is directed such that no cycle exists in the graph, before understanding why Topological sort only exists for DAGs, lets first answer two questions:
- Why Topological Sort is not possible for graphs with undirected edges?
This is due to the fact that undirected edge between two vertices u and v means, there is an edge from u to v as well as from v to u. Because of this both the nodes u and v depend upon each other and none of them can appear before the other in the topological ordering without creating a contradiction.
- Why Topological Sort is not possible for graphs having cycles?
Imagine a graph with 3 vertices and edges = {1 to 2 , 2 to 3, 3 to 1} forming a cycle. Now if we try to topologically sort this graph starting from any vertex, it will always create a contradiction to our definition. All the vertices in a cycle are indirectly dependent on each other hence topological sorting fails.
Hence, a Directed Acyclic Graph removes the contradiction created by above two questions, hence it is suitable for topological ordering. A DFS based solution to find a topological sort has already been discussed.
Topological order may not be Unique:
Topological sorting is a dependency problem in which completion of one task depends upon the completion of several other tasks whose order can vary. Let us understand this concept via an example:
Suppose our task is to reach our School and in order to reach there, first we need to get dressed. The dependencies to wear clothes is shown in the below dependency graph. For example you can not wear shoes before wearing socks.
From the above image you would have already realized that there exist multiple ways to get dressed, the below image shows some of those ways.
Can you list all the possible topological ordering of getting dressed for above dependency graph?
Algorithm for Topological Sorting using DFS:
Here’s a step-by-step algorithm for topological sorting using Depth First Search (DFS):
- Create a graph with n vertices and m-directed edges.
- Initialize a stack and a visited array of size n.
- For each unvisited vertex in the graph, do the following:
- Call the DFS function with the vertex as the parameter.
- In the DFS function, mark the vertex as visited and recursively call the DFS function for all unvisited neighbors of the vertex.
- Once all the neighbors have been visited, push the vertex onto the stack.
- After all, vertices have been visited, pop elements from the stack and append them to the output list until the stack is empty.
- The resulting list is the topologically sorted order of the graph.
Illustration Topological Sorting Algorithm:
Below image is an illustration of the above approach:
Overall workflow of topological sorting
Step 1:
- We start DFS from node 0 because it has zero incoming Nodes
- We push node 0 in the stack and move to next node having minimum number of adjacent nodes i.e. node 1.
Step 2:
- In this step , because there is no adjacent of this node so push the node 1 in the stack and move to next node.
Step 3:
- In this step , We choose node 2 because it has minimum number of adjacent nodes after 0 and 1 .
- We call DFS for node 2 and push all the nodes which comes in traversal from node 2 in reverse order.
- So push 3 then push 2 .
Step 4:
- We now call DFS for node 4
- Because 0 and 1 already present in the stack so we just push node 4 in the stack and return.
Step 5:
- In this step because all the adjacent nodes of 5 is already in the stack we push node 5 in the stack and return.
Step 6: This is the final step of the Topological sorting in which we pop all the element from the stack and print it in that order .
Below is the implementation of the above approach:
#include <bits/stdc++.h>
using namespace std;
// Function to perform DFS and topological sorting
void topologicalSortUtil(int v, vector<vector<int> >& adj,
vector<bool>& visited,
stack<int>& Stack)
{
// Mark the current node as visited
visited[v] = true;
// Recur for all adjacent vertices
for (int i : adj[v]) {
if (!visited[i])
topologicalSortUtil(i, adj, visited, Stack);
}
// Push current vertex to stack which stores the result
Stack.push(v);
}
// Function to perform Topological Sort
void topologicalSort(vector<vector<int> >& adj, int V)
{
stack<int> Stack; // Stack to store the result
vector<bool> visited(V, false);
// Call the recursive helper function to store
// Topological Sort starting from all vertices one by
// one
for (int i = 0; i < V; i++) {
if (!visited[i])
topologicalSortUtil(i, adj, visited, Stack);
}
// Print contents of stack
while (!Stack.empty()) {
cout << Stack.top() << " ";
Stack.pop();
}
}
int main()
{
// Number of nodes
int V = 4;
// Edges
vector<vector<int> > edges
= { { 0, 1 }, { 1, 2 }, { 3, 1 }, { 3, 2 } };
// Graph represented as an adjacency list
vector<vector<int> > adj(V);
for (auto i : edges) {
adj[i[0]].push_back(i[1]);
}
cout << "Topological sorting of the graph: ";
topologicalSort(adj, V);
return 0;
}
import java.util.*;
public class TopologicalSort {
// Function to perform DFS and topological sorting
static void
topologicalSortUtil(int v, List<List<Integer> > adj,
boolean[] visited,
Stack<Integer> stack)
{
// Mark the current node as visited
visited[v] = true;
// Recur for all adjacent vertices
for (int i : adj.get(v)) {
if (!visited[i])
topologicalSortUtil(i, adj, visited, stack);
}
// Push current vertex to stack which stores the
// result
stack.push(v);
}
// Function to perform Topological Sort
static void topologicalSort(List<List<Integer> > adj,
int V)
{
// Stack to store the result
Stack<Integer> stack = new Stack<>();
boolean[] visited = new boolean[V];
// Call the recursive helper function to store
// Topological Sort starting from all vertices one
// by one
for (int i = 0; i < V; i++) {
if (!visited[i])
topologicalSortUtil(i, adj, visited, stack);
}
// Print contents of stack
System.out.print(
"Topological sorting of the graph: ");
while (!stack.empty()) {
System.out.print(stack.pop() + " ");
}
}
// Driver code
public static void main(String[] args)
{
// Number of nodes
int V = 4;
// Edges
List<List<Integer> > edges = new ArrayList<>();
edges.add(Arrays.asList(0, 1));
edges.add(Arrays.asList(1, 2));
edges.add(Arrays.asList(3, 1));
edges.add(Arrays.asList(3, 2));
// Graph represented as an adjacency list
List<List<Integer> > adj = new ArrayList<>(V);
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
for (List<Integer> i : edges) {
adj.get(i.get(0)).add(i.get(1));
}
topologicalSort(adj, V);
}
}
def topologicalSortUtil(v, adj, visited, stack):
# Mark the current node as visited
visited[v] = True
# Recur for all adjacent vertices
for i in adj[v]:
if not visited[i]:
topologicalSortUtil(i, adj, visited, stack)
# Push current vertex to stack which stores the result
stack.append(v)
# Function to perform Topological Sort
def topologicalSort(adj, V):
# Stack to store the result
stack = []
visited = [False] * V
# Call the recursive helper function to store
# Topological Sort starting from all vertices one by
# one
for i in range(V):
if not visited[i]:
topologicalSortUtil(i, adj, visited, stack)
# Print contents of stack
print("Topological sorting of the graph:", end=" ")
while stack:
print(stack.pop(), end=" ")
# Driver code
if __name__ == "__main__":
# Number of nodes
V = 4
# Edges
edges = [[0, 1], [1, 2], [3, 1], [3, 2]]
# Graph represented as an adjacency list
adj = [[] for _ in range(V)]
for i in edges:
adj[i[0]].append(i[1])
topologicalSort(adj, V)
using System;
using System.Collections.Generic;
class Program {
// Function to perform DFS and topological sorting
static void TopologicalSortUtil(int v,
List<List<int> > adj,
bool[] visited,
Stack<int> stack)
{
// Mark the current node as visited
visited[v] = true;
// Recur for all adjacent vertices
foreach(int i in adj[v])
{
if (!visited[i])
TopologicalSortUtil(i, adj, visited, stack);
}
// Push current vertex to stack which stores the
// result
stack.Push(v);
}
// Function to perform Topological Sort
static void TopologicalSort(List<List<int> > adj, int V)
{
// Stack to store the result
Stack<int> stack = new Stack<int>();
bool[] visited = new bool[V];
// Call the recursive helper function to store
// Topological Sort starting from all vertices one
// by one
for (int i = 0; i < V; i++) {
if (!visited[i])
TopologicalSortUtil(i, adj, visited, stack);
}
// Print contents of stack
Console.Write("Topological sorting of the graph: ");
while (stack.Count > 0) {
Console.Write(stack.Pop() + " ");
}
}
// Driver code
static void Main(string[] args)
{
// Number of nodes
int V = 4;
// Edges
List<List<int> > edges = new List<List<int> >{
new List<int>{ 0, 1 }, new List<int>{ 1, 2 },
new List<int>{ 3, 1 }, new List<int>{ 3, 2 }
};
// Graph represented as an adjacency list
List<List<int> > adj = new List<List<int> >();
for (int i = 0; i < V; i++) {
adj.Add(new List<int>());
}
foreach(List<int> i in edges)
{
adj[i[0]].Add(i[1]);
}
TopologicalSort(adj, V);
}
}
// Function to perform DFS and topological sorting
function topologicalSortUtil(v, adj, visited, stack) {
// Mark the current node as visited
visited[v] = true;
// Recur for all adjacent vertices
for (let i of adj[v]) {
if (!visited[i])
topologicalSortUtil(i, adj, visited, stack);
}
// Push current vertex to stack which stores the result
stack.push(v);
}
// Function to perform Topological Sort
function topologicalSort(adj, V) {
// Stack to store the result
let stack = [];
let visited = new Array(V).fill(false);
// Call the recursive helper function to store
// Topological Sort starting from all vertices one by
// one
for (let i = 0; i < V; i++) {
if (!visited[i])
topologicalSortUtil(i, adj, visited, stack);
}
// Print contents of stack
console.log("Topological sorting of the graph: ");
while (stack.length > 0) {
console.log(stack.pop() + " ");
}
}
// Driver code
(() => {
// Number of nodes
const V = 4;
// Edges
const edges = [[0, 1], [1, 2], [3, 1], [3, 2]];
// Graph represented as an adjacency list
const adj = Array.from({ length: V }, () => []);
for (let i of edges) {
adj[i[0]].push(i[1]);
}
topologicalSort(adj, V);
})();
Output
Topological sorting of the graph: 3 0 1 2
Time Complexity: O(V+E). The above algorithm is simply DFS with an extra stack. So time complexity is the same as DFS
Auxiliary space: O(V). The extra space is needed for the stack
Topological Sorting Using BFS:
#include <iostream>
#include <list>
#include <queue>
using namespace std;
// Class to represent a graph
class Graph {
int V; // No. of vertices
list<int>* adj; // Pointer to an array containing
// adjacency lists
public:
Graph(int V); // Constructor
void addEdge(int v,
int w); // Function to add an edge to graph
void topologicalSort(); // prints a Topological Sort of
// the complete graph
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
// Function to perform Topological Sort
void Graph::topologicalSort()
{
// Create a vector to store in-degree of all vertices
vector<int> in_degree(V, 0);
// Traverse adjacency lists to fill in_degree of
// vertices
for (int v = 0; v < V; ++v) {
for (auto const& w : adj[v])
in_degree[w]++;
}
// Create a queue and enqueue all vertices with
// in-degree 0
queue<int> q;
for (int i = 0; i < V; ++i) {
if (in_degree[i] == 0)
q.push(i);
}
// Initialize count of visited vertices
int count = 0;
// Create a vector to store topological order
vector<int> top_order;
// One by one dequeue vertices from queue and enqueue
// adjacent vertices if in-degree of adjacent becomes 0
while (!q.empty()) {
// Extract front of queue (or perform dequeue)
// and add it to topological order
int u = q.front();
q.pop();
top_order.push_back(u);
// Iterate through all its neighbouring nodes
// of dequeued node u and decrease their in-degree
// by 1
list<int>::iterator itr;
for (itr = adj[u].begin(); itr != adj[u].end();
++itr)
// If in-degree becomes zero, add it to queue
if (--in_degree[*itr] == 0)
q.push(*itr);
count++;
}
// Check if there was a cycle
if (count != V) {
cout << "Graph contains cycle\n";
return;
}
// Print topological order
for (int i : top_order)
cout << i << " ";
}
// Driver code
int main()
{
// Create a graph given in the above diagram
Graph g(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
cout << "Following is a Topological Sort of the given "
"graph\n";
g.topologicalSort();
return 0;
}
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
// Class to represent a graph
class Graph {
private int V; // No. of vertices
private ArrayList<Integer>[] adj; // Adjacency list
// representation of
// the graph
// Constructor
Graph(int V)
{
this.V = V;
adj = new ArrayList[V];
for (int i = 0; i < V; ++i)
adj[i] = new ArrayList<>();
}
// Function to add an edge to the graph
void addEdge(int v, int w)
{
adj[v].add(w); // Add w to v’s list.
}
// Function to perform Topological Sort
void topologicalSort()
{
// Create an array to store in-degree of all
// vertices
int[] inDegree = new int[V];
// Calculate in-degree of each vertex
for (int v = 0; v < V; ++v) {
for (int w : adj[v]) {
inDegree[w]++;
}
}
// Create a queue and enqueue all vertices with
// in-degree 0
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < V; ++i) {
if (inDegree[i] == 0)
q.add(i);
}
// Initialize count of visited vertices
int count = 0;
// Create an ArrayList to store topological order
ArrayList<Integer> topOrder = new ArrayList<>();
// One by one dequeue vertices from queue and
// enqueue adjacent vertices if in-degree of
// adjacent becomes 0
while (!q.isEmpty()) {
// Extract front of queue and add it to
// topological order
int u = q.poll();
topOrder.add(u);
count++;
// Iterate through all its neighboring nodes of
// dequeued node u and decrease their in-degree
// by 1
for (int w : adj[u]) {
// If in-degree becomes zero, add it to
// queue
if (--inDegree[w] == 0)
q.add(w);
}
}
// Check if there was a cycle
if (count != V) {
System.out.println("Graph contains cycle");
return;
}
// Print topological order
for (int i : topOrder)
System.out.print(i + " ");
}
}
// Driver code
public class Main {
public static void main(String[] args)
{
// Create a graph given in the above diagram
Graph g = new Graph(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
System.out.println(
"Following is a Topological Sort of the given graph");
g.topologicalSort();
}
}
from collections import defaultdict
class Graph:
def __init__(self, vertices):
# Number of vertices
self.V = vertices
# Dictionary to store adjacency lists
self.adj = defaultdict(list)
def addEdge(self, u, v):
# Function to add an edge to the graph
self.adj[u].append(v)
def topologicalSort(self):
# Function to perform Topological Sort
# Create a list to store in-degree of all vertices
in_degree = [0] * self.V
# Traverse adjacency lists to fill in_degree of vertices
for i in range(self.V):
for j in self.adj[i]:
in_degree[j] += 1
# Create a queue and enqueue all vertices with in-degree 0
q = []
for i in range(self.V):
if in_degree[i] == 0:
q.append(i)
# Initialize count of visited vertices
count = 0
# Create a list to store topological order
top_order = []
# One by one dequeue vertices from queue and enqueue
# adjacent vertices if in-degree of adjacent becomes 0
while q:
# Extract front of queue (or perform dequeue)
# and add it to topological order
u = q.pop(0)
top_order.append(u)
# Iterate through all its neighbouring nodes
# of dequeued node u and decrease their in-degree
# by 1
for node in self.adj[u]:
# If in-degree becomes zero, add it to queue
in_degree[node] -= 1
if in_degree[node] == 0:
q.append(node)
count += 1
# Check if there was a cycle
if count != self.V:
print("Graph contains cycle")
return
# Print topological order
print("Topological Sort:", top_order)
# Driver code
if __name__ == "__main__":
# Create a graph given in the above diagram
g = Graph(6)
g.addEdge(5, 2)
g.addEdge(5, 0)
g.addEdge(4, 0)
g.addEdge(4, 1)
g.addEdge(2, 3)
g.addEdge(3, 1)
print("Following is a Topological Sort of the given graph")
g.topologicalSort()
// Class to represent a graph
class Graph {
constructor(V) {
this.V = V; // No. of vertices
this.adj = new Array(V); // Array containing adjacency lists
for (let i = 0; i < V; i++) {
this.adj[i] = [];
}
}
// Function to add an edge to the graph
addEdge(v, w) {
this.adj[v].push(w); // Add w to v’s list.
}
// Function to perform Topological Sort
topologicalSort() {
// Create a array to store in-degree of all vertices
let inDegree = new Array(this.V).fill(0);
// Traverse adjacency lists to fill inDegree of vertices
for (let v = 0; v < this.V; v++) {
for (let w of this.adj[v]) {
inDegree[w]++;
}
}
// Create a queue and enqueue all vertices with in-degree 0
let queue = [];
for (let i = 0; i < this.V; i++) {
if (inDegree[i] === 0) {
queue.push(i);
}
}
// Initialize count of visited vertices
let count = 0;
// Create an array to store topological order
let topOrder = [];
// One by one dequeue vertices from queue and enqueue
// adjacent vertices if in-degree of adjacent becomes 0
while (queue.length !== 0) {
// Extract front of queue and add it to topological order
let u = queue.shift();
topOrder.push(u);
// Iterate through all its neighboring nodes
// of dequeued node u and decrease their in-degree by 1
for (let w of this.adj[u]) {
// If in-degree becomes zero, add it to queue
if (--inDegree[w] === 0) {
queue.push(w);
}
}
count++;
}
// Check if there was a cycle
if (count !== this.V) {
console.log("Graph contains cycle");
return;
}
// Print topological order
console.log("Topological Sort of the given graph:");
console.log(topOrder.join(" "));
}
}
// Driver code
// Create a graph given in the above diagram
let g = new Graph(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
console.log("Following is a Topological Sort of the given graph:");
g.topologicalSort();
//This code is contributed by Utkarsh
Output
Following is a Topological Sort of the given graph 4 5 2 0 3 1
Time Complexity:
The time complexity for constructing the graph is O(V + E), where V is the number of vertices and E is the number of edges.
The time complexity for performing topological sorting using BFS is also O(V + E), where V is the number of vertices and E is the number of edges. This is because each vertex and each edge is visited once during the BFS traversal.
Space Complexity:
The space complexity for storing the graph using an adjacency list is O(V + E), where V is the number of vertices and E is the number of edges.
Additional space is used for storing the in-degree of vertices, which requires O(V) space.
A queue is used for BFS traversal, which can contain at most V vertices. Thus, the space complexity for the queue is O(V).
Overall, the space complexity of the algorithm is O(V + E) due to the storage of the graph, in-degree array, and the queue.
In summary, the time complexity of the provided implementation is O(V + E), and the space complexity is also O(V + E).
Note: Here, we can also use a array instead of the stack. If the array is used then print the elements in reverse order to get the topological sorting.
Advantages of Topological Sort:
- Helps in scheduling tasks or events based on dependencies.
- Detects cycles in a directed graph.
- Efficient for solving problems with precedence constraints.
Disadvantages of Topological Sort:
- Only applicable to directed acyclic graphs (DAGs), not suitable for cyclic graphs.
- May not be unique, multiple valid topological orderings can exist.
- Inefficient for large graphs with many nodes and edges.
Applications of Topological Sort:
- Task scheduling and project management.
- Dependency resolution in package management systems.
- Determining the order of compilation in software build systems.
- Deadlock detection in operating systems.
- Course scheduling in universities.
Related Articles:
Contact Us