Pre and Post visited Times in DFS | Graphs | Pre and Post numbers

*** CLARIFICATION: At 5:40, I said all the edges will go from Left to Right. It was for DFS Tree edges only i.e., edges we used in DFS. There will be Back edge going from right to left.
In DAGs there will be no Edges from Right to left.

Lesson 7: Depth First Search Pre and Post Numbers
--------------------------

#Graphs #GraphTraversal #DFS #DepthFirstSearch #PrePost

[KnowledgeCenter]

*** CLARIFICATION: At 5:40, I said all the edges will go from Left to Right. It was for DFS Tree edges only i.e., edges we used in DFS. There will be Back edge going from right to left.
In DAGs there will be no Edges from Right to left.

[MrSun]

What a nice video! I really wish to see the video of using this algorithm to solve actual problems

[digantgupta]

Make videos on Tarjans algo ! Along with LeetCode example of any SC Components.
Also thank you for your work !

[RajeshKumarsep]

These pre and post timings refer to the timings the node is added (pre) to the stack and then removed (post) from the stack. Makes things easier and need no memorization! Try to visualize the stack and you are all set!

[naidusunny]

Can you please add the lecture no also so that it will be easy to view videos in order, youtube playlist shows videos in random order

[bhattibhatti]

How to undirected graph start and end time

[AmanVerma-orge]

Can you please share python code for this.

[sanskritinannore]

Here's the Java code for your reference:

class Graph{
private int m_V;
private List<Integer>[] m_adj;
private int time;

Graph(int v){
m_V = v;
m_adj = new LinkedList[v];
for(int i=0;i<v;++i){
m_adj[i] = new LinkedList<Integer>();
}
time=0;
}

public void addEdge(int u, int v){
m_adj[u].add(v);
// adj[v].add(u);// Undirected

}

public void DFS(){
boolean[] visited = new boolean[m_V];
int[] pre = new int[m_V];
int[] post = new int[m_V];
for(int i=0;i<m_V;++i){
if(!visited[i]){
DFSUtil(i, visited, pre, post);
}
}
System.out.println();
for(int i=0;i<m_V;i++){
System.out.println( i +":"+ pre[i] +", "+ post[i] );
}
}

public void DFSUtil(int v, boolean visited[], int[] pre, int[] post){
visited[v] = true;
pre[v] = ++time;
System.out.print(v + " ");
for(int i : m_adj[v]){
if(!visited[i]){
DFSUtil(i, visited, pre, post);
}
}
post[v] = time++;
}

public static void main(String args[])throws java.lang.Exception{
Graph G = new Graph(5);
G.addEdge(0, 1);
G.addEdge(0, 3);
G.addEdge(1, 2);
G.addEdge(3, 2);
G.addEdge(3, 4);
G.DFS();
}
}