How to Find Path in Graphs using Depth First Search | Graphs in Data Structures
Vložit
- čas přidán 8. 08. 2020
- Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we discuss the question where we are required to check if a graph has a path from the source vertex to the destination vertex or not. We discuss the constructor of a graph using an Edge class and how a graph is present in memory.
We solve this question using recursion - Faith and Expectation ,a similar technique which was used while solving the flood fill question in recursion. To watch the solution for Flood Fill, click here: • Flood Fill - Solution ...
For a better experience and more exercises, VISIT: www.pepcoding.com/resources/o...
#pepcoding #graphs #datastructures
Have a look at our result: www.pepcoding.com/placements
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
One of the best explanations of DFS. I am glad you take time to dry run with diagrams as it helps understand at deeper level. Some coding related CZcamsrs have more views/subscribers but they do not explain half as good as this instructor. Amazing in depth analysis!
Glad you enjoyed it!
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
I guess Pepcoding is one of the most underrated channels. Sumeet Sir provides such premium content for free. He should get more views. I have taken DSA courses from other big platforms but their quality and quantity isn't even close to this. Thank You, sir.
Glad to know that you liked the content and thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
I have never had a good grasp of ds algo, but with your videos sir it has been the biggest and only help. SIr please never stop making videos.
Sir, you know what is the best thing about pepcoding and you? You guys give significant amount of time to things until we understand the concept clearly,you already know that where we are going to have doubt and you put emphasis on that part and it become crystal clear then whereas in other channel they explain whole thing in just 10 min, that's why pepcoding is best
I am now able to solve the graph questions by myself(for the first time). All credit goes to you, Sir. Best tutorial for graph on the web.
Thank you so much, Sir
Great Explanation!!, the thing I was known about visited was never to visit that vertex, but when I saw Sir's explanation, now I actually/practically got to know with dry run, how that absence of visited array impacted the flow, no one explains this,
Thanks a lot for such great explanation, even dry run became more strong after watching this video...
Yeh banda samjhaye aur dimag mein naa utre aisa ho hi nai sakta.....thanks for such a vivid explanation guruji.
This is pure Gold sir, you simply rock Sumeet sir..Thank you so much for such wonderful content ❤ Specially, the dry run part.
There is no words to appreciate the effort you are giving to enlighten us every moment
This is a pure diamond! Thanks a lot sirr
Great Explaination!
Awesome explanation..❤️
ohh... My god such a great explanation........Loved it😍😍😍😍
The beauty of this course is you know how things are working
Amazing analysis Sir. The drawings are really helpful. Keep up the great work.
Thanks, will do!
Thank You so much sir for this amazing video. Even though I am from CPP background I get all the points U told 💯
Your lectures have always been my goto place for revision... very intuitive explanation, sir...
Glad you liked it !! Share among your peers
Worth watching it.
sir great explanation will finish the whole playlist!These videos have really improved my thinking capability.
Thankyou beta!!We r glad my beta😊
thanks sir for such a informative lecture :)
one of my favorite channel thanks for providing such content sir...
Keep learning.
And for better experience and well curated content explore nados.pepcoding.com
He is first teacher who replies to all student !!
Great explaination !!
Thank you for the kind words.
aisa dry run koi nahi karta...thanks Sumit bhaiya
loved it
Good explanation
This is how I reached to this video....
Started watching number of island problem,
then there was a reference to connected graph
then came to connected graph
then there was a reference to graph traversal
so came here
now here flood fill reference is there and I am going to watch that first :)
Main Point: I am loving your explanation and not able to leave your video
This is first time I got courage to even learn about Graphs because of the simple explanation :)
Thanks :)
Keep up the good work please.... :)
Glad you love our explanation .
For better experience sign up on nados.io
And don't forget to follow us on Instagram instagram.com/pepcoding/
in case Vertices 0-7 ke range me na hokar ke kuch bhi kuch aur nums hite like 10, 43, 78879, etc any numbers then is case me Map me in verices ki value as key and ArrayList as Value of map ke taur pe used kia jaa sakta hai kya??? please ans .
What is the solution of "Cant create generic array of arraylist" ??
you cant create array of generic classes ,it will give compile time error
Demo.java:20: error: generic array creation
do arraylist of arraylist instead
Excellent explanation.
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review - g.page/Pepcoding/review?rc
Gr8 explanation sir.
Thankyou beta!
Will you like to write a few words about us here (www.quora.com/Which-is-the-best-institute-for-coding-in-Delhi)
😍😍😍nice explanation sir!!
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Super explanation!
Glad it was helpful!
Keep learning.
And for better experience and well organised content visit nados.pepcoding.com
Excellent sirji 👍👍
Thankyou beta!
Keep learning and keep loving Pepcoding😊
Thank you sir 💓
Most welcome. Please share and subscribe
After the the explanation of this question i am the Jabra fan of sumeet sir
This guy is a genius when it comes to explaining complex topics. I am feeling better now.
Good bless you Sumeet Sir.
Sir wese abb Level up ke question nahi aayenge kya? I mean 10-15 dino se nahi aa rahe hai questions.
It's a request ki aap please usse pura krr do atleast Dp and Graph of level up.
Baaki sab badiya hai sir
Thankyou beta,
I am glad you liked it. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
Aayege beta, jaldi he. Till then, stay tuned.
great explaination sir
Glad you liked it!
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities.
why backtracking step is not there in this?
Graph ki playlist porri nahi hai na?? pepcoding.
sir, the Dark Mode on website looks pretty awesome :)
Thankyou😊
Nicely explained
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Sir recursion ke bad ye sab mst lagta hai
Yahi to chaie
Why are Graph questions not available in java foundation series on the pepcoding website??
We will make them available today
@@Pepcoding Ok sir thank you very much 😄
sir agar ye visited[src]= true for loop ke bad krte toh koi error aati kya?
han beta, stack overflow ho jata.
sir, i am from PIET college haryana... do you know about our college... how are the placements here?
beta PIET to nahi suna.
Flood fill me visited ko false bhi karte hai hum, yaha kyu nahi kiya?
for loop samj nhi aya
can some one explain me>
for(ArrayList edge : graph[src]){ // array ka andar list hai, list liye q nhi loop nhi lagaya and how edge.nbr is valid ?
}
for(Edge edge : graph[src] )
This is the right syntax.
We are taking a object / variable 'edge' of class Edge type to access the array list of edges.
extremely well explained and i wonder how this channel has just 103k subscriber please people share this as much you i am also sharing, help your friends and this channel grow
These words really mean a lot, for better experience and well organised content sign up on nados.io and start learning.
Please try to write code in c++ also
sir do you have explanation in c++ also if yes please provide link
Yes, please check c++ video of this same content on nados.pepcoding.com
ArrayList[] graph=new ArrayList[vtces];
ye line pr "cannot create generic array of arraylist" error aa raha hai
ArrayList graph = new ArrayList();
for(int i=0;i
ArrayList[] graph=new ArrayList[vtces];
Sir please thoda sa ye explain kar dijiye thoda mushkil hora h graphs abhi
arey graph wali first video pehle dekhie na
yahan se kijie
www.pepcoding.com/resources/online-java-foundation/graphs
Nice
Very nice
Mohit Tyagi of Computer Science .
ArrayList edge:graph [src]
how this line produces neighbours
for(Edge edge : graph[src] )
This is the right syntax.
We are taking a object / variable 'edge' of class Edge type to access the array list of edges.
Flood fill m aesa btaye the
Have you not used stack anywhere
Last question
Guru ji aap pahle ku ni mile :)
Some hardest problems please
Levelup ki backtracking aane ko hai. Ekdum sahi lagegi
@@Pepcoding parallely ek ek que doosre topics ka v daal do :), jo khi usually covered na ho .Thanks a lot
isVisited[src]= false kyon nahi kiya?? flood fill mein to kiya tha
Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.
@Sharath Kumar did you get answer for why visited[src] = false is not done ? I have the same query....Can anybody else help us here ?
@@subbucs5674 sorry I don't remember it now Did it a month ago right
@sharath.kumar
In flood fill, we traverse each cell multiple time, hence we need to set visited[I] = false.
But, To traverse graph - we need to traverse each node only hence we do not need to set visted[I] = false.
@Sahil Raj are you trying to say - by not writing visited[I] = false, we are doing some optimization?
I don't think "not writing visited[i] = false" is an optimization technique... Instead, it is a mandatory code statement to make sure that each node is visited only once in SINGLE traversal - if want to multiple traversal then we need to write visited = false.
Sir path print krna chaiye n
Wo question bhi hai
@@Pepcoding all paths?
Aap neighbour ke pichhe neighbour aapke pichhe too much fun
🤣🤣🤣🤣🤣
Or ye mai 10:58 pe ja rha hu flood fill dekhne😑😂
Generic array creation error🤕
Has anyone attempted this Q in c++?
no
Typo in name
Thanks for reporting.
Peepcoding doesn't have - ve comment.
5 🌟
keep motivating, keep learning and keep loving Pepcoding😊
neighbor badmas h sir, sath me le k nahi ja rha!
sir please make one is cpp also
beta ye to next year karunga
Saare not 1
All good, but is it english? I can not understand, sorry
its in Hindi.
recursive solution without using visited space
import java.io.*;
import java.util.*;
public class Main {
static class Edge {
int src;
int nbr;
int wt;
Edge(int src, int nbr, int wt){
this.src = src;
this.nbr = nbr;
this.wt = wt;
}
}
public static boolean has_path(ArrayList[] graph,int sr,int de,int l){
if(l==graph.length){
return false;
}
if(sr==de){
return true;
}
boolean a=false;
for(int i=0;i