Awesome videos! I like how you use real world examples for data structures, which help to visualize the structures as they would actually be implemented.
+alivfishland There are a lot of other videos out there to compete with. If enough people watch and like a video, it will go up in reputation, and perhaps in a year or two it will start to show up high within search engines. Right now, the heap series shows up okay, but it took a while to get there, and that series had the head start of a reference from the "beta release" on my previous channel, which had a 2 year head start. So basically, in 1-3 years, hopefully more videos on this channel will do well. If they help you out, let your friends know it is helpful, maybe it will only take half as long.
+Algorithms with Attitude yea I actually discovered your channel through the heap videos too and subscribed. I know there are plenty of other videos out there and watched quite some of them, but this channel is definitely one of the better ones. i like how your slides contents change as you teaches. This alone shows how much effort you put into making these videos. I will definitely tell my friends about yoir channel.
at 5:27, is the $time variable 'u.discovery = time++' and 'u.discovery = time++' some sort of global static variable? does recursive calls toDFSVertex(v) each increment this variable (twice per call).
I suppose it might be implemented as a graph variable, while the discovery and finish times are vertex variables. If calculated, these just help to record the order in which vertices are explored, which can be useful in ways we will get to.
Hi, May you please explain how you get the finishing times for every vertex, that's the one thing that confuses me. For example at 5:03 , vertex G gets a finishing time of 5, then vertex B gets a finishing time of 6 then there's a massive jump in size where vertex C somehow gets a finishing time of 9. But how, thanks a lot in advance.
Each step is named in the video, but at a much quicker pace than prior steps, and without naming every single variable assignment. So, immediately after G finishes, B finishes (time 6). (I say so it (B) is done, instead of "B finishes".) We return to D and discover F from it (time 7), and then F discovers C (time 8) which has nothing new to discover, so C finishes (time 9). There are no "jumps" in the time assignments, the video does them in order, I just start going faster after the first half of the graph is completed. If needed, watch from 5:00 to 5:25 at half-speed, you should see each step separately.
I understand the simple implementation of DFS has a runtime of time of O(|V| +E). However, shouldn’t your detailed implementation of DFS (at ~4:13 mark) have a runtime of O( V* (|V| +E) ) due to the outer loop in the DFS() method. We are *touching every vertex twice, once to discover it and the second time to see if it has been discovered. Due to the reset, the entire runtime will be O( |V| + V* (|V| +E) ), which is then reduced to O( V* (|V| +E) ). I’m correct? Also, why do you have |V| in your runtime of the graph, instead of a simple V? What is the difference between |V| vs. V? Thank again,
First, notation. V is the set of vertices. E is the set of edges. |V| is the size of the set of vertices, it should be |V| and |E| throughout the slides (let me know if it isn't somewhere). DFS is linear, O(|V| + |E|): reseting the graph takes linear time. After that, you call DFSVertex once on each vertex. (Any other time you "touch" the vertex, when it is already discovered, that takes constant time, and happens due to the edge leading to the vertex.) So, you can call the conditional in DFSVertex once per edge, and only step into the vertex once each.
Sorry I'm confused. Can anybody help me? In the non-recursive implementation. How do I implement " x.isVertex() "? It is supposed that we do pop() to vexter only. Thanks.
For my version, you can push edges as well (during the middle line of vertex exploration) as well. This might not be such a standard approach, but it allows all of the bells and whistles like edge labelling in the same runtime, without needing to use iterators or any other method to track which edges you have handled from any given vertex. Probably there are cleaner ways, but I didn't actually look anything up for this code. I suppose I should have.
Thanks a lot. I implemented Kosaraju's algorithm with your're non recursive DFS, then I tested with 875714 vertices and 5105043 edges, and It runs blazingly fast with less than 4 seconds.
What is the "output" of a graph? I don't know what you want to print. But, if each node has some information in it that you want to print, you should be able to add that into the given pseudocode for DFS. The general purpose of the videos is to explain the idea behind DFS, from the high level down to pseudocode. When it comes to coding some specific variant, if you understand how the algorithm works, it is kind of up to you to code that variant.
By far one of the best video on DFS.
I have an exam on graphs tomorrow and you helped me finally understand everything! Thank you!
+Felipe Custódio Just in time with this one, I guess. Good luck.
Significantly easier to follow than the professor I am paying thousands of dollars a semester... Thank you so much!
Tell classmates...
To be fair, I probably confuse my students in person too.
Playback helps significantly.
Hahah "what's that smell" - I am so glad I found these. You explain it well without being superficial, and the examples are great!
Awesome videos! I like how you use real world examples for data structures, which help to visualize the structures as they would actually be implemented.
Deserve more viewers &subscribers. Please Keep up the good work, I learned a lot from your videos.
+alivfishland Thanks.
+alivfishland There are a lot of other videos out there to compete with. If enough people watch and like a video, it will go up in reputation, and perhaps in a year or two it will start to show up high within search engines. Right now, the heap series shows up okay, but it took a while to get there, and that series had the head start of a reference from the "beta release" on my previous channel, which had a 2 year head start.
So basically, in 1-3 years, hopefully more videos on this channel will do well. If they help you out, let your friends know it is helpful, maybe it will only take half as long.
+Algorithms with Attitude yea I actually discovered your channel through the heap videos too and subscribed. I know there are plenty of other videos out there and watched quite some of them, but this channel is definitely one of the better ones. i like how your slides contents change as you teaches. This alone shows how much effort you put into making these videos. I will definitely tell my friends about yoir channel.
thats true!! this guy is amazing!!! fantastic!
The video was very helpful and contributed massively to my coursework considering how short it was. Thanks!
Finally, most informative info on DFS and I've been looking for an hour. Thanks!
These videos were great, very well explained!
I enjoyed seeing Latex used in your presentation. :)
7:58 - Was that a deadpan reference to the AC/DC song, or have I just watched this video one too many times?
I kind of blew it by having vertex B highlighted instead of C. Oh well.
at 5:27, is the $time variable 'u.discovery = time++' and 'u.discovery = time++' some sort of global static variable? does recursive calls toDFSVertex(v) each increment this variable (twice per call).
I suppose it might be implemented as a graph variable, while the discovery and finish times are vertex variables. If calculated, these just help to record the order in which vertices are explored, which can be useful in ways we will get to.
VERY WELL!! NICE EXPLANATION
very helpful
It was so helpful. Thank you so much sir!
Thanks.
Kinda used 11:07's DFS(G) in the 23-tree lab. I've used something similar when writing a filesystem scanner but didn't know it was called DFS.
Excellent explnation!
How is equilibrium used in video games exactly
Great content!, thank you!. You got one new Subscriber!
beautiful explanaton...
For the last line of RESETGRAPH(G), shouldn’t it be time = 0?
What time in the video?
Hi, May you please explain how you get the finishing times for every vertex, that's the one thing that confuses me. For example at 5:03 , vertex G gets a finishing time of 5, then vertex B gets a finishing time of 6 then there's a massive jump in size where vertex C somehow gets a finishing time of 9. But how, thanks a lot in advance.
Each step is named in the video, but at a much quicker pace than prior steps, and without naming every single variable assignment. So, immediately after G finishes, B finishes (time 6). (I say so it (B) is done, instead of "B finishes".) We return to D and discover F from it (time 7), and then F discovers C (time 8) which has nothing new to discover, so C finishes (time 9). There are no "jumps" in the time assignments, the video does them in order, I just start going faster after the first half of the graph is completed. If needed, watch from 5:00 to 5:25 at half-speed, you should see each step separately.
Algorithms with Attitude || Thank you for clarifying that for me and also the quick reply, all your videos are of a great quality.
I understand the simple implementation of DFS has a runtime of time of O(|V| +E). However, shouldn’t your detailed implementation of DFS (at ~4:13 mark) have a runtime of O( V* (|V| +E) ) due to the outer loop in the DFS() method. We are *touching every vertex twice, once to discover it and the second time to see if it has been discovered.
Due to the reset, the entire runtime will be O( |V| + V* (|V| +E) ), which is then reduced to O( V* (|V| +E) ). I’m correct?
Also, why do you have |V| in your runtime of the graph, instead of a simple V? What is the difference between |V| vs. V?
Thank again,
First, notation. V is the set of vertices. E is the set of edges. |V| is the size of the set of vertices, it should be |V| and |E| throughout the slides (let me know if it isn't somewhere). DFS is linear, O(|V| + |E|): reseting the graph takes linear time. After that, you call DFSVertex once on each vertex. (Any other time you "touch" the vertex, when it is already discovered, that takes constant time, and happens due to the edge leading to the vertex.) So, you can call the conditional in DFSVertex once per edge, and only step into the vertex once each.
8:31 did you mean to say "during the lifetime of D" instead of G?
Yes. It looks like I captioned it correctly, but probably read it incorrectly.
Sorry I'm confused. Can anybody help me? In the non-recursive implementation. How do I implement " x.isVertex() "? It is supposed that we do pop() to vexter only. Thanks.
For my version, you can push edges as well (during the middle line of vertex exploration) as well. This might not be such a standard approach, but it allows all of the bells and whistles like edge labelling in the same runtime, without needing to use iterators or any other method to track which edges you have handled from any given vertex. Probably there are cleaner ways, but I didn't actually look anything up for this code. I suppose I should have.
Thanks a lot. I implemented Kosaraju's algorithm with your're non recursive DFS, then I tested with 875714 vertices and 5105043 edges, and It runs blazingly fast with less than 4 seconds.
Nice. That algorithm will be one of my next videos.
Algorithms with Attitude still waiting on SCC (i.e. Strongly Connected Components) by Kosaraju
@@cssensei610 It's up!
haha, I love the closing comment
pseudocode for print output in unweighted graph???
What is the "output" of a graph? I don't know what you want to print. But, if each node has some information in it that you want to print, you should be able to add that into the given pseudocode for DFS.
The general purpose of the videos is to explain the idea behind DFS, from the high level down to pseudocode. When it comes to coding some specific variant, if you understand how the algorithm works, it is kind of up to you to code that variant.
niqqa you good
Non recursive implementation is difficult to understand.
Yt. Lol I’ve done death by search. 😅🙃