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.
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.

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

## 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

#### 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:

### 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

class Graph
{
int V; // No. of vertices

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

// function for adding to the graph

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

{
}

//function for dfs and departure time

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

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

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

return 0;
}``````

### Implementation in Pythonđź§°

``````""" A Python3 program to print topological sort of a DAG """

""" The function to perform DFS and store departure time of every vertex """
def DFS(v):
global vis, dep, time
vis[v] = 1
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)]

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

### Implementation in Javađź§°

``````import java.util.ArrayList;

public class Main
{
int nV;
int time = 0;
// constructor
public Main(int v)
{
nV = v;
for (int i = 0; i < v; i++)
}

public void AddEdge(int v, int 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

{
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);

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

### 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).

### 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! đźĄ·

Live masterclass