Algorithms: Graph Search, DFS and BFS

[martincopes]

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.

[tourniquet]

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

[YogeshPersonalChannel]

It's amazing how elegantly sophisticated you made such an easy concept.

[Arunnn]

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).

[chrizonline]

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<Node> nextToVisit = new LinkedList<>();
while(!nextToVisit.isEmpty()) {
Node node = nextToVisit.remove();
....
}

[beedavis]

Very good overview ... but when you get to the code you rush through important detail that leave me a little in the dark.

[brianotte]

This was fantastic! I'm so grateful this is on YouTube

[beedavis]

So ... You never show the code for the "getNode" method. It's folded up and we can't see it ...

[pavelerokhin]

I just love Gayle! The best explanation ever. See also her book!

[garciamilord]

What's in her private Node getNode(int id) body and what is it returning?

[ScottMeesey]

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.

[flueepwrien]

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

[mdazam]

Amazing explanations. Long live HackerRank

[OzoneGamerStation]

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 😢

[swapnilgaikwad]

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.

[tejaspatel]

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

[kylep]

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.

[drormik]

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.

[ihora]

The content of the getNode method was not explained

[RyanLeiTaiwan]

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!