*** 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.
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!
First 6-7 lectures relating to theory are in order. After that ordering is not maintained for Leetcode examples. Definitely needs some proper ordering for those examples as well. Will have a look.
Here's the Java code for your reference: class Graph{ private int m_V; private List[] m_adj; private int time; Graph(int v){ m_V = v; m_adj = new LinkedList[v]; for(int i=0;i
Take the Python code for DFS from this github: github.com/KnowledgeCenterTH-cam/Graphs/blob/master/DFS Ignore the DFS_it(). Just take DFS_rec(), and add the 2 time stamps before and after dfs. So it will be like this: def DFS_rec(self, s, visited): visited[s] = True self.time += 1 self.pre[s] = self.time print(s) for u in self.m_adj[s]: if not visited[u]: self.DFS_rec(u, visited) self.time += 1 self.post[s] = self.time And in the main dfs: add the lists pre and post, and variable time to self. That should do. References: github.com/KnowledgeCenterTH-cam/Graphs/blob/master/DFS github.com/KnowledgeCenterTH-cam/Graphs/blob/master/Pre_Post_Visit_Times_DFS
*** 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.
What a nice video! I really wish to see the video of using this algorithm to solve actual problems
Make videos on Tarjans algo ! Along with LeetCode example of any SC Components.
Also thank you for your work !
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!
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
First 6-7 lectures relating to theory are in order. After that ordering is not maintained for Leetcode examples. Definitely needs some proper ordering for those examples as well. Will have a look.
How to undirected graph start and end time
Nice explanation....
Thanks.
you're a legend
Haha. Nope.
Here's the Java code for your reference:
class Graph{
private int m_V;
private List[] m_adj;
private int time;
Graph(int v){
m_V = v;
m_adj = new LinkedList[v];
for(int i=0;i
Thanks for sharing.
Thanks
Welcome
Can you please share python code for this.
Take the Python code for DFS from this github: github.com/KnowledgeCenterTH-cam/Graphs/blob/master/DFS
Ignore the DFS_it(). Just take DFS_rec(), and add the 2 time stamps before and after dfs. So it will be like this:
def DFS_rec(self, s, visited):
visited[s] = True
self.time += 1
self.pre[s] = self.time
print(s)
for u in self.m_adj[s]:
if not visited[u]:
self.DFS_rec(u, visited)
self.time += 1
self.post[s] = self.time
And in the main dfs: add the lists pre and post, and variable time to self.
That should do.
References:
github.com/KnowledgeCenterTH-cam/Graphs/blob/master/DFS
github.com/KnowledgeCenterTH-cam/Graphs/blob/master/Pre_Post_Visit_Times_DFS