Topological Sort of a Graph Using Departure Time of Vertex

Arrival Time and Departure Time⏱

Arrival Time in DFS Algorithm is when the vertex was explored for the first time, and Departure Time is when we have explored all of the vertex's neighbours and are ready to backtrack.

Problem Statement❓

In this problem, we have been given a directed acyclic graph(DAG), and we have to find the topological graph using the vertex's departure time.

Sample Example👀

Input⌨️

Let the given graph be

Output🖥️

The graph's topological sort will be 0 3 5 1 4 2 6.

Explanation🗒️

In the above example, vertex 0 has the least in-degree, so it comes first in the output, and vertex 6 has the highest in-degree, so it comes last.

Approach 🔍

To find the topological sort of the given graph, we will use the departure time of all the vertices using DFS(depth-first search), starting from all the unvisited vertices one by one.

Dry Run

The dry run for the above example is shown in the steps below:

Step 1

Step 2

Step 4

Step 5

Algorithm⚙️

1. In the first step, we run DFS one by one, beginning with all unvisited vertices.
    
2. Before exploring any of its neighbours, we note the arrival time of that vertex, and after exploring all of its neighbours, we note its departure time, but here in this problem, we need only departure time, so we keep track of that only.
    
3. Finally, after we have visited all of the graph's vertices, we print the vertices in decreasing order of departure time, which is our desired topological order of vertices.

Implementation in C++🧰

The implementation of the above approach is given below:

#include <bits/stdc++.h>
using namespace std;

/*The Graph class represents a directed graph using an 
adjacency list. */

class Graph 
{
	int V; // No. of vertices
	list<int>* adj;

	public:
	Graph(int); // Constructor
	~Graph(); // Destructor

	// function for adding to the graph
	void addEdge(int, int);

	// function to perform DFS
	void DFS(int, vector<bool>&, vector<int>&, int&);

	// funtion for topological sorting
	void topoSort();
};

Graph::Graph(int V)
{
	this->V = V;
	this->adj = new list<int>[V];
}

Graph::~Graph() { delete[] this->adj; }

void Graph::addEdge(int v, int w)
{
	adj[v].push_back(w); 
}

//function for dfs and departure time

void Graph::DFS(int v, vector<bool>& vis, vector<int>& departure, int& time)
{
	vis[v] = true;

	for (int i : adj[v])
	if (!vis[i])
	DFS(i, vis, departure, time);

	// set departure time of vertex v
	departure[time++] = v;
}

// function for topological sort.

void Graph::topoSort()
{
	// vector to store departure time of vertex.
	vector<int> dep(V, -1);

	// Mark all the vertices as not visited
	vector<bool> vis(V, false);
	int time = 0;

	for (int i = 0; i < V; i++) 
	{
		if (vis[i] == 0) 
		{
			DFS(i, vis, dep, time);
		}
	}
	reverse(dep.begin(),dep.end());
	for(auto i : dep)
    {
    cout<<i<<" ";
    }
}
int main()
{
	Graph g(7);
	g.addEdge(0, 1);
	g.addEdge(0, 3);
	g.addEdge(1, 2);
	g.addEdge(1, 4);
	g.addEdge(3, 5);
	g.addEdge(5, 4);
   	g.addEdge(4, 6);
   	g.addEdge(2, 6);
   	g.addEdge(5, 6);

	cout << "The graph's topological sort will be \n";
	g.topoSort();

	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output🖥️

Implementation in Python🧰

""" A Python3 program to print topological sort of a DAG """
def addEdge(u, v):
	global adj
	adj[u].append(v)

""" The function to perform DFS and store departure time of every vertex """
def DFS(v):
	global vis, dep, time
	vis[v] = 1
	for i in adj[v]:
		if vis[i] == 0:
			DFS(i)
	dep[time] = v
	time += 1

# The function perform Topological Sort
def topologicalSort():

	# perform DFS on all unvisited vertices
	for i in range(nV):
		if(vis[i] == 0):
			DFS(i)

	# Printing vertices in topological ordering
	for i in range(nV - 1, -1, -1):
		print(dep[i], end = " ")

if __name__ == '__main__':

	# Creating graph given in the above diagram
	nV,time, adj, vis, dep = 7, 0, [[] for i in range(8)], [0 for i in range(8)],[-1 for i in range(8)]
	addEdge(0, 1)
	addEdge(0, 3)
	addEdge(1, 2)
	addEdge(1, 4)
	addEdge(3, 5)
	addEdge(5, 4)
	addEdge(4, 6)
	addEdge(2, 6)
	addEdge(5, 6)

	print("The graph's topological sort will be")
	topologicalSort()

You can also try this code with Online Python Compiler

Run Code

Output🖥️

Implementation in Java🧰

import java.util.ArrayList;

public class Main 
{
	int nV;
	ArrayList<ArrayList<Integer> > ad;
	int time = 0;
	// constructor
	public Main(int v)
	{
		nV = v;
		ad = new ArrayList<>();
		for (int i = 0; i < v; i++)
		ad.add(new ArrayList<>());
	}

	// Adding edge
	public void AddEdge(int v, int w)
	{
		ad.get(v).add(w);
	}

	// The function to perform dfs and store departure time
	private void DFS(int v, boolean[] vis, int[] dep)
	{
		vis[v] = true;
		// time++; // arrival time of vertex v

		for (int i : ad.get(v)) 
		{
			if (!vis[i])
			DFS(i, vis, dep);
		}

		// set departure time of vertex v
		dep[time++] = v;
	}

	// The function to do Topological Sort. It uses DFS().
	public void TopologicalSort()
	{
		// vector to store dep time of vertex.

		int[] dep = new int[nV];
		for (int i = 0; i < nV; i++)
		dep[i] = -1;

		// Mark all the vertices as not visited

		boolean[] vis = new boolean[nV];

		// perform DFS on all unvisited vertices

		for (int i = 0; i < nV; i++)
		{
			if (!vis[i]) 
			{
				DFS(i, vis, dep);	
			}
		}
		// print the topological sort

		for (int i = nV - 1; i >= 0; i--)
		System.out.print(dep[i] + " ");
	}

	// Driver program to test above functions

	public static void main(String[] args)
	{
		Main g = new Main(7);
		g.AddEdge(0, 1);
    	g.AddEdge(0, 3);
    	g.AddEdge(1, 2);
    	g.AddEdge(1, 4);
    	g.AddEdge(3, 5);
    	g.AddEdge(5, 4);
    	g.AddEdge(4, 6);
    	g.AddEdge(2, 6);
    	g.AddEdge(5, 6);

		System.out.println("The graph's topological sort will be");
		g.TopologicalSort();
	}
}

You can also try this code with Online Java Compiler

Run Code

Output🖥️

Time and Space Complexity⏳

Time Complexity: Time complexity is a type of computational complexity that describes how long it takes to run an algorithm. The time complexity of an algorithm is the amount of time it takes to complete each statement. As a result, the size of the processed data is extremely important. The time complexity of the above code is O(V + E).

Space Complexity: The total amount of memory space used by an algorithm or program, including the space of input values for execution, is referred to as its space complexity. The space complexity of the code is O(V^2).

Frequently Asked Questions

What is a Graph?

A graph is a non-linear data structure composed of nodes and edges. The nodes are also known as vertices; edges are lines or arcs connecting any two nodes in the graph.

What is a directed acyclic graph?

Finally, after we have visited all of the graph's vertices, we print the vertices in decreasing order of departure time, which is our desired topological order of vertices.

Can a DAG have zero edges?

A directed graph is nothing more than a collection of vertices and directed edges. A directed graph can have an empty set of edges because a set can be empty.

What is a topological sort?

A topological sort, also known as a topological ordering, of a directed graph, is a linear ordering of its vertices in which u comes before v when ordering every directed edge uv from vertex u to vertex v.

What is the maximum number of edges in node N's undirected graph?

In an undirected graph, each node can have the edge over every other n-1 node. As a result, the total number of edges possible is n*(n-1)/2.

Conclusion

This article extensively discusses a graph problem in which we have to find the topological sort of a graph using the departure time of the vertex.

Do you not feel eager to read/explore additional information on the Graph subject after reading about how to find the topological sort of a graph using the departure time of the vertex? See the Print All Mother Vertices In The Graph, DFS Traversal of a Graph - Iteratively, Clone of an undirected graph, and Clone a Directed Acyclic Graph.

Recommended Problems - 

• Sort 0 1 2 
• Wiggle sort
• Find first and last position in sorted array

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enrol in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Happy Learning Ninja! 🥷