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; }
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
@@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.
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; } };
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😀
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)
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 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.
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
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.
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)
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
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
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.
the best playList on graphs i ever see..Thank you so much 😊😍
Best video tuturials on the you tube absolutely!!!
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
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 as always, thank you very 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
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 😅
striver op...explanation op....... graph series SUperrrrrrr OP
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)
understood each and every bit of your explanation...
lol mena 0.5 pa dekh lia puri video too funny .
nice video bro
Amazing explanation as always.
UNDERSTOOD!!!!!!!!!!!!!!!!!!!!!!!!!
Completely UNDERSTOOD.
Understood! Amazing explanation
Please make a videos on number theory
Thank you very much. Great 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
best series on Graph👍
your contribution is matchless. thank you.
you r god of coding
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.
great and amazing work! Loving it, thanks a lot❤
"UNDERSTOOD BHAIYA!!"
Thank you, Striver 🙂
Understood Striver!! Thank you so so much for these amazing lectures :)
Understood each and every word♥
Great Explaination
Understood. Also, nice explanation.
Liked the video, notes taken, understood
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
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Awesome work, thank you!
Understood and rewatched to revise
understood, perfect explanation
understood bro, love from bangladesh.
Thank you very much. You are a genius.
Understood Sir, Thank you very much
great lecture bhai
Thanks... I solved this by myself...
Thankyou Striver, Understood!
Understood beautifully!!!
Understood 😌
superb explanation
Thank you sir
understood sir
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
Understood ❤
Awesome work 👍
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
#Striver rocks🤟
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.
Understood. Thanks a lot.
Understood bhaiya
thanks so much it was very helpful
understood.. Depth!!!! Depth!!! Depth!!!!
understood, thanks!
Understood sir.
Thanks. Understood.
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 bhaiya
In java code why have we taken the size of visited array as v+1 when graph nodes are zero indexed
Can we not use stack method, if so please provide the code for it
understood striver
understood sir👍👍
Understood🌻
understood!
Use V (for vertex) instead of N to remember better, N is ambiguous
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
Understood 🎉
understood..and liked
understood thank you
6/56 DONE (3.12.22)
currently at which video or completed on which date graph series?
14:03 You forgot to mention 3 in DFS call. It should ve 1,2,5,6,3,7,8,4
understood striver!!!
Thanks striver
thank you
Can a stack based solution be made for tha same DFS?
Understood strvier sir ;)
great explanation bhaiya but you forget 3 to werite in ans
Understood.
great content
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)
UNDERSTOOD
understoooooooooood
tysm sir
understood..
understood.
Understood:)
Revisit:)
Understood!
Understood...
superb