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.

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.

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⚙️

In the first step, we run DFS one by one, beginning with all unvisited vertices.

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.

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

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

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

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.