Illustration Topological Sorting Algorithm
Below image is an illustration of the above approach:
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.
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 :
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”.
Contact Us