Step 1: Use English characters as data for each node Step 2: Assign English letters to the nodes in the algorithm and make the explanation confusing. Step 3: Watch everybody struggle
She’s literally explaining what each line of code but not explaining the big picture of the implementation.. confusing explanation of search in the beginning
What do you not understand about the implementation? I think it would help if you first look up Reducible's graph video where they animate stuff to make it easier to understand.
People are getting confused with those 'data' values inside the node circles and the 'variable names' Gayle uses to explain the search process. Heck, I was confused myself. But, start by ignoring the letter values inside the node circles, those are there just to represent data. When Gayle says "I'm going to call this node 's' and this other node 't', she is not talking about the data that you can see inside those circles, she is more likely talking about the variable names that she is going to use to carry out the search process. The 's' node will be the source node, or the node you are using as your starting point. The node 't' will be your target node, the node you are looking for. Watch the video again and you will see how she draws 's' and an arrow, then draws 't' and an arrow. Those are the nodes she is referring to when she says 's' or 't'.
Notice that the space complexity required for the recursive implementation of DFS is O(h) where h is the maximum depth of the graph. This is because of the space needed to store the recursive calls. DFS can also be implemented iteratively following the same idea as BFS but using a stack instead of a queue. This implementation uses O(v) extra memory where v is the number of vertices in the graph.
Issues with this: - This implementation will work for graphs whose nodes are all connected to one another (e.g. every node has a path to every other node whether you have to go down the tree/graph or back up it and then perhaps down again). This will *not* work for _disconnected_ graphs with nodes that are disconnected to one another. Example: 1->2->3->4->5, 6->7->8 (no connection between 1 through 5 and 6 through 8) - Breath First Search was not explained for more than one iteration down the tree. You should really explain using at least two, typically three iterations so people can understand the process of the loop and the decision-making of the loop (e.g. how do we know when to add nodes to the queue, helps explain what happens if there's duplicates).
Something that could have been explained better is the LinkedList nextToVisist procedure. That LinkedList is a queue. So the first time we add the original node, the queue is size 1, inside the while, we remove the first element and obtained at the same time, the queue is size 0. When we add the children, then the queue size grows again and the while can keep looping. THE KEY IS: Understand the LinkedList as a supermarket. The first elements, add more elements, then those child elements are checked first because the elements that each of those adds, are added to the last position to the queue. Lets the first node has 2 children. The first node is checked, then add 2 children, child A and child B. The first child is checked, B, and that child adds C, D, E, but only after the second children. So the third iteration the queue looks like this [C, D, E]. And that is why is breadth-first because the queue makes the children get ordered in the back of the line. So every ancestor is checked first.
For those who wonder why there isn't a nextToVisit.remove() in hasPathBFS(....), thats because you have to use a Queue. She mentioned it at 3:27 So it should be like: private boolean hasPathBFS(Node source, Node destination) { ... Queue nextToVisit = new LinkedList(); while(!nextToVisit.isEmpty()) { Node node = nextToVisit.remove(); .... }
I am not sure this is correct. Removing that check from where it is, triggers unnecessary looping. The idea is to skip unnecessary iterations altogether.
@@hfontanez98 exactly the opposite. Unnecessary looping happens if the visited.contains it's where it is now. Because you add nodes to the queue that were already visited.
Everyone here comlaining about the data and letters for each node blah blah, well I just want to thank you ! I am new at programming and have a project to do for college using graphs, this helped me a lot! Thanks!!
I think this would be the addEdge method that has been collapsed. It's not enough to add the node to nodeLookup, you also need to set it as the adjacent node of whatever node you want to link it to, hence addEdge having the parameters of source and destination.
It is really confusing to use letters as node values and then also use letters as node variables ! At the beginning I was like what we are taking about : S node is actually G node .. what?? I just stopped watching it.
It feels like everybody in the comments thinks they are smarter than her. A messup happens, so what. If you dont count the start, the video teached me the basics and thats why I watched this
As the video goes further I get more confused. First the variable name with mismatching values inside where variable name is the one being referred to without prior knowledge on what she is referring. Once the coding started she started jumping all over the place as if it's the weekend and she has to catch the bus. It would also be nice if we get a copy of the code since getNode was not shown which will allow us to study how the code works ourselves.
Video could be somewhat confusing at first. Specifically the ambiguity of node 's' vs. node 'S'. It's completely clear after a couple of seconds of thought, though still annoying. There is already a node 'S', which is different the node 's' that the narrator talks about. Wasn't sure which 's' she meant after statements as seen below: At 1:07 the narrator says, "Hmm...I'm not sure let me go ask [S's children]". Then immediately after that t is displayed pointing to H, a child of 'S'.
This implementation has a flaw. If you create a graph with, for example, four nodes labeled 1, 2, 3, and 4 and you pass something like graph.hasPathXXX(20, 44) will return true instead of false because the getNode methods can return null both, which will pass the source == destination test. To avoid this, you have to add a case that checks for null and returns false if either the source node or the destination node is null. I tried this implementation at home and was able to confirm it by running a simple test like the one I included above.
In DFT, We can't say if visited has source node then path doesn't exist. Instead we should modify the algorithm as : Algorithm hasPathDFS(source , target, visited) { if(source == target ) { return true; } visited.add(source); for(Node child : sources.adjecent) { if(!visited.contains(child)) { if( hasPathDFS(child , target, visited) ) { return true; } } } return false; } Explanation and examples are really good. Thanks for this video.
The line "if(visited.contains(source.id) return false" is important. It simply means if visited contains the source.id, then there is a cycle and no need to start checking from that source again and again.
It's nice to see that terminology like "boo-boo-boo-boo-boop" has survived the test of time. No shade, I think I've used it in my career at some point.
Well I’m surely going to save this implementation for last to memorize from scratch. Already got Linked Lists, Doubly Linked Lists, Stacks, and Queues down. Currently on trees but Graphs just seem a doozy 😢
I found this BFS code not very efficient. You could've moved the "if (visited.contains(node.id))" condition (without continue statement) in the "for each child" loop. That is, enqueue the child node only if it has not been visited. In this case, we can also ensure the dequeued nodes will always be unvisited (no need to check for continue). The current implementation will redundantly enqueue many visited child nodes, especially in an undirected graph!
Thanks a lot for your code! But, one thing that I wanted to ask just in case: you don't need the visited.add(node.id) right before the for loop in this corrected code as it's already within the for loop (but now adding child.id to visited) right?
I think its relative tradeoff depending upon the connectedness of the graph. In your solution your calling contains across ALL children, including nodes that could have 8000 leaf nodes that will never be revisited. Also, if the node in question is found early, you've still called contains on lots of child nodes that have never been walked yet.
@@KhanSlayer ok but even then the code in the video could lead to an infinite loop. If node is in visited yiy should NOT be adding it to "next to visit".
Instead of adding values in hashset we should add the entire node so that we may not stuck in uniqueness property in graph!! This will solve problem when the graph contains same value but the nodes are different and also their neighbors are different
For anyone still watching this, if you want to run it make a main method and then call the class and set up your Hash Map In your main method: Graph (Whatever name) = new Graph; System.out.println((Whatever name).hasPathDFS(1, 5)); It'll turn true or false depending on how your hash table is set up
I liked the explanations of DFS and DFS algorithms. Did not like that the entire code was not covered or made available. The description seems to be for a bidirectional graph. If there is a path form G -> H then there should be one form H -> G. The implementation of the addEdge() does not allow for it. When I did my implementation I used letters instead of numbers. Found it easier to follow.
Would be nice to see this also return the distance between the nodes. I implemented this by queuing this information together with the node being queued, but I wonder if that's the best way to do it or if there is a more elegant way.
Great explanation madam..respect you.What is the best programming language to learn data structures and algorithms as a beginner??..please answer me madam..
a. thank you for the video. b. i think there is an issue with the BFS function. The entire condition - if (visited.contains(node.if)) - seems meaningless. because no action is taken - whether the condition is met or not.
I think it was confusing because the voice over is little ahead so when she says "I'm gonna call it 's' " - it doesn't appear making us look at the node with value 'S'
If it is an undirected graph, I think the addEdge method should be : public void addEdge(int source, int destination) { Node s = getNode(source); Node d = getNode(destination); s.adjacent.add(d); d.adjacent.add(s); }
I see, so if it's directed then we can have it as. public void addEdge(int source, int destination) { Node s = getNode(source); Node d = getNode(destination); s.adjacent.add(d); } Not sure of this though but that is what I think
I am unable to visualize the graph data structure with this implementation. In the implementation, each node has a linked list of adjacent nodes. That just makes the data structure a very long linked list right? I am unable to correlate this with the graph shown at 2:11. 's' has 2 children - 'a' and 'b'. In this case, what will be the 'adjacent' linked list of 's'?
I don't understand why line 33 (in DFS) has 'return false' ... I understand that if the node has been visited previously from the same node, then there is a loop. So a loop exists in the graph... How does that imply that there is no path to the destination (it could be in another path of the graph?) Thanks EDIT - I just saw the comment below by swapnil gaikwad . He thinks this part of the algorithm is wrong!
I was thinking this is just a sanity check for disconnected graphs? where the destination is not connected, but even then I feel like this condition is unnecessary.
I wish she would actually show how to actually instantiate this algorithm. Like, HOW do I create the tree and then HOW to do I actually call the search methods?
Sorry, it might be my own problem but I am struggling to understand your explaination about the s to t to a b c thing. I feel quite confusing about the figure youre pointing at.
We can actually take all four of her DFS/BFS methods and condense them into a single method as follows (isBFS = true for a BFS, and isBFS = false for a DFS): public boolean hasPath(int source, int destination, boolean isBFS) { LinkedList nextToVisit = new LinkedList(); HashSet visited = new HashSet(); nextToVisit.add(getNode(source)); while (!nextToVisit.isEmpty()) { Node node = isBFS == true? nextToVisit.remove() : nextToVisit.removeLast(); if (node == getNode(destination)) return true; visited.add(node.id); for (Node child : node.adjacent){ if (!visited.contains(child.id)) nextToVisit.add(child); } } return false; }
Node node = nextToVisit.remove() the above method is wrong as remove() method returns a boolean value. Node node = nextToVisit.removeFirst() will work and returns next node to visit.
Honestly for the first 2 minutes, I was so confused I had to come to the comment. Now I see she just spelled the word GRAPH DFS BFS as the nodes. I thought those were the values. It would be better to point that out next time. But Great Explanation!!!
Thanks for the video. Just one question tho. Why is that there's no value in the Node class? I mean there's id and which other nodes are connected to it, but there's no value? Why?
There seems to be a bug in your BFS code. once you find that a nide has already been visited why are you continuing and then adding that same mode back to the que? It should be a if conditoons checking that the node id is "not visited" and then continue and add the node id to the visted que
Is there an efficient way to compute the level of connectivity of a graph? That is the number of vertices (or edges) that must be deleted to disconnect the graph. Or it is this NP hard?
Can someone please explain to me why in the DFS, we return false as soon as we found the node was already visited. While in BFS we continue when we found the node was visited? 🤔
Is the order in graph near the end correct or am I missing something? 5 and 7 are calendar before 6 and 8 but there's no other path connecting them to S
good tutorial I did something similar and just used a vector node pointers...this looks like c++? Also a paired vector is good for holding a node and it edge values Is there a tutorial for searches when node edges have values to find the path with the lowest cost?
Hi everyone, i am learning algorithms. I looked through lots of syllabus and found them interesting, but i dont know what resource to learn them from. Theres a whole list of algorithms and clever tricks i would like to learn, sorting, search, dp, recursion, etc. Please, if you have a good resource to learn these from, they would be very helpful!
To understand a coding topic, I used to check your videos first, it leaves me bit confused, I check other videos, and things become clear then.. You have some good videos but not the coding ones, I think you may work harder to simplify things, you may try to explain the code while linking it with the algorithm. Thanks for your efforts anyways.
That's a great explanation!! One question though, In BFS implementation I haven't seen the use of visited HashSet. shouldn't we check if a node already exists in the set before adding it into the queue?
Hello ma'am, I am new to programming. According to my understanding Node class should not be static. Because we need to create multiple nodes, which means we need many instances of the same class. Please correct me if I am wrong. Thank you
Akshay Chandrachood Static classes are not like static variables. You can create many instances of them. In Java, you can create static NESTED classes for encapsulation. I’m For example, the Graph class can access the Node classes private variables and methods because it is nested. However, functionally, the Node class isn’t different from any other class. In fact, I don’t know why people use static classes at all haha
Ok I see, "if the member or constructor is declared private, then access is permitted if and only if it occurs within the body of the top level class (§7.6) that encloses the declaration of the member or constructor"
Why would you do this(inside hasBFS method): if (visited.contains(firstNode.id)){ continue; } if you are adding node.id to visited list anyway? also we can check the condition below first thing in the method so if it is equal we dont have to go through any extra operation if(source == destination){ return true; }
I didn't quite understand the implementation; Can we use LinkedList inbuilt? what does this mean ? what is adjacent? what is HashSet, what is it doing? what does "for (Node Child : node.adjacent) ? so many questions... Help will be appreciated :)
I love your videos and recently bought your book. Do you have samples of all of the data structures in javascript? That would be a fantastic resource to supplement your material--especially for noobs like me! Thank you.
I think 's', 't', 'a' are the alias of the node. "graph labels" inside of the circle are the node values, could be anything, integers, strings,etc. In this case it just happened to be letters. for example, from node s to node t could mean from New York to Vancouver.
We ask question "Hey S, do you have path to node T?" but there is no node T. But later she points S to G and T to H.... can somebody please explain me this part.
Ignore the letters inside the node circles, those are there just to represent data. When she says "I'm going to call this node 's' and this other node 't', she is not talking about the data that you can see inside those circles, she is more likely talking about the variable name that she is going to use to carry out the search process. The 's' node will be the source node, or the node you are using as your starting point. The node 't' will be your target node, the node you are looking for. Watch the video again and you will see how she draws 's' and an arrow, then draws 't' and an arrow. Those are the nodes she is referring to when she says 's' or 't'.
Step 1: Use English characters as data for each node
Step 2: Assign English letters to the nodes in the algorithm and make the explanation confusing.
Step 3: Watch everybody struggle
Haha! Nailed it! :D
literally that was so confusing and unnecessary!!
Ridiculous video
Step 4: Boop Boop Boop
Step 5: Profit $$$$$$$$$$
Hahaha. Exactly
You guys are experts at making things more confusing than they already are..
She’s literally explaining what each line of code but not explaining the big picture of the implementation.. confusing explanation of search in the beginning
100%
What do you not understand about the implementation? I think it would help if you first look up Reducible's graph video where they animate stuff to make it easier to understand.
Fr
That's how you become the person who decides what we all have to learn to get a job.
People are getting confused with those 'data' values inside the node circles and the 'variable names' Gayle uses to explain the search process. Heck, I was confused myself. But, start by ignoring the letter values inside the node circles, those are there just to represent data. When Gayle says "I'm going to call this node 's' and this other node 't', she is not talking about the data that you can see inside those circles, she is more likely talking about the variable names that she is going to use to carry out the search process. The 's' node will be the source node, or the node you are using as your starting point. The node 't' will be your target node, the node you are looking for. Watch the video again and you will see how she draws 's' and an arrow, then draws 't' and an arrow. Those are the nodes she is referring to when she says 's' or 't'.
Thanks dude
Why would that be confusing? Shouldn't it be pretty obvious, or do you think she should have used numbers as the vertex data instead of letters?
it is confusing because she uses chars for both the data values and the variable names.
stfu simp
Or use 's' for start and 'g' for goal... Pick your poison!
Notice that the space complexity required for the recursive implementation of DFS is O(h) where h is the maximum depth of the graph. This is because of the space needed to store the recursive calls.
DFS can also be implemented iteratively following the same idea as BFS but using a stack instead of a queue. This implementation uses O(v) extra memory where v is the number of vertices in the graph.
Both implementations have the same memory complexity. Stack implementation uses heap memory (dynamic) while recursion uses stack memory.
The iterative is also simpler and easier to understand, at least to me.
Issues with this:
- This implementation will work for graphs whose nodes are all connected to one another (e.g. every node has a path to every other node whether you have to go down the tree/graph or back up it and then perhaps down again). This will *not* work for _disconnected_ graphs with nodes that are disconnected to one another. Example: 1->2->3->4->5, 6->7->8 (no connection between 1 through 5 and 6 through 8)
- Breath First Search was not explained for more than one iteration down the tree. You should really explain using at least two, typically three iterations so people can understand the process of the loop and the decision-making of the loop (e.g. how do we know when to add nodes to the queue, helps explain what happens if there's duplicates).
Something that could have been explained better is the LinkedList nextToVisist procedure. That LinkedList is a queue. So the first time we add the original node, the queue is size 1, inside the while, we remove the first element and obtained at the same time, the queue is size 0. When we add the children, then the queue size grows again and the while can keep looping. THE KEY IS: Understand the LinkedList as a supermarket. The first elements, add more elements, then those child elements are checked first because the elements that each of those adds, are added to the last position to the queue. Lets the first node has 2 children. The first node is checked, then add 2 children, child A and child B. The first child is checked, B, and that child adds C, D, E, but only after the second children. So the third iteration the queue looks like this [C, D, E]. And that is why is breadth-first because the queue makes the children get ordered in the back of the line. So every ancestor is checked first.
For those who wonder why there isn't a nextToVisit.remove() in hasPathBFS(....), thats because you have to use a Queue. She mentioned it at 3:27
So it should be like:
private boolean hasPathBFS(Node source, Node destination) {
...
Queue nextToVisit = new LinkedList();
while(!nextToVisit.isEmpty()) {
Node node = nextToVisit.remove();
....
}
Very good overview ... but when you get to the code you rush through important detail that leave me a little in the dark.
Very intuitive if you actually knew how to code lol
In the BFS section, there might be as many as O(n^2) nodes in the nextToVisit. For example consider a complete graph.
Boop boop boop boop
There were five boops.
that is accurate bro
LOL
hahahha
I had a genetics professor who always used 'boops' in her explanations as well, good times
An optimization for the BFS is to put:
if(visited.contains(child.id)) continue;
inside the for loop so it won't add unnecessary items to the queue.
I am not sure this is correct. Removing that check from where it is, triggers unnecessary looping. The idea is to skip unnecessary iterations altogether.
@@hfontanez98 exactly the opposite. Unnecessary looping happens if the visited.contains it's where it is now. Because you add nodes to the queue that were already visited.
So ... You never show the code for the "getNode" method. It's folded up and we can't see it ...
Missing method:
private Node getNode(int id){ return nodeLookup.get(id); }
When you hear break-fast search instead of breadth-first search you know you should go take a nap
or go eat
really underrated
Made me laugh at the middle of a dark night 😂
Everyone here comlaining about the data and letters for each node blah blah, well I just want to thank you ! I am new at programming and have a project to do for college using graphs, this helped me a lot! Thanks!!
Missing a method:
public void addNode(int id) {
nodeLookup.put(id, new Node(id));
}
I think this would be the addEdge method that has been collapsed. It's not enough to add the node to nodeLookup, you also need to set it as the adjacent node of whatever node you want to link it to, hence addEdge having the parameters of source and destination.
0:57 "Hey ass" ...
I literally got terror flashbacks of my life
It's amazing how elegantly sophisticated you made such an easy concept.
ruclips.net/video/bIA8HEEUxZI/видео.html
True
@@yashashwisen that was a good video
Are you looking for a rendez-vous ?
@@yashashwisen good video actually
It is really confusing to use letters as node values and then also use letters as node variables ! At the beginning I was like what we are taking about : S node is actually G node .. what?? I just stopped watching it.
I total agree with you on the S node which was actually g node and how confused i was.
Is Gayle really helping or tormenting us at this point I gotta ask myself
It feels like everybody in the comments thinks they are smarter than her. A messup happens, so what. If you dont count the start, the video teached me the basics and thats why I watched this
As the video goes further I get more confused.
First the variable name with mismatching values inside where variable name is the one being referred to without prior knowledge on what she is referring.
Once the coding started she started jumping all over the place as if it's the weekend and she has to catch the bus.
It would also be nice if we get a copy of the code since getNode was not shown which will allow us to study how the code works ourselves.
Video could be somewhat confusing at first. Specifically the ambiguity of node 's' vs. node 'S'.
It's completely clear after a couple of seconds of thought, though still annoying.
There is already a node 'S', which is different the node 's' that the narrator talks about. Wasn't sure which 's' she meant after statements as seen below:
At 1:07 the narrator says, "Hmm...I'm not sure let me go ask [S's children]". Then immediately after that t is displayed pointing to H, a child of 'S'.
This implementation has a flaw. If you create a graph with, for example, four nodes labeled 1, 2, 3, and 4 and you pass something like graph.hasPathXXX(20, 44) will return true instead of false because the getNode methods can return null both, which will pass the source == destination test. To avoid this, you have to add a case that checks for null and returns false if either the source node or the destination node is null.
I tried this implementation at home and was able to confirm it by running a simple test like the one I included above.
Thank you so much. The way you explain is so simple and easy to understand.
In DFT,
We can't say if visited has source node then path doesn't exist.
Instead we should modify the algorithm as :
Algorithm hasPathDFS(source , target, visited) {
if(source == target ) {
return true;
}
visited.add(source);
for(Node child : sources.adjecent) {
if(!visited.contains(child)) {
if( hasPathDFS(child , target, visited) ) {
return true;
}
}
}
return false;
}
Explanation and examples are really good. Thanks for this video.
yes. i do not understand why we need 'if visited.contains(source.id) then return false'.
The line "if(visited.contains(source.id) return false" is important. It simply means if visited contains the source.id, then there is a cycle and no need to start checking from that source again and again.
Missing method:
private Node getNode(int id){ return nodeLookup.get(id); }
thanks
what is nodeLookup??
@@AlancRodriguez I think nodeLoopup is the hashmap for all the nodes in the graph in Key(id)-Value(Node) format.
This was fantastic! I'm so grateful this is on RUclips
I just love Gayle! The best explanation ever. See also her book!
It's nice to see that terminology like "boo-boo-boo-boo-boop" has survived the test of time. No shade, I think I've used it in my career at some point.
Well I’m surely going to save this implementation for last to memorize from scratch. Already got Linked Lists, Doubly Linked Lists, Stacks, and Queues down. Currently on trees but Graphs just seem a doozy 😢
I found this BFS code not very efficient. You could've moved the "if (visited.contains(node.id))" condition (without continue statement) in the "for each child" loop. That is, enqueue the child node only if it has not been visited. In this case, we can also ensure the dequeued nodes will always be unvisited (no need to check for continue). The current implementation will redundantly enqueue many visited child nodes, especially in an undirected graph!
for(Node child : node.adjacent) {
if (!visited.contains(child.id)) {
visited.add(child.id);
nextToVisit.add(child);
}
}
Thanks a lot for your code! But, one thing that I wanted to ask just in case: you don't need the visited.add(node.id) right before the for loop in this corrected code as it's already within the for loop (but now adding child.id to visited) right?
I think its relative tradeoff depending upon the connectedness of the graph. In your solution your calling contains across ALL children, including nodes that could have 8000 leaf nodes that will never be revisited. Also, if the node in question is found early, you've still called contains on lots of child nodes that have never been walked yet.
@@KhanSlayer ok but even then the code in the video could lead to an infinite loop. If node is in visited yiy should NOT be adding it to "next to visit".
@@youngcitybandit valid point
Instead of adding values in hashset we should add the entire node so that we may not stuck in uniqueness property in graph!! This will solve problem when the graph contains same value but the nodes are different and also their neighbors are different
Yep, i noticed that too.
For anyone still watching this, if you want to run it make a main method and then call the class and set up your Hash Map
In your main method:
Graph (Whatever name) = new Graph;
System.out.println((Whatever name).hasPathDFS(1, 5));
It'll turn true or false depending on how your hash table is set up
I liked the explanations of DFS and DFS algorithms. Did not like that the entire code was not covered or made available. The description seems to be for a bidirectional graph. If there is a path form G -> H then there should be one form H -> G. The implementation of the addEdge() does not allow for it. When I did my implementation I used letters instead of numbers. Found it easier to follow.
What's in her private Node getNode(int id) body and what is it returning?
Can you please provide this complete programme?
Would be nice to see this also return the distance between the nodes. I implemented this by queuing this information together with the node being queued, but I wonder if that's the best way to do it or if there is a more elegant way.
Great explanation madam..respect you.What is the best programming language to learn data structures and algorithms as a beginner??..please answer me madam..
a. thank you for the video.
b. i think there is an issue with the BFS function.
The entire condition - if (visited.contains(node.if)) - seems meaningless.
because no action is taken - whether the condition is met or not.
When explaining DFS/BFS, why don't you use the existing graph nodes instead of arbitrary nodes, thereby causing unnecessary confusion in the process?
Just because it's Gayle McDowell she isn't not getting slammed for this explanation
I think it was confusing because the voice over is little ahead so when she says "I'm gonna call it 's' " - it doesn't appear making us look at the node with value 'S'
If it is an undirected graph, I think the addEdge method should be :
public void addEdge(int source, int destination) {
Node s = getNode(source);
Node d = getNode(destination);
s.adjacent.add(d);
d.adjacent.add(s);
}
I see, so if it's directed then we can have it as.
public void addEdge(int source, int destination) {
Node s = getNode(source);
Node d = getNode(destination);
s.adjacent.add(d);
}
Not sure of this though but that is what I think
For DFS, I think there should be a null check since it is possible that there are no children to a node - i.e. the leaf node.
Would it be possible show an example being ran? For those of us watching this video to learn, I am unsure of how to run your program.
damn i finally understand after watching for the 5th time
For BFS, why use a linked list when you can just use a queue?
LinkedList is a Queue in java
Queue adjacent = new LinkedList();
I am unable to visualize the graph data structure with this implementation. In the implementation, each node has a linked list of adjacent nodes. That just makes the data structure a very long linked list right? I am unable to correlate this with the graph shown at 2:11. 's' has 2 children - 'a' and 'b'. In this case, what will be the 'adjacent' linked list of 's'?
She also explains it towards the end of the video with an example so that helps
I don't understand why line 33 (in DFS) has 'return false' ... I understand that if the node has been visited previously from the same node, then there is a loop. So a loop exists in the graph... How does that imply that there is no path to the destination (it could be in another path of the graph?) Thanks
EDIT - I just saw the comment below by swapnil gaikwad . He thinks this part of the algorithm is wrong!
I was thinking this is just a sanity check for disconnected graphs? where the destination is not connected, but even then I feel like this condition is unnecessary.
I wish she would actually show how to actually instantiate this algorithm. Like, HOW do I create the tree and then HOW to do I actually call the search methods?
What are the complexities of both DFS and BFS in terms of O() and Omega() ?
Run this in .75 speed for better understanding!!
Sorry, it might be my own problem but I am struggling to understand your explaination about the s to t to a b c thing. I feel quite confusing about the figure youre pointing at.
We can actually take all four of her DFS/BFS methods and condense them into a single method as follows (isBFS = true for a BFS, and isBFS = false for a DFS):
public boolean hasPath(int source, int destination, boolean isBFS) {
LinkedList nextToVisit = new LinkedList();
HashSet visited = new HashSet();
nextToVisit.add(getNode(source));
while (!nextToVisit.isEmpty()) {
Node node = isBFS == true? nextToVisit.remove() : nextToVisit.removeLast();
if (node == getNode(destination)) return true;
visited.add(node.id);
for (Node child : node.adjacent){
if (!visited.contains(child.id))
nextToVisit.add(child);
}
}
return false;
}
Node node = nextToVisit.remove()
the above method is wrong as remove() method returns a boolean value.
Node node = nextToVisit.removeFirst() will work and returns next node to visit.
I believe she used the remove() method that returns the removed element and not the boolean.
She could define her own methods.
Honestly for the first 2 minutes, I was so confused I had to come to the comment. Now I see she just spelled the word GRAPH DFS BFS as the nodes. I thought those were the values. It would be better to point that out next time. But Great Explanation!!!
Great video! Filling the need for a Khan-academy channel for CS topics. More please!
Amazing explanations. Long live HackerRank
Thanks for the video. Just one question tho. Why is that there's no value in the Node class? I mean there's id and which other nodes are connected to it, but there's no value? Why?
There seems to be a bug in your BFS code. once you find that a nide has already been visited why are you continuing and then adding that same mode back to the que? It should be a if conditoons checking that the node id is "not visited" and then continue and add the node id to the visted que
visited Set should Set I think. Otherwise, we assume all nodes have unique ids
Is there an efficient way to compute the level of connectivity of a graph? That is the number of vertices (or edges) that must be deleted to disconnect the graph. Or it is this NP hard?
1:39 When she said "boop boop boop boop boop", that really hit me
Can someone please explain to me why in the DFS, we return false as soon as we found the node was already visited. While in BFS we continue when we found the node was visited? 🤔
If it was visited, then its children had inserted in nextToVisit.
Yes this tutorial is advanced and so detailed, but it is so helpful. thank you so much.
Is the order in graph near the end correct or am I missing something? 5 and 7 are calendar before 6 and 8 but there's no other path connecting them to S
The content of the getNode method was not explained
good tutorial I did something similar and just used a vector node pointers...this looks like c++?
Also a paired vector is good for holding a node and it edge values
Is there a tutorial for searches when node edges have values to find the path with the lowest cost?
A graph data structure can be represented by using a Map as well
Awesome and very simple explanation! Enthralled . Superb mam. You are so Good . !
Hi everyone, i am learning algorithms. I looked through lots of syllabus and found them interesting, but i dont know what resource to learn them from. Theres a whole list of algorithms and clever tricks i would like to learn, sorting, search, dp, recursion, etc. Please, if you have a good resource to learn these from, they would be very helpful!
in the addEdge function, should we also not do something like d.adjascent(s);
I think so, my test(1,4) fault at 1-2, 1-3, 3-2, 3-4 configuration.
It depends if you want your graph to be a digraph or not :).
To understand a coding topic, I used to check your videos first, it leaves me bit confused, I check other videos, and things become clear then..
You have some good videos but not the coding ones, I think you may work harder to simplify things, you may try to explain the code while linking it with the algorithm.
Thanks for your efforts anyways.
This video really helps! Anyone knows where the source code of this tutorial is?
How do you find the cost of a path?
Hi, what microphone do you use in the beggining? It sounds very clear ! Thanks :-)
if visited.contains (node.id) check should be at start of loop in BFS I believe
That's a great explanation!!
One question though,
In BFS implementation I haven't seen the use of visited HashSet. shouldn't we check if a node already exists in the set before adding it into the queue?
What was the point of that continue if statement for bfs??? Also wouldnt you NOT want to add the node to "visited" if its already inside visited???
Continue skips to the while loop again. If you have already visited this node there is no need to add their child again.
@@MrJeffFeng oh woops completely forgot. Thanks
Hey Gayle , very nice explanation !!! do you have graph traversal videos in C also ? If yes , can you please provide links.
loved the video but i wish you could have attached the source code in the description...
I did not see that she used nodeLookup (the hashMap at the beginning). :(
A well explained video on this topic. Thank you.
Hello ma'am, I am new to programming. According to my understanding Node class should not be static. Because we need to create multiple nodes, which means we need many instances of the same class. Please correct me if I am wrong. Thank you
Akshay Chandrachood Static classes are not like static variables. You can create many instances of them. In Java, you can create static NESTED classes for encapsulation. I’m For example, the Graph class can access the Node classes private variables and methods because it is nested. However, functionally, the Node class isn’t different from any other class. In fact, I don’t know why people use static classes at all haha
Thanks for the clarification.
@@jessicahuang5507 in C++, you cannot instantiate a static class. I think this is the origin of the confusion.
I read the comments before watching the video, and now i really don't know what to do! Is it really helpful or confusing?
After 3 minutes watching: Hill man.. I'm gonna quite!
Great video! Helped me a lot implementing DFS and BFS!
She didn't use visited HashMap for the depth first search - how would this ever terminate?
Why the Node class has a private constructor? (line 7)
Ok I see, "if the member or constructor is declared private, then access is permitted if and only if it occurs within the body of the top level class (§7.6) that encloses the declaration of the member or constructor"
Why would you do this(inside hasBFS method):
if (visited.contains(firstNode.id)){
continue;
}
if you are adding node.id to visited list anyway?
also we can check the condition below first thing in the method so if it is equal we dont have to go through any extra operation
if(source == destination){
return true;
}
Or better just put it inside the for loop so it won't add items that we've already check to the queue
I didn't quite understand the implementation; Can we use LinkedList inbuilt? what does this mean ? what is adjacent? what is HashSet, what is it doing? what does "for (Node Child : node.adjacent) ? so many questions... Help will be appreciated :)
Why would you use letters all over the place for nodes? 😓 More confusing than it needs to be
I love your videos and recently bought your book. Do you have samples of all of the data structures in javascript? That would be a fantastic resource to supplement your material--especially for noobs like me! Thank you.
What ‘s the name of the compiler your using ?
That’s my morning routine. Breakfast search.
where from did you get s and t and a, stay consistent with your graph labels
I think 's', 't', 'a' are the alias of the node. "graph labels" inside of the circle are the node values, could be anything, integers, strings,etc. In this case it just happened to be letters. for example, from node s to node t could mean from New York to Vancouver.
It's funny to see book "КАРЬЕРА ПРОГРАММИСТА" on the table)) It could be translated as "Programmer Career". What it is the first and second one?
Psyduck uses Graphs with characters for both name and values
Enemy Pokemon is confused
She is talking about Node "s" and Node "t" not the english character of node data field.
HashSet x = HashMap? so you didn't even mind to run the algo? nice!
Do anyone know what's the benefit of using a LinkedList for storing the adjacent children of the Node class. Why not use a std::vector for this?
We ask question "Hey S, do you have path to node T?" but there is no node T. But later she points S to G and T to H.... can somebody please explain me this part.
Ignore the letters inside the node circles, those are there just to represent data. When she says "I'm going to call this node 's' and this other node 't', she is not talking about the data that you can see inside those circles, she is more likely talking about the variable name that she is going to use to carry out the search process. The 's' node will be the source node, or the node you are using as your starting point. The node 't' will be your target node, the node you are looking for. Watch the video again and you will see how she draws 's' and an arrow, then draws 't' and an arrow. Those are the nodes she is referring to when she says 's' or 't'.