Like the explanation. But don’t you think we need an outer for loop outside while (!q.isEmpty) to travel the whole graph because it may be possible that, since it’s directional graph, not all nodes can be reached from the starting point node that we add in the queue. This main point is missed in the video.
2:30 Just a notice, 3-4-2 should not be underlined with a single line as 3-4 and 2 are from different levels;) 5:15 I would've inserted such line: if(current.isVisited()) continue; This would not create new nesting level;)
Great explanation and visualization. Question, could you move the if not visited check to only add non visited neighbors, which would mean you would never poll a visited vertex? Not sure if that makes sense or even works, but I was just curious.
Hello :) Glad you liked it! I am not sure I got you, but there is always a way to code what you have in mind! Everything "works"! Now to explain a bit: in this example, and in BFS, with every iteration we are adding all the neighbors to the queue, which may lead to duplicates or to have vertices that have been already visited through difference paths, hence the visited-check. Even if you wanted to pre-filter your vertices before polling, you will have to do this with every iteration as they are being updated at the end of every round. Hope this answers part of your question. Cheers!
Pretty comprehensive and high-quality review. Liked it. Though, small remark: plz, place this video as the second in playlist: it is the second by sense but placed third. Meanwhile dfs is placed second but it announces bfs as already covered:))
What happen if Vertex A and Vertex B are both pointing to Vertex D? this algorithm will add D to the queue twice. One time as an adjacent to A and second as adjacent of B. This violate the rule that ever node is visited once. It is true that we will not actually visit it again since when it will be pulled out of the queue for the second time it will be marked as visited. Yet, it will be added to the queue twice. This is double work. I wonder if we could avoid this.
You can do anything! In your case, we could move the check to only add to the queue vertices that haven't been visited yet! I guess that'll do it, right? Cheers!
Hello :) We are passing it to the constructor at around 4:10 as you can see. And we also made use of this attribute at around 6:02 (v1). Hope this answers your question! Feel free to check our Git repo if the code is still not clear. Cheers!
Hello :) In this implementation it is done in a way that if B is a neighbor of A then you can go from A to B, you will have to also set A to be a neighbor of B to go the other way! Hope this answers your question :) Cheers!
@@geekific sorry..let me rephrase my question. how do you represent directions in the object? like say the graph is directed from a -> b -> c. how would the traversal algorithm know which direction is the edge moving?
Hey, sorry if my previous answer wasn't clear enough :) If your graph is directed a -> b -> c, then in this implementation, c is a neighbor of b and b is a neighbor of a. b is not a neighbor of c, and a is not a neighbor b, therefore the algorithm will know that the graph is moving from a to b to c. Hope this was clearer!
Nope. Because of that we are only invoking this call on unvisited neighbors (we are checking if it is visited before adding its neighbors), at some point all the nodes in the queue will be visited and the logic inside the if-statement will be skipped. Your method works as well! We can move the check to the level of each neighbor, both work, but it is not a bug.
This is by far the best BFS explanation I have found on TH-cam. The animation definitely helps
Glad it was helpful :)
Like the explanation. But don’t you think we need an outer for loop outside while (!q.isEmpty) to travel the whole graph because it may be possible that, since it’s directional graph, not all nodes can be reached from the starting point node that we add in the queue. This main point is missed in the video.
Just found this channel today while frantically studying for my final. Great examples with simple explanations.
Glad it was helpful! Best of luck with your finals!
I am surprised this guy only has 5k subs. Isn't he one of the top educators on TH-cam?
incredible explanation Geekific, keep going
Thanks, will do!
awsome video really helped alot thanks ❤❤
Glad it helped
Good explaining, Thank You Sir
Glad you liked it :)
Thank you. This is very interesting, if my teacher wasn't such a horrible person i would enjoy learning this
It's really superb!
Glad you think so!
2:30
Just a notice, 3-4-2 should not be underlined with a single line as 3-4 and 2 are from different levels;)
5:15
I would've inserted such line:
if(current.isVisited()) continue;
This would not create new nesting level;)
Nice observations! Good work :)
Why didn't you made the setNeighbors for V2, V3 and V5?
Great explanation and visualization. Question, could you move the if not visited check to only add non visited neighbors, which would mean you would never poll a visited vertex? Not sure if that makes sense or even works, but I was just curious.
Hello :) Glad you liked it! I am not sure I got you, but there is always a way to code what you have in mind! Everything "works"!
Now to explain a bit: in this example, and in BFS, with every iteration we are adding all the neighbors to the queue, which may lead to duplicates or to have vertices that have been already visited through difference paths, hence the visited-check. Even if you wanted to pre-filter your vertices before polling, you will have to do this with every iteration as they are being updated at the end of every round.
Hope this answers part of your question. Cheers!
Pretty comprehensive and high-quality review. Liked it.
Though, small remark: plz, place this video as the second in playlist: it is the second by sense but placed third. Meanwhile dfs is placed second but it announces bfs as already covered:))
Done! Thanks for the feedback!
@@geekific
No, thank You for nice material☝🏼
Excellent video
Glad you liked it
What happen if Vertex A and Vertex B are both pointing to Vertex D? this algorithm will add D to the queue twice. One time as an adjacent to A and second as adjacent of B. This violate the rule that ever node is visited once. It is true that we will not actually visit it again since when it will be pulled out of the queue for the second time it will be marked as visited. Yet, it will be added to the queue twice. This is double work. I wonder if we could avoid this.
You can do anything! In your case, we could move the check to only add to the queue vertices that haven't been visited yet! I guess that'll do it, right? Cheers!
Does the order matter when it comes to polling from the queue?
It depends on the application you are using it for, most of the time it won't!
superb
I think you may have forgotten to pass startVertex as a parameter in traverse() function ? Correct me if I am wrong
Hello :) We are passing it to the constructor at around 4:10 as you can see. And we also made use of this attribute at around 6:02 (v1).
Hope this answers your question! Feel free to check our Git repo if the code is still not clear. Cheers!
At th-cam.com/video/9Oev6UgLhiI/w-d-xo.html how are you setting the directions in the graph?
Hello :) In this implementation it is done in a way that if B is a neighbor of A then you can go from A to B, you will have to also set A to be a neighbor of B to go the other way!
Hope this answers your question :) Cheers!
@@geekific sorry..let me rephrase my question. how do you represent directions in the object? like say the graph is directed from a -> b -> c. how would the traversal algorithm know which direction is the edge moving?
Hey, sorry if my previous answer wasn't clear enough :) If your graph is directed a -> b -> c, then in this implementation, c is a neighbor of b and b is a neighbor of a. b is not a neighbor of c, and a is not a neighbor b, therefore the algorithm will know that the graph is moving from a to b to c. Hope this was clearer!
@@geekific yes..now clear
Algorithms rise up
There is a bug. By using queue.addAll() you are putting every neighbours in without checking whether they are visited/queued already.
Nope. Because of that we are only invoking this call on unvisited neighbors (we are checking if it is visited before adding its neighbors), at some point all the nodes in the queue will be visited and the logic inside the if-statement will be skipped.
Your method works as well! We can move the check to the level of each neighbor, both work, but it is not a bug.