Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction📖
2.
Topological Sort📶
3.
Arrival Time and Departure Time⏱
4.
Problem Statement❓
4.1.
Sample Example👀
4.1.1.
Input⌨️
4.1.2.
Output🖥️
4.1.3.
Explanation🗒️
5.
Approach 🔍
5.1.
Dry Run
5.1.1.
Step 1
5.1.2.
Step 2
5.1.3.
Step 4
5.1.4.
Step 5
5.2.
Algorithm⚙️
5.3.
Implementation in C++🧰
5.4.
Output🖥️
5.5.
Implementation in Python🧰
5.6.
Output🖥️
5.7.
Implementation in Java🧰
5.8.
Output🖥️
5.8.1.
Time and Space Complexity⏳
6.
Frequently Asked Questions
6.1.
What is a Graph?
6.2.
What is a directed acyclic graph?
6.3.
Can a DAG have zero edges?
6.4.
What is a topological sort?
6.5.
What is the maximum number of edges in node N's undirected graph?
7.
Conclusion
Last Updated: Mar 27, 2024
Easy

Topological Sort of a Graph Using Departure Time of Vertex

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction📖

In this blog, we will discuss a graph problem. In programming contests and technical interviews, graphs are one of the most important and frequently asked data structures. There are many common graph problems and techniques. 

Topological Sort of a Graph Using Departure Time of Vertex coding ninjas

This blog explores a coding task that explores how to find the topological sort of a graph using the departure time of the vertex.

Also see Application of graph data structure

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

sample example Topological Sort of a Graph Using Departure Time of Vertex coding ninjas

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

dry run example Topological Sort of a Graph Using Departure Time of Vertex coding ninjas

Step 2

dry run Topological Sort of a Graph Using Departure Time of Vertex coding ninjas

Step 4

dry run example Topological Sort of a Graph Using Departure Time of Vertex coding ninjas

Step 5

dry run example Topological Sort of a Graph Using Departure Time of Vertex coding ninjas

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;
}

Output🖥️

output c++ Topological Sort of a Graph Using Departure Time of Vertex coding ninja

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()

Output🖥️

output python Topological Sort of a Graph Using Departure Time of Vertex coding ninja

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();
	}
}

Output🖥️

output java Topological Sort of a Graph Using Departure Time of Vertex coding ninja

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 GraphDFS Traversal of a Graph - IterativelyClone of an undirected graph, and Clone a Directed Acyclic Graph.

Recommended Problems - 


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! 🥷

Previous article
Single Source Shortest Path
Next article
All Topological Sorts of a Directed Acyclic Graph
Live masterclass