Arrival and Departure time.

You are given a directed graph. You need to find the arrival and departure time of all the vertices in the graph. Arrival time is the at which a vertex was explored the first time in the DFS traversal of the graph and departure time is the time at which we have explored all the neighboring vertices of the vertex and are now ready to backtrack.

Consider the below graph.

The arrival and departure time of the vertices are as follows –

Vertex 0 (0, 11)
Vertex 1 (1, 2)
Vertex 2 (3, 10)
Vertex 3 (4, 7)
Vertex 4 (8, 9)
Vertex 5 (5, 6)
Vertex 6 (12, 15)
Vertex 7 (13, 14)

Algorithm:

We can solve the problem using simple DFS traversal.

  1. We keep two lists arrival and departure to store the arrival and departure time of the vertices and a variable time to keep track of the current time.
  2. Mark the source vertex as discovered and set its arrival time to 0 and increment the time by 1.
  3. For all the neighboring vertices of the current vertex, if they have not been previously discovered, recur for those vertices and while backtracking, set their departure times as well.
#include <bits/stdc++.h>
using namespace std;

// data structure to store graph edges
struct Edge {
	int src, dest;
};

// class to represent a graph object
class Graph
{
public:
	// construct a vector of vectors to represent an adjacency list
	vector<vector<int>> adjList;

	// Graph Constructor
	Graph(vector<Edge> const &edges, int N)
	{
		// resize the vector to N elements of type vector<int>
		adjList.resize(N);

		// add edges to the directed graph
		for (auto &edge: edges)
			adjList[edge.src].push_back(edge.dest);
	}
};

// Function to perform DFS Traversal
void DFS(Graph const &graph, int v, vector<bool> &discovered,
	vector<int> &arrival, vector<int> &departure, int &time)
{	
	// set arrival time of vertex v
	arrival[v] = ++time;

	// mark vertex as discovered
	discovered[v] = true;
	
	for (int i : graph.adjList[v])
	if (!discovered[i])
		DFS(graph, i, discovered, arrival, departure, time);

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

// main function
int main()
{
	// vector of graph edges as per above diagram
	vector<Edge> edges = {
		{0, 1}, {0, 2}, {2, 3}, {2, 4}, {3, 1}, {3, 5},
		{4, 5}, {6, 7}
	};

	// Number of nodes in the graph
	int N = 8;

	// create a graph from given edges
	Graph graph(edges, N);

	// vector to store arrival time of vertex
	vector<int> arrival(N);

	// vector to store departure time of vertex
	vector<int> departure(N);
	
	// Mark all the vertices as not discovered
	vector<bool> discovered(N);
	int time = -1;

	// Do DFS traversal from all undiscovered nodes to
	// cover all unconnected components of graph
	for (int i = 0; i < N; i++)
	if (!discovered[i])
		DFS(graph, i, discovered, arrival, departure, time);
	
	// print arrival and departure time of each
	// vertex in DFS
	for (int i = 0; i < N; i++) {
		cout << "Vertex " << i << " (" << arrival[i]
			 << ", " << departure[i] << ")" << endl;
	}

	return 0;
}

Also check out another popular interview question Print all paths from root to leaf in a tree.

One comment

Leave a Reply

Your email address will not be published.