Dark

Algorithms: Graph Search, DFS and BFS

HackerRank
Subscribe
Views 560 053
84% 3 432 607

Learn the basics of graph search and common operations; Depth First Search (DFS) and Breadth First Search (BFS). This video is a part of HackerRank's Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell. www.hackerrank.com/domains/tutorials/cracking-the-coding-interview?

Science & Technology

Published on

 

Sep 27, 2016

Share:

Link:

Download:

Loading link...

Add to:

My playlist
Watch later
Comments 190
Bhavani Shankar
Bhavani Shankar Month ago
good
Harry Potter
Harry Potter Month ago
She sounds like Jimmy Fallon's "EH" show 😄
Misha Lubich
Misha Lubich Month ago
A well explained video on this topic. Thank you.
David Sun
David Sun Month ago
This video really helps! Anyone knows where the source code of this tutorial is?
Blue Print
Blue Print Month ago
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
Shafiqe Akhtar
Shafiqe Akhtar 2 months ago
Wow u beautiful girl...
Yousef Ahmad
Yousef Ahmad 2 months ago
You draw instead of use quality computer generated animations, and that will be your downfall.
chronocide
chronocide 2 months ago
She didn't use visited HashMap for the depth first search - how would this ever terminate?
Agnes Akne
Agnes Akne 2 months ago
this computer science woman is not ugly
John Canessa
John Canessa 3 months ago
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.
Quobby Dave
Quobby Dave 4 months ago
am fresh peogramming student and can I have the link to your source code
Limitless 1
Limitless 1 4 months ago
You guys are experts at making things more confusing than they already are..
Ricardo Plascencia Silva
Missing method: private Node getNode(int id){ return nodeLookup.get(id); }
Antreas Tzionis
Antreas Tzionis 4 months ago
Why are adjacent nodes a LinkedList rather than an array?
Vaibhav Sharma
Vaibhav Sharma 4 months ago
The sound is Terrble!
CrzyAsianGuy
CrzyAsianGuy 4 months ago
You aren't good a teaching. How do I block this channel?
NimeniTv
NimeniTv 5 months ago
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.
Mehrdad Karami
Mehrdad Karami 5 months ago
Should update visited to true in DFS
Daniel Cojocaru
Daniel Cojocaru 5 months ago
"And first S goes to node A". And you point to node H. What the????????? Put some heart into it.
Brian Otte
Brian Otte 5 months ago
This was fantastic! I'm so grateful this is on RUvid
6 months ago
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'
Isselmou Sneiguel
Isselmou Sneiguel 6 months ago
Do it slowly please. take your time and explain it line by line. You are using many hashSets why ? It's very confusing!! Thank you for the effort anyway
Ashwini Iyer
Ashwini Iyer 6 months ago
Where do I add adjacent nodes to source node to build graph can you please post that code
TheresaShen3397
TheresaShen3397 6 months ago
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? 🤔
Makii Chii
Makii Chii 7 months ago
When you hear break-fast search instead of breadth-first search you know you should go take a nap
Oscar
Oscar Month ago
or go eat
cutiko
cutiko 9 months ago
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.
Tony Fadin
Tony Fadin 9 months ago
All who got confused did not pass the interview.
membu chibuzormembu
membu chibuzormembu 9 months ago
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!!!
Eric Cannon
Eric Cannon 9 months ago
@5:32 in the hasPathDfs function, it takes two parameters and you try to recursively call it with 3 parameters?
Lingobol :)
Lingobol :) 9 months ago
She's calling the private method which has 3 parameters.
Hasnaa Ibraheem
Hasnaa Ibraheem 10 months ago
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.
Muhammad Mohib Khan
Muhammad Mohib Khan 10 months ago
if visited.contains (node.id) check should be at start of loop in BFS I believe
Pravin Patel
Pravin Patel 11 months ago
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?
Young City Bandit
Young City Bandit 11 months ago
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???
Young City Bandit
Young City Bandit 11 months ago
@Jeff Feng oh woops completely forgot. Thanks
Jeff Feng
Jeff Feng 11 months ago
Continue skips to the while loop again. If you have already visited this node there is no need to add their child again.
OzoneGamerStation
OzoneGamerStation 11 months ago
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 😢
AGT0M
AGT0M 11 months ago
HackerRank, thanks for trying...
blackstreet23
blackstreet23 11 months ago
The way you explain it is horrible ...
CrzyAsianGuy
CrzyAsianGuy 11 months ago
Horrible explianation
Shelby Faaron
Shelby Faaron Year ago
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!!
yymin-ouch san
notice that she's not going too deep into the concepts and making it easier for us, but she's impressing us just enough to get us interested in her book. after all every video starts with her introduction then her book! or I'm just overthinking
Ihor Mochurad
Ihor Mochurad Year ago
Missing a method: public void addNode(int id) { nodeLookup.put(id, new Node(id)); }
Elias Alabssie
terrible explanation
Flip Boy
Flip Boy Year ago
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
Clay Morrison
Clay Morrison Year ago
Thanks for this, it saved me!
Sw4gBeard
Sw4gBeard Year ago
Breast First Search Oh Yeah!
Seshamany Vigneshan
loved the video but i wish you could have attached the source code in the description...
Dibbendu Koley
Boop boop boop boop boop
Rishabh Rahul
Rishabh Rahul Year ago
boop boop booop boop ... so cute
Daksh Agrawal
Daksh Agrawal Year ago
Is there is a lag in the explanation at 1:13. I feel something going weird.
نورس 'ۦ،
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!
Brandon Salazar
Y’all... Nodes = uppercase Pointers to them = lowercase
Christine Hill
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?
Batyr Atamamedov
It's so confusing! Why are you renaming nodes when they already have letters on it? Instead of 'G' node you write 'S', instead of 'R' you're writing 'a'??? Why on earth you have to do this? Just keep it simple, from G to R, from R to A and so on and so forth. No need for extra letters...
Thanh Truong
Thanh Truong Year ago
this video explanation is so dumb, lady/producers you need to stop this stupidity
K Badsha
K Badsha Year ago
When did she actually use a queue?
Alexander Myronov
Anyone knows what software/hardware is being used to write and present this? Tnx
Aniket Bhoite
Aniket Bhoite 2 months ago
Hackerrank website's own code editor
Akshay Chandrachood
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
Thanks for the clarification.
Jessica Huang
Jessica Huang Year ago
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
Bboy Network
Bboy Network Year ago
Psyduck uses Graphs with characters for both name and values Enemy Pokemon is confused
ttma1046
ttma1046 Year ago
She is talking about Node "s" and Node "t" not the english character of node data field.
Jason Bassos
Jason Bassos Year ago
node.equals(dest) not node == dest
Next videos