Arrival Time / Pre -Visit Time /Starting Time:
Arrival time for a node is the time when it is first discovered in DFS . It is the time at which the node gets into the recursion stack .
Departure Time / Post-Visit Time/Finishing time :
Departure time for a node is the time when all of its adjacent node in the graph are explored and is ready to backtrack . It is the time at which the node pops out of the recursion stack .
Take an example — When parents bring food to home , they first ensures that every child of them is fed , then they start eating . Same simple concept is applied here .
Program:
import java.util.ArrayList;
import java.util.Iterator;
public class ArrivalDepartureTime {
public ArrivalDepartureTime() {
}
void addEdge(ArrayList<ArrayList<Integer>> adj, int v, int u){
adj.get(v).add(u);
}
public static void main(String[] args) {
ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
for(int i=0;i<8;i++){
adj.add(new ArrayList<>());
}
ArrivalDepartureTime g = new ArrivalDepartureTime();
g.addEdge(adj,0, 1);
g.addEdge(adj,0, 2);
g.addEdge(adj,2, 3);
g.addEdge(adj,2, 4);
g.addEdge(adj,3, 1);
g.addEdge(adj,3, 5);
g.addEdge(adj,4, 5);
g.addEdge(adj,6, 7);
g.arrivalDepartureVertex(adj,8);
}
void arrivalDepartureVertex(ArrayList<ArrayList<Integer>> adj,int V){
boolean[] visited = new boolean[V];
int[] arrival = new int[V];
int[] departure = new int[V];
int time = -1;
for(int i=0;i<V;i++){
if(!visited[i]){
time = DFS(i,adj,visited,arrival,departure,time);
}
}
for(int i=0;i<arrival.length;i++){
System.out.println("vertex "+i +" arrival time:"+arrival[i]+" departure time: "+departure[i]);
}
}
int DFS(int v,ArrayList<ArrayList<Integer>> adj,boolean[] visited, int[] arrival, int[] departure, int time){
visited[v]=true;
arrival[v] = ++time;
ArrayList<Integer> list = adj.get(v);
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()){
Integer i = iterator.next();
if(!visited[i]){
time = DFS(i,adj,visited,arrival,departure,time);
}
}
departure[v] = ++time;
return time;
}
}
