Depth-first search in 4 minutes
ฝัง
- เผยแพร่เมื่อ 13 พ.ค. 2024
- 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
You explained in 4 minutes what my data structures professor failed to do in 1 hour. Thank you!
ayifdi hele deme
In one semester bro
@@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 ❤
Thanks a lot! Currently working on Cracking the code interview and found this. Short and precise enough:D Keep it up man.
if you could also explain uniform-cost search, depth-limited, iterative deepening and bidirectional would be amazing ! great vids, learning a lot from you.
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
Appreciate it, Francesco!
Thanks man. Perfect explanation and understandable code!
So clear and conscise, thank you!
the right video to be free from confusion
OG Michael back at it again 🎉🎉🎉
Thank you lots, your channel is super informative.
RETURN OF THE KING
This channel is perfect!
Welcome back man :D
The Legend is back
finally you updated!
yooo he's back. lesgooo
Welcome back :)
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.
brother said im going to teach you DFS in 4 min and went on to teach DFS in 4min. kudos
🫡
Back with a Bang!!
Awesome!
Welcome back
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 ?
Very Intuitive, thank you
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!
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.
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.
He pushed three items onto the stack, forcing G to the bottom.
great video
I never thought about dfs as the "opposite" of bfs... thank you
King!!
Nice !
Thanks💞💓
Thank you I have subscribed to you
Thank you!
so, is dfs in tree same as its preorder traversal?
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"?
Not really, the "in" operation is a lookup in a hash table, so it's constant time O(1), not O(n).
you really save my life !!!!!
💪🏼❤️
Thanks
you said that the graph is stored in an "adjacency list" but isn't that an adjacency map?
Why add both visited and stack? Why just one i don't understand 😢
🇧🇷 thankssss
So the difference between BFS and DFS is simply whether the queue is FIFO or FILO?
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
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
Shout out to the Computer Science majors in the comment section .
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.
Why is graph[s] reversed?
This is just so the output matches the recursive version (shown is the iterative code).
Lex Fridman ?
kod yok
fyi git hub link is broken
fixed, thanks!
The code seems wrong.
Which part?
A for loop in a while loop for dfs smh ? Just learn recursion and no need to impprt anything from collections module.
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')