Depth First Search Algorithm
ฝัง
- เผยแพร่เมื่อ 16 ก.พ. 2013
- This is one of the important Graph traversal technique. DFS is based on stack data structure.
Analysis:
The time complexity of DFS using Adjacency list is O(V + E) where V & E are the vertices and edges of the graph respectively. - วิทยาศาสตร์และเทคโนโลยี
this 4 minute video explains better than my prof did in 1 hour
same here
same here
One of the better professors I had barely spoke english and we could hardly understand him but all he did was teach what we needed to know and did examples, even though we barely understood what he said (like 50% of it we kinda got) the examples made sense as he did them along the way and we ended up having the last 2 and a half lectures be just show up, "do you have question" "no okay we can review but you can go if you want" so we all just left
same here :v
thats because professors can't common sense they only know logic thats why they will always suck compared to looking anything up on google lmfao
I had trouble understanding the pseudo code given in class... your explanation is precise and to the point. I find it very easy to relate it to my pseudo code. Thank you very much!
Difference between depth first search & breadth first search:
BFS looks at each adjacent node and doesn't consider the children of those adjacent nodes.
DFS looks at each adjacent node, and looks at all the children of the current adjacent nodes. It again, looks at the children of the next adjacent node (adjacent to the children of the prevoius).
I just remember it like stack(dfs) vs queue(bfs) after watching these youtuber videos.
So depth first search is a pedophile?
@@jakeryker546 XD
@@jakeryker546 this shit has me dyin rn 😂😅
Best video for depth first search : th-cam.com/video/sxCp1lUxwtw/w-d-xo.html
At the peak times to attend the exam it is very useful 😛😀😀😀
Yes... watching this at very last minute before exam 😎
Yeah
Thank you very much for your video. Abut 4 minutes of your explaining is more effective than my teacher explain 1 hours
LOL
thing adds up
this is too true
this is a simple search strategy, but i have trouble handling with some misunderstanding about the stack. your video had solved it nice and tidy. i have no confusion now. thanks a lot.
Best DFS animation ever watched. Thank you man!
Hey, again, can you add the discovery (d) and finalization (f) times? thanks
So the differences between depth first search and breadth first traversal are:
a)Breadth traversal has a queue but depth search has a stack
b) The other difference you will notice with node C at 2:13. In breadth traversal the result would be C D E F, in depth it is C D E H.
other difference at 1:30 where in depth the result is S C D but in breadth it is S C G
Someone down there added a little bit more: Breadth First traverses each level of the graph, irrespective of the children of each node. Depth first search traverses the children of a node, irrespective of the level of the graph.
csandreas1 you are legend
so we will pop it off
And a poo poo purru booom
Skiyaaa
pop pop pop thats what ur brain is filled off.....niga
@@nandkishorenangre8244 You are disgusting
Which country?
@@nandkishorenangre8244 could you not fucking speak
Very clear, clean to the point. Thank you very much!
this short video conveys the message very effectively..nice work
Was a whole lot easier coding it from your example than reading pseudo code, thanks a bunch, great videos
Very clear and easy to understand the concept of dfs - pls make more vids
That was truly an appreciation to our hard work. Thanks Namitha.
If you like the video, do subscribe for more such video. You can explore other videos too. I hope you'd like those too. Do share it across your friends.
Thank you for sharing your knowledge with us! had an easier time understanding this way
You have forgotten to mention the most imp point -
1) This is iterative version of DFS ( there is a recursive version too )
2) This DFS will only give you all connected components within the same SCC.
Anythign disconnected is not seen
Awesome videos. Simple explanation. This was exactly what I needed. Sometimes it's just nice to see how an algorithm works than to see the code only and struggle to guess what's going on in it.
I know that this comment was made 8 years ago, however, I am curious to know if you have by now found a career for yourself following the field of computer science/engineering.
I learnt DFS in less than three minutes, compared to 40 hours of a semester -_- Thank you so much, this made DFS so easy! :)
true got exam on this at 5 pm
good job mate...this video was real helpful for understanding..please next upload about the explanations to the algorithms of these searches.
Hi. I have a question how can we look for cycles in the graph from this approach? Please let me know.
Thank you! Very good explanation; simple and effective.
Very specific explanation and great tutorial. Thanks
If the ADT, Stack, is used, the implementation is non-recursive (iterative). If the code refers to the pseudocode of non-recursive DFS in Wikipedia and the neighbors are pushed onto the stack in alphabetical order, then the output sequence should be ASGHEFCDB; moreover, A should be popped immediately after it is pushed onto the stack.
thanks, for sharing your knowledge with beginners like me. this video helped me a lot.
thank you sir, it helps me so much to understand the bfs and dfs algorithm! :)
in case of alphabets do we have to use of alphabetic order regardless of the structure ???
better !!!
This is one of the best video for DFS in the whole internet
Very nice - but D is added a bit late to the output sequence - when D is popped off, rather than when it is added.
Please do a video just like this for Dijkstra's algorithm.
Looking at S , the next Elements in Stack should be C ,G oder ?
thanks for your feedback Bharat. If you like the video, do share it across your friends and subscribe for other upcoming videos too.
Thanks for such a clear explanation.
I would consider your comments as a Appreciation namitha. If you like the videos, then do subscribe and share it across your friends.
This video helps me to do my report in Data structure and algorithm thank you so much! 💛
Concise and precise. Thanks a lot!
Thank you so much,
All the best for everyone.
Stay safe 💪
could you post your hand written pseudo code on how to solve this problem
we can choose any vertex as a starting point??
Thanks man.. You are awesome!
I have learned DFS in a versy short time.
Thank you for the explanation! It helped me answer all the edge cases that I was thinking about!
Thank you for your time and clear exposition. From watching this and the breadth first search video I have gathered the following: A depth first search is a breadth first search with a stack instead of a queue which causes a different traversal because of the LastInFirstOut property of a stack versus the FirstInFirstOut property of a queue. Is this in the ballpark?
ForcesOfOdin more or less, you got it the wrong way around, the main difference between BFS and DFS are exactly what their name implies, breath vs depth. On one hand, bfs will search every node in the same distance from the origin first and move by layers, on the other hand, DFS will continue going deeper and deeper into the graph searching by depth first and only then coming back up! There is indeed a difference between the structures used in each but the difference in the way they work is what calls for the diferent structures, not the other way around!
Hope i was clear :/
Miguel Vera it helped me, thanks!!!
Miguel Vera You are correct, of course, in your qualitative description of the two algorithms. However it's wrong to argue as you have. The only difference, between the two algorithms is the data structure used to store nodes which have been discovered until those nodes can be procesed and marked "visited". The first in first out property of Queue's causes the node visitation order to process every node at the current depth from the source node before any node at the next depth from the source. The LAST in first out property of the Stack data type is what causes the nodes children (which were added after the source node) to be explored in the next iteration rather than the nodes siblings.
I'm not saying it's the data set that determines the algorithm , nor am I disagreeing with what you say, that the algorithm type creates the need for the specific data set, i'm actually saying something stronger.The causation can go either way. This implies, that you can discover new algorithms by replacing the data structure. If I use a priority Queue, for example, my implementation of the prirority sorting completely determines the node traversal order and thus the algorithm. Again, I'm saying that you can start with EITHER the data set or the algorithm , and you uniquely and consistently come up with the other. If you start with BFS you need a queue. if you use a queue you get BFS. Do you see ?
This article I'm linking is much better written than my post (I do hope I wasn't to rambly /confusing but multiple sources cant hurt).
jeremykun.com/2013/01/22/depth-and-breadth-first-search/
Very helpful. Thanks for the video.
Thanks a lot for this wonderful explanation.. DFS can't be explained any better than this..
thanks, this clarification made implementations easier
How am I supposed to know, which Children I choose first (S or B). You´ve said "we go alphabetically". But is there any rule for picking One out of two childrens coming up the same parent node?
This video is helpful for me. Thank you!
thank you so much sir. Well explained in just 3 minutes thank you.
when s is vistied we pop it from stack and at the place of s we add c or g
Thank you! Thank you! I'm now halfway done with my assignment!
I don't know u are reading my comment but this vedio is one of the best than the other you tube videos 😊
bro thank you, so enjoyable to watch
DFS gives spanning tree or forest ... where it is .... ?
Your DFS stack is a functional stack, which is related with recursive function call.
But if you mean the stack is a kind of memory type, (not recursive function call) 'G' may be pushed in the stack before pushing 'D'.
So my suggestion is that you should give the information that your stack type is a recursive function not the stack array.
Simple and to the point.. good... although add D to the output immediately you added it to the stack instead of after the pop...
thanks bro for smoothly understanding us
unique way of clear explaination..
Great Video In A Very Short Amount Of Time.
So that means you have to always push all the nodes into the stack first And then pop them one by one?
So, finally, after watching 2-3 videos, I got it !!!
Very well explained
Love and support
Thank you very much! It made a great help for me to understand this one in simpler way.
Smooth af😎 understood in secs💯🙏🏻
Excellent explanation!
Short and simple explained, thanks!
thank you for your effort .
Great video. Thanks! :)
Awesome. Nice and clear. UK Computer Science teacher.
Well explained,Thank you boss
Very well explained!
Where we apply DFS & why ???
I think the algorithm you describe will only work for a connected graph
thank u fr ur clear explanation sir!!!...
Great explanation!
This is DFS WITH Huristic ! Right?
very simple explanation good job
Is it necessary to go alphabetical order
thank you ! It's very useful for me to understand this algorithm ^^
Months of shitty theoretical concepts and this video on only 4 minutes i understand more and better. Thank you very much for your video.
Everything is seems to be good but I have one question????? For B and D we don't have any place to go. For B, when you have visited you add it in the output sequence and also stack before pop it from stack. Bur for D you first add it on stack then pop up it and then add it to the output sequence. Actually which one is correct?
adding to output seq. while popping is correct(actually doesn't matter)...
Oh, well my lecturer is referring to this video on her phone to teach us. That's great (sarcasm intended).
Great video ! Even I understood
Thanks a lot for this!!
Thanks for uploading such a great content in quick time :)
Nice video! thank you!
Thanks for saving my time :)
The output should be displayed in the reverse order in which you have it in the video, because you're popping from the top of the stack, meaning the most recent element pushed in should be the first element popped out and returned to the output AKA Last In First Out(LIFO).
This is very helpful!
thanks for your effort
This seems to be wrong. You push to the stack all the adjacent nodes of the current node, then you pop out one of them and etc. en.wikipedia.org/wiki/Depth-first_search
Very interested...Thanks a lot
thanks for the short and sweet explaination bro
great explanation!
nice explanation ..thank u so much
when you visit S, you need to add G then C, instead of just adding C to the stack
Very good explanation
Simple and clear..
Very helpful!
AWESOME DUDE
Allah razı olsun :) çok yardımcı oldu.