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 ❤
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 !
if you could also explain uniform-cost search, depth-limited, iterative deepening and bidirectional would be amazing ! great vids, learning a lot from you.
so when FBI wants to find the king terrorist, they grab one of his associates - throw that guy into stack - interrogate - get the names - grab next associates - interrogate - get the names - until suspect == king terrorist. THEY WERE USING DFS ALL THIS TIME 😁😁😁
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.
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"?
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
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.
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
dieses visited array braucht man doch garnicht, weil sowieso der current node gleich vom stack gepoppt wird und somit dessen childs nur einmal in den stack kommen koennen, oder?
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.
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')
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
@@Fatbatman3452 in one lifetime bro
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 ❤
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 !
brother said im going to teach you DFS in 4 min and went on to teach DFS in 4min. kudos
🫡
Ehy Michael, I only watch your videos because your explanations are clear (many slides) and straight to the point. Thank you
Appreciate it, Francesco!
Consice, straight-to-the-point and very easy to understand! Great video!
Just stumbled upon your channel and all your videos are so short yet informative. Thank you!
such an underrated channel, you help me so much in reviewing these algos. thanks!
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.
Thanks a lot for the new videos!! Hope you are back definitely!
the right video to be free from confusion
if you could also explain uniform-cost search, depth-limited, iterative deepening and bidirectional would be amazing ! great vids, learning a lot from you.
Thanks a Ton! I have my data structure exam today 😁.
Welcome back too 🥳🥳
Thanks man. Perfect explanation and understandable code!
so when FBI wants to find the king terrorist, they grab one of his associates - throw that guy into stack - interrogate - get the names - grab next associates - interrogate - get the names - until suspect == king terrorist. THEY WERE USING DFS ALL THIS TIME 😁😁😁
That's a funny way to put it🤣🤣
An underrated channell💔🎀
OG Michael back at it again 🎉🎉🎉
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.
Thank you lots, your channel is super informative.
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.
Thanks. This is a great explaination.
I'm so happy that you start to post videos again.
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).
RETURN OF THE KING
This channel is perfect!
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
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 ?
So clear and conscise, thank you!
Beautiful job.
Thank you I have subscribed to you
Thank you!
Only thing, deque and all is not pre defined u have to code that too or make a class Node,Stack,etc...
finally you updated!
Back with a Bang!!
*Why would it be big O of vertices AND edges? The edges aren't being visited or added.*
I never thought about dfs as the "opposite" of bfs... thank you
Great content! Thanks!
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.
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
Absolute KING
yooo he's back. lesgooo
if time complexity is the same, why choose dfs over bfs, or vice-versa?
bfs is for copy tree, dfs is for delete tree.
The Legend is back
so, is dfs in tree same as its preorder traversal?
Thank you, Your voice reminds me of Batman's voice "Where are they?"
Welcome back man :D
Very Intuitive, thank you
dieses visited array braucht man doch garnicht, weil sowieso der current node gleich vom stack gepoppt wird und somit dessen childs nur einmal in den stack kommen koennen, oder?
Why add both visited and stack? Why just one i don't understand 😢
you really save my life !!!!!
💪🏼❤️
Welcome back :)
good video.
great video
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.
Thanks💞💓
Is this a pre order traversal?
I am wondering the same thing have you found the answer
Why is graph[s] reversed?
This is just so the output matches the recursive version (shown is the iterative code).
I have a question why are are you popping a whilst we are still items in a thats wrong kaa
The code you have shared for dfs is incorrect. It works like bfs.
github.com/msambol/dsa/tree/master/search
Awesome!
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?
Nice !
King!!
Welcome back
Thanks
Shout out to the Computer Science majors in the comment section .
🇧🇷 thankssss
thx
Lex Fridman ?
fyi git hub link is broken
fixed, thanks!
The code seems wrong.
Which part?
kod yok
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')