I was 5.27 minutes into the video and i initially thought that dfs would use recursion when you started explaining about going back and front. The moment you told recursion i stopped the video and started to code my own recursion algorithm. And i figured it out and got output. Im complete honest here . I myself came up with my algorithm and it worked in first attemt itself. All thanks to strivers recursion playlist. my code public static void depthsearch(ArrayListal,int[] vis,Queue qu,int node) { for(int a:al.get(node)) { if(vis[a]==1)continue; vis[a]=1; qu.add(a); depthsearch(al,vis,qu,a); } return; }
00:04 Learn about depth-first search (DFS) in graphs. 02:23 Depth-First Search (DFS) is about traversing in depth 04:26 DFS explores in depth, uses recursion. 06:47 Explanation of Depth-First Search (DFS) 09:04 DFS traversal explores graph depth-wise and avoids revisiting visited nodes. 11:18 Depth-First Search (DFS) traversal technique in graphs. 13:25 DFS technique explained using adjacency list in graphs 15:35 Depth-First Search (DFS) traversal technique in graphs. 17:44 DFS traversal iterates on node neighbors and calls function once per node. 19:36 The time and space complexity depend on the number of edges. Crafted by Merlin AI.
@@kavyabanka4482 We are just visiting each node and adding it to an array list. And if for a particular node, there are no neighbours, then we are not calling the function again. So we just need to return the updated list back for each recursive call
Understood each and every word♥. Kudos to your hard work and dedication, you are the motivation behind a lot of people. Your hardwork inspires a lot of people to work hard. Thankyou for providing such a beautiful graph series keep posting such content ♥, we all need this.
I thought before coming to this video , you have explained topics like spanning forests and how its different from spanning tree and how peeps can relate tree-traversals with graph-traversals (relate doesn't means same !!). But you have just straight hopped on algorithms and code 🙂. Good , Carry on😀
if anyone wants an iterative approach here it is-> class Solution { public: vector dfsOfGraph(int V, vector adj[]) { stackstk; vectorvisited(V,0), dfs; stk.push(0); while(!stk.empty()) { int temp=stk.top(); stk.pop(); if(!visited[temp]) { visited[temp]=1; dfs.push_back(temp); //as the nodes in the adj list are given in order of left to right //so push right to left so that we can pop left to right, to maintain order for(int i=adj[temp].size()-1; i>=0; i--) { int t=adj[temp][i]; if(!visited[t]) stk.push(t); } } } return dfs; } };
understood almost , but why is the vis array is not accessed by & sign as we need the values of it, or are arrays refrenced directly , and for vectors we need a '&'
arrays are always passed by reference , when we pass an array as a parameter to a function , the pointer to the first element of the array is passed , so any changes in the array inside external function will reflect in the main function, or the changes made in the array remains ! but for vector we need to specifically pass by reference to avoid making a copy of it
I am bit confused, on why the time complexity if added as O(n) + O(2*E) instead it should be multiplied right ? We are calling for all the nodes once and for each each we are calling all its neighbours no of time. i.e. O(n*2*E) ~ O(nE) . Please help me understand.
For each value from 0 -> n we are not visiting 2*E nodes.....we are visiting 2*E nodes in total for all n...not for each for i in 1 to n..... that's why time complexity is O(n + 2*E)
you need to pass it by reference, as you don't wanna send a copy of the vector every time dfs is called, and rather the original vis vector needs to be manipulated, hence, you need to pass it by reference
I think for the undirected graph the time complexity should be TC-> O(N)*O(2E) i.e for each node visit you have to cheak all of its neibours so TC -> O(2*N*E)
I have an interview tomorrow for a good hefty package and I feel pretty confident . I really don't know what is going to happen tomorrow but I hope I come back with some thing good . Just putting this comment up to see if this would be a great memory or a don't know what 💕💕
@@aishuladha6911 did not go well . I was able to answer all questions almost right but not 100% right . In the end they ended up taking 2 students who I guess might were able to answer 100% right
At 2:44, we push 4 and 7 into the stack after removing 3, now 7 traverse and check for neighbor node 8, it pushes that into stack, 4 was already visited so 8 will simply get pop and will not push anything.... Corrct me if I'm wrong
I would have liked to see the code for a DFS using a stack rather than recursion. It is more intuitive. It makes DFS and BFS almost identical except that DFS uses a stack and BFS uses a queue.
I have a doubt in this code of yours what if in a graph I give you two components you can traverse with only one component but for the other one this code will fail. Now, to answer which will be the right code so in Striver bhaiya old series he explained that code which will run for every graph doesn't matter how many components you have.
I have the same doubt , if more than one disconnected components. I am running the loop for all the nodes if there are disconnected components and passing visited array as reference then it giving me an error don't know why . have you any idea why it is giving me an error while passing the reference of visited array . ???
//I think this code will work for unconnected components also void dfs(vector&visited, int node, vector&ans, vector adj[]){ visited[node]=1; ans.push_back(node); for(auto it:adj[node]){ if(visited[it]==0){ dfs(visited,it,ans,adj); } } } vector dfsOfGraph(int V, vector adj[]) { // Code here vectorans; vectorvisited(10000); for(int i=0; i
@@amansinghal4663 for this u have to go from starting node to last vertix I actually use python see the code def dfsOfGraph(self, V, adj): # code here ans=[] visited=[False]*V for i in range(V): if visited[i] is False: self.dfshelper(i,visited,adj,ans) return ans def dfshelper(self,SN,visited,adj,ans): visited[SN]=True ans.append(SN) for i in adj[SN]: if visited[i] is False: self.dfshelper(i,visited,adj,ans) #It will work
Then you will have to declare visited array of type of vector and pass it by reference to DFS func and then run a loop in your main function for non-visited nodes.
for each node we are going through their adjacent node which is degree and sum of all degree is 2E so isnt time complexity is O(2E)=O(E),am i missing something? if we have outer loop going 1 through n and in each iteration inner loop goes for 1 throguh i . so time complexity is 1 + 2 + 3 + n = O(n2) . why similar thing not happening??
A very silly question but still it keeps bugging me that why the time complexity is O(N + 2E) and not O(N*2E) as for each node we are checking all the edges . If anyone can clear my doubt it will be very helpful for me. Thanks in advance.
there is some error with dfs travel: 1256487 , you forgot to write mark 3 as visited. overall its amazing, just watching it again to revise it, sorry if was rude.
recursion uses Call Stack which is nothing but a stack provided in order to handle function callings so it is upto you that either you use your own Explicit stack or implicit stack ( i.e. Recursion or Call STack)
All the adjacent vertices will surely be visited for all nodes, but as it is an undirected graph that mean if an edge exists from 1 to 2 then that same edge will also be checked as an edge from 2 to 1 , so we are checking an edge 2 times so it adds to the time complexity.
Hello bhaiya I will be starting my college 2-3 months later since jee advanced is this month end ...... Can you make a video on what we can explore in first year of college
@@abhijeettripathi7615 are you talking about jee? I did qualify it with 98.6 percentile..rank-11876 ....maybe I will get a decent Nit with ece branch .....just wanted to learn about coding and stuff before starting college
why adj and vis are not passed by reference ? it is giving me error. we need to store there values in different function passes while recursion goes on naa
arrays are always passed by reference , when we pass an array as a parameter to a function , the pointer to the first element of the array is passed , so any changes in the array inside external function will reflect in the main function, or the changes made in the array remains !
Let's continue the habit of commenting “understood” if you got the entire video.
Do follow me on Instagram: striver_79
Understood mere bade bhaii !
what if the graph is not strongly connected?
how can the code work for connected components?
understood
Striver bhaiya 13:12 you done a mistake hear... you didn't write 3 over their....
Entire Semester you taught in these 56 videos. Kudos to your efforts...!!!!! Keep growing.
I was 5.27 minutes into the video and i initially thought that dfs would use recursion when you started explaining about going back and front. The moment you told recursion i stopped the video and started to code my own recursion algorithm. And i figured it out and got output. Im complete honest here . I myself came up with my algorithm and it worked in first attemt itself. All thanks to strivers recursion playlist.
my code
public static void depthsearch(ArrayListal,int[] vis,Queue qu,int node)
{
for(int a:al.get(node))
{
if(vis[a]==1)continue;
vis[a]=1;
qu.add(a);
depthsearch(al,vis,qu,a);
}
return;
}
Bro i have a doubt whts the use of list and why we take it vectorls?
@@SohailKhan-cx9gb vector is for c++, and list is for Java
what's your codeforces rating?
Yhi cheej me saari visited nodes hoenge@@SohailKhan-cx9gb
I did it too!! Striver's recursion playlist has indeed made me good at it!
Striver bhaiya ki jai...far far far better explaination than that of College professor ⚡🙌
no comparison with college professor
don't call him bhaiya pls🥲
Profs don't teach you for placements, keep in mind
00:04 Learn about depth-first search (DFS) in graphs.
02:23 Depth-First Search (DFS) is about traversing in depth
04:26 DFS explores in depth, uses recursion.
06:47 Explanation of Depth-First Search (DFS)
09:04 DFS traversal explores graph depth-wise and avoids revisiting visited nodes.
11:18 Depth-First Search (DFS) traversal technique in graphs.
13:25 DFS technique explained using adjacency list in graphs
15:35 Depth-First Search (DFS) traversal technique in graphs.
17:44 DFS traversal iterates on node neighbors and calls function once per node.
19:36 The time and space complexity depend on the number of edges.
Crafted by Merlin AI.
The passion with which you teach is commendable !!
Understood! Amazing explanation as always, thank you very much!!
Pointing a mistake, at 12:36 you removed 3 from the final dfs traversal list and it stays like that till the end. Which is incorrect.
I forgot to write it 😅
Thanks striver for such an amazing explanation of the recursive tree.
Can you tell me why here not mentioned base condition
@@kavyabanka4482 We are just visiting each node and adding it to an array list. And if for a particular node, there are no neighbours, then we are not calling the function again.
So we just need to return the updated list back for each recursive call
Understood each and every word♥. Kudos to your hard work and dedication, you are the motivation behind a lot of people. Your hardwork inspires a lot of people to work hard.
Thankyou for providing such a beautiful graph series keep posting such content ♥, we all need this.
Best video tuturials on the you tube absolutely!!!
Your explanation and efforts you put in every video are beyond words to express the gratitude, God bless you
the best playList on graphs i ever see..Thank you so much 😊😍
instead of "int vis[v] = {0}" we can also use "vector vis(v)" right?
You can write "vector vis(v,0)"
@@ayushsenapati8420 vector vis(v) would also work. as default values will all be 0
it's just more intuitive to use normal array
UNDERSTOOD!!!!!!!!!!!!!!!!!!!!!!!!!
I thought before coming to this video , you have explained topics like spanning forests and how its different from spanning tree and how peeps can relate tree-traversals with graph-traversals (relate doesn't means same !!). But you have just straight hopped on algorithms and code 🙂. Good , Carry on😀
Understood! Amazing explanation
Should not we have a for loop in the top if we have unconnected components?
Yes, you should. But this one was a single component graph. So not needed.
@@takeUforward Ok got it thanks. Understood.
can you give the code which will work for unconnected components also ?
Or can u just explain the logic ?
@@takeUforward Is the below code correct for unconnected components also ?
void dfs(vector&visited, int node, vector&ans, vector adj[]){
visited[node]=1;
ans.push_back(node);
for(auto it:adj[node]){
if(visited[it]==0){
dfs(visited,it,ans,adj);
}
}
}
vector dfsOfGraph(int V, vector adj[]) {
// Code here
vectorans;
vectorvisited(10000);
for(int i=0; i
if anyone wants an iterative approach here it is->
class Solution
{
public:
vector dfsOfGraph(int V, vector adj[])
{
stackstk;
vectorvisited(V,0), dfs;
stk.push(0);
while(!stk.empty())
{
int temp=stk.top();
stk.pop();
if(!visited[temp])
{
visited[temp]=1;
dfs.push_back(temp);
//as the nodes in the adj list are given in order of left to right
//so push right to left so that we can pop left to right, to maintain order
for(int i=adj[temp].size()-1; i>=0; i--)
{
int t=adj[temp][i];
if(!visited[t]) stk.push(t);
}
}
}
return dfs;
}
};
compilation error is there in ur code and it is for bfs, not dfs
It is ac on gfg and. It is indeed for dfs, notice the data structure used
i can confirm akshat's method is logical & correct
arre hello bhai
@@VEDANSHSHARMA-o6k are bhai hello
striver op...explanation op....... graph series SUperrrrrrr OP
great and amazing work! Loving it, thanks a lot❤
Please make a videos on number theory
Can a stack based solution be made for tha same DFS?
Amazing explanation as always.
In java code why have we taken the size of visited array as v+1 when graph nodes are zero indexed
lol mena 0.5 pa dekh lia puri video too funny .
nice video bro
understood almost , but why is the vis array is not accessed by & sign as we need the values of it, or are arrays refrenced directly , and for vectors we need a '&'
arrays are always passed by reference , when we pass an array as a parameter to a function , the pointer to the first element of the array is passed , so any changes in the array inside external function will reflect in the main function, or the changes made in the array remains !
but for vector we need to specifically pass by reference to avoid making a copy of it
@@sumerrawat6947 i have the same doubt about the reference . thanks to you .
@@sumerrawat6947 copy thodi banegi, reference bola haina, same memory address par hi saare changes hoge array mai
I am bit confused, on why the time complexity if added as O(n) + O(2*E) instead it should be multiplied right ? We are calling for all the nodes once and for each each we are calling all its neighbours no of time. i.e. O(n*2*E) ~ O(nE) . Please help me understand.
I too have the same doubt
@@suchetapal713 Did u understand??
The comment section in the BFS video contains a great explanation by @YeaOhYeahh. Should help.
that O(2*E) is kind of the summation over all those inner for loops , striver has explained that check out the bfs video
For each value from 0 -> n we are not visiting 2*E nodes.....we are visiting 2*E nodes in total for all n...not for each for i in 1 to n..... that's why time complexity is O(n + 2*E)
Thank you very much. Great explanation.
Completely UNDERSTOOD.
Understood Striver!! Thank you so so much for these amazing lectures :)
understood each and every bit of your explanation...
i am using vectorvis(V,0) than only three test cases are passing
you need to pass it by reference, as you don't wanna send a copy of the vector every time dfs is called, and rather the original vis vector needs to be manipulated, hence, you need to pass it by reference
Thank you "goat" for these amazing lectures
best series on Graph👍
I think for the undirected graph the time complexity should be TC-> O(N)*O(2E) i.e for each node visit you have to cheak all of its neibours so TC -> O(2*N*E)
2E is the total number of degrees, not the number of degrees of each node. So it will be O(N) + O (2E)
I have an interview tomorrow for a good hefty package and I feel pretty confident . I really don't know what is going to happen tomorrow but I hope I come back with some thing good . Just putting this comment up to see if this would be a great memory or a don't know what 💕💕
How's your interview
@@aishuladha6911 did not go well . I was able to answer all questions almost right but not 100% right . In the end they ended up taking 2 students who I guess might were able to answer 100% right
At 2:44, we push 4 and 7 into the stack after removing 3, now 7 traverse and check for neighbor node 8, it pushes that into stack, 4 was already visited so 8 will simply get pop and will not push anything.... Corrct me if I'm wrong
In the interviews, can we be sure, that we would be given adjacency lists, or we can be given adjacency matrix also?
100%
kudos!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Thank you, Striver 🙂
Can we not use stack method, if so please provide the code for it
Understood each and every word♥
Hi, the node 3 was traversed but not added to the visited array. Please correct me if I am wrong
you are right, hi missed writing it by mistake
your contribution is matchless. thank you.
14:03 You forgot to mention 3 in DFS call. It should ve 1,2,5,6,3,7,8,4
you have not discussed it for non connected components . btw nice explaination
im not sure but can we traverse to a node if its not even connected to the parent node?
Visited does that work
you r god of coding
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Awesome work, thank you!
why do we need to make vis[0]=1?? when the nodes are 1 based indexing and why do we need vis[n+1] when using 1 based indexing?
"UNDERSTOOD BHAIYA!!"
understood bro, love from bangladesh.
we should use for loop in main ic case of non-connected components right?
I would have liked to see the code for a DFS using a stack rather than recursion. It is more intuitive. It makes DFS and BFS almost identical except that DFS uses a stack and BFS uses a queue.
Hii bro
vector dfsOfGraph(int V, vector adj[]) {
vectorans, visited(V, 0);
stacks;
s.push(0);
while(!s.empty()){
int ele = s.top();
s.pop();
if(!visited[ele]){
ans.push_back(ele);
visited[ele] = 1;
}
for(int i = adj[ele].size() - 1; i >= 0; i--){
if(!visited[adj[ele][i]]){
s.push(adj[ele][i]);
}
}
}
return ans;
@@Raju_Sharma852 I know how to code it. I just thought it would be useful for other viewers to see it done in this video.
Liked the video, notes taken, understood
I have a doubt in this code of yours what if in a graph I give you two components you can traverse with only one component but for the other one this code will fail.
Now, to answer which will be the right code so in Striver bhaiya old series he explained that code which will run for every graph doesn't matter how many components you have.
I have the same doubt , if more than one disconnected components.
I am running the loop for all the nodes if there are disconnected components and passing visited array as reference then it giving me an error don't know why .
have you any idea why it is giving me an error while passing the reference of visited array . ???
@@jiteshjoshisde3154 share me the code in which you are facing error I will help you out.
//I think this code will work for unconnected components also
void dfs(vector&visited, int node, vector&ans, vector adj[]){
visited[node]=1;
ans.push_back(node);
for(auto it:adj[node]){
if(visited[it]==0){
dfs(visited,it,ans,adj);
}
}
}
vector dfsOfGraph(int V, vector adj[]) {
// Code here
vectorans;
vectorvisited(10000);
for(int i=0; i
@@amansinghal4663 for this u have to go from starting node to last vertix I actually use python see the code
def dfsOfGraph(self, V, adj):
# code here
ans=[]
visited=[False]*V
for i in range(V):
if visited[i] is False:
self.dfshelper(i,visited,adj,ans)
return ans
def dfshelper(self,SN,visited,adj,ans):
visited[SN]=True
ans.append(SN)
for i in adj[SN]:
if visited[i] is False:
self.dfshelper(i,visited,adj,ans) #It will work
Thank you so much! just finished it
Thank you very much. You are a genius.
Great Explaination
mawa super explanation
thaggedhe le
Understood Sir, Thank you very much
Why the visited array size is plus 1 ? In BFS also you have taken plus one size
great lecture bhai
Awesome work 👍
is it mandatory in graphs that we have nodes numbered like 1,2,3.... or can we use it like 2 ,5,9 something like that
Understood and rewatched to revise
Wouldn't this only work for connected graph? what would happen if there are multiple different connected components ?
Then you will have to declare visited array of type of vector and pass it by reference to DFS func and then run a loop in your main function for non-visited nodes.
@@KdStatusKing got it, thank you.
Understood beautifully!!!
for each node we are going through their adjacent node which is degree and sum of all degree is 2E so isnt time complexity is O(2E)=O(E),am i missing something?
if we have outer loop going 1 through n and in each iteration inner loop goes for 1 throguh i . so time complexity is 1 + 2 + 3 + n = O(n2) . why similar thing not happening??
Understood. Also, nice explanation.
understood, perfect explanation
Thankyou Striver, Understood!
A very silly question but still it keeps bugging me that why the time complexity is O(N + 2E) and not O(N*2E) as for each node we are checking all the edges . If anyone can clear my doubt it will be very helpful for me. Thanks in advance.
For a node E can change not every n has same E
Thanks... I solved this by myself...
Will no return statement in the void function not cause a problem?
nope,it's not necesaary to return something in void function( )
superb explanation
time complexity is O(N +2E) or O(N)+O(2E)??????
both means same 🙂
@@anshumaan1024 arre haaannnn..idk why i asked such a silly doubt😶
@@bageshwardham-1M it hapuns 🙃
Understood 😌
what is the base condition
there is some error with dfs travel: 1256487 , you forgot to write mark 3 as visited. overall its amazing, just watching it again to revise it, sorry if was rude.
great explanation bhaiya but you forget 3 to werite in ans
Understood ❤
in the dfs traversal node 3 is missing
When will all the videos be completed
Why we are not using Stack here instead of recursion.Kindly guide Anyone.
stack also uses recursion , and recursion make use of stack so both are just same.
recursion uses Call Stack which is nothing but a stack provided in order to handle function callings
so it is upto you that either you use your own Explicit stack or implicit stack ( i.e. Recursion or Call STack)
Understood. Thanks a lot.
thanks so much it was very helpful
if for each vertex, DFS visits all its adjacent vertices ..shouldn't time complexity be V*E ?
All the adjacent vertices will surely be visited for all nodes, but as it is an undirected graph that mean if an edge exists from 1 to 2 then that same edge will also be checked as an edge from 2 to 1 , so we are checking an edge 2 times so it adds to the time complexity.
can a graph contain similar nodes
Use V (for vertex) instead of N to remember better, N is ambiguous
Dfs vs Bfs which one should we use while solving question
you will automatically understand it by yourself,the more you practice.
understood sir👍👍
Hello bhaiya
I will be starting my college 2-3 months later since jee advanced is this month end ...... Can you make a video on what we can explore in first year of college
if you didn't qualify for the exam then he will help you
@@abhijeettripathi7615 are you talking about jee?
I did qualify it with 98.6 percentile..rank-11876 ....maybe I will get a decent Nit with ece branch .....just wanted to learn about coding and stuff before starting college
@@siddhantmishra5659 c++ with dsa ,thodi competitive coding bhi karlo
,full stack web development seekhlo
understood, thanks!
#Striver rocks🤟
why adj and vis are not passed by reference ? it is giving me error. we need to store there values in different function passes while recursion goes on naa
arrays are always passed by reference , when we pass an array as a parameter to a function , the pointer to the first element of the array is passed , so any changes in the array inside external function will reflect in the main function, or the changes made in the array remains !
@@amansinghal4663 thanks got it! and vectors are not always passed by reference ? right
@@prathmeshmodhe6330 Yes, vectors are not passed by reference automatically. You have to manually do it by using the "&" symbol.
understood striver!!!
what app do you drawing?
Errors n not declared + vector has no member named push
Vector bfs has no member named push
understood..and liked