Depth-first search in 4 minutes
Depth-first search in 4 minutes.
Code: github.com/msambol/dsa/blob/m...
Sources:
1. Introduction To Algorithms, Third Edition (CLRS) [www.amazon.com/Introduction-A...]
2. en.wikipedia.org/wiki/Depth-f...
LinkedIn: / michael-sambol
Пікірлер: 80
You explained in 4 minutes what my data structures professor failed to do in 1 hour. Thank you!
@hesenlihacaga6814
2 жыл бұрын
ayifdi hele deme
@sachinnn3452
7 ай бұрын
In one semester bro
@danieldeda3188
2 ай бұрын
@@sachinnn3452 in one lifetime bro
I had already seen your search and sorting videos , they were concise and helped me first understanding how it works and figuring out everything else in the process , helped the cogs of my brain move a lot !
Just stumbled upon your channel and all your videos are so short yet informative. Thank you!
Consice, straight-to-the-point and very easy to understand! Great video!
My professor was great at teaching DSA but I missed classes due to sickness and various reasons today I have a test I am don't know what I am going to do but thanks to you , your videos are short sweet and minimalistic ❤
These videos are so incredibly well done, efficient, and helpful. Thank you!
Thanks a lot! Currently working on Cracking the code interview and found this. Short and precise enough:D Keep it up man.
I'm so happy that you start to post videos again.
Thanks a lot for the new videos!! Hope you are back definitely!
Thanks a Ton! I have my data structure exam today 😁. Welcome back too 🥳🥳
Ehy Michael, I only watch your videos because your explanations are clear (many slides) and straight to the point. Thank you
@MichaelSambol
Жыл бұрын
Appreciate it, Francesco!
if you could also explain uniform-cost search, depth-limited, iterative deepening and bidirectional would be amazing ! great vids, learning a lot from you.
OG Michael back at it again 🎉🎉🎉
Thanks man. Perfect explanation and understandable code!
the right video to be free from confusion
So clear and conscise, thank you!
This channel is perfect!
Thank you lots, your channel is super informative.
Beautiful job.
Great content! Thanks!
RETURN OF THE KING
finally you updated!
The Legend is back
Very Intuitive, thank you
Back with a Bang!!
yooo he's back. lesgooo
would it possible to link references on how the distance matrix is populated with BFS and DFS? and merits of using a stack vs a queue for DFS ?
Welcome back man :D
Welcome back :)
brother said im going to teach you DFS in 4 min and went on to teach DFS in 4min. kudos
@MichaelSambol
10 ай бұрын
🫡
great video
A stack only has two operations, push and pop. They do not let you add the 3 elements C,D and E before G as you did in the 3rd step.
@brennandolan1683
Жыл бұрын
He pushed three items onto the stack, forcing G to the bottom.
Awesome!
Welcome back
Great video! A have a question (probably stupid, but anyway) about mapping your explanation to your code. So this video says: stack is a list of nodes to be visited; 1) 'A' is a first node to be visited 2) Add it to stack (to be visited) 3) Pop it from stack 4) Mark as visited 5) Add adjacent nodes (to be visited) in stack ... Now according to your code for dfs: 1) 'A' is a first node to be visited 2) You add right away 'A' node to visited array ( visited.append(node)) before popping, so it's marked as visited? 3) You add 'A' node into a stack (to be visited) but 'A' is already been visited according to visited array 4) 'A' node is popped 5) Then you loop through 'A's adjacent nodes (G first) (for n in reversed(graph[s])) marking 'G' as visited ( visited.append(n)); pushed into visited array 6) Then you put 'G' into stack to be visited (stack.append(n)). But 'G' is already in visited, isn't it? 7) Same as point 6) happens with 'B' 8) Pop 'B' from the stack ... Then algorithm proceeds with other nodes pushing into visited before popping them So the question is: am I getting something wrong? What is the indicator of nodes to be marked as visited: being popped from the stack or being pushed into visited? Again in short: -The video states: Add node to be visited in the stack -> pop it -> mark as visited -> add adjacent nodes to the stack -> repeat -And according to code: Mark 'A' as visited(push to visited array) -> add 'A' to stack(to be visited) -> pop 'A' from stack -> loop through 'A's adjacent nodes (mark 'G' as visited, add 'G' to stack, mark 'B' as visited, add 'B' to stack) ->pop 'B' -> repeat Hope I explained my confusion well. Trying hard to get DFS right so I'll be waiting for your response, thanks!
@solracodraude2211
Жыл бұрын
i guess this is not useful for you anymore, since it has been a year, but I caught the same error. In the code, nodes should be added to visited just as they are popped from the stack and not while considering the neighboring nodes.
Thank you I have subscribed to you
@MichaelSambol
Жыл бұрын
Thank you!
I never thought about dfs as the "opposite" of bfs... thank you
you really save my life !!!!!
@MichaelSambol
Жыл бұрын
💪🏼❤️
Hello, great video. I would like to ask you some additional question. List of Stack and list of Visited will be on the evening like this? Stack: A, B, G, C, D, E, F, H, I Visited: A, B, C, D, E, F, G, H, I I am not sure if the List of Stack should preserve all previous values or it is changed continuously.
so, is dfs in tree same as its preorder traversal?
King!!
Nice !
Thanks💞💓
the "in" operation has a time complexity of O(n) though, in this case wouldnt it be O(n!) because you check it for 1,2,3,...n elements when you do "not in visited"?
@lfsever
8 ай бұрын
Not really, the "in" operation is a lookup in a hash table, so it's constant time O(1), not O(n).
Why add both visited and stack? Why just one i don't understand 😢
Thanks
Only thing, deque and all is not pre defined u have to code that too or make a class Node,Stack,etc...
🇧🇷 thankssss
So the difference between BFS and DFS is simply whether the queue is FIFO or FILO?
@MichaelSambol
Жыл бұрын
BFS = queue / FIFO ... DFS = stack / FILO. Note: I chose to teach the iterative approach. You can also do this recursively, and I have examples on my GitHub [1]. DFS (pre/in/post in the code below) is easier to do recursively than BFS (level). [1] github.com/msambol/youtube/blob/master/tree_traversal/traversal.py
please do graph data structure code implementation in python
you said that the graph is stored in an "adjacency list" but isn't that an adjacency map?
Is this a pre order traversal?
I have a question why are are you popping a whilst we are still items in a thats wrong kaa
kod yok
Why is graph[s] reversed?
@MichaelSambol
2 жыл бұрын
This is just so the output matches the recursive version (shown is the iterative code).
fyi git hub link is broken
@MichaelSambol
2 жыл бұрын
fixed, thanks!
Shout out to the Computer Science majors in the comment section .
This is a good explanation, but it is for a tree not a graph. I don't think the arithmetic version would work for a graph since there is no real root. You would have to use recursion for a true graph
Lex Fridman ?
The code seems wrong.
@MichaelSambol
2 жыл бұрын
Which part?
Isn't the algorithm works best, if we continue to add vertices till we reach leaf node and in the process of backtracking (popping out of the stack) marking it as visited. While backtracking if any node has children, same process will be applied (adding descendant vertices in the stack till leaf node and backtracking it.
A for loop in a while loop for dfs smh ? Just learn recursion and no need to impprt anything from collections module.
@MichaelSambol
Жыл бұрын
Thanks for the feedback. Yes, can also do it recursively! See examples below [1]. deque is O(1) for append and pop [2], but I did change it to an array so there is no import [3]. [1] github.com/msambol/youtube/blob/master/tree_traversal/traversal.py [2] wiki.python.org/moin/TimeComplexity [3] github.com/msambol/youtube/blob/master/search/depth_first_search.py#L15
Check this sample and give me feedback: from queue import deque def depth_first_search(graph, node): visited = [] stack = deque() visited.append(node) stack.append(node) while stack: s = stack.pop() print(s, end=" ") for n in reversed(graph[s]): if n not in visited: visited.append(n) stack.append(n) graph = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': [], 'D': [], 'E': ['F'], 'F': [], 'G': ['H'], 'H': ['I'], 'I': [], } depth_first_search(graph, 'A')