Your teaching is really awesome bhai, I have taken GFG dsa course but i unable to understand graphs concepts property but after watching your graph's video series now i can say i can any basic graph, Thank you for your quality content.
Striver, your explanation is always so good that after watching just 3-4 mins of your explanation I'm able to code and think the rest part on my own. Gives me a lot of confidence .Crystal clear concepts.
Anyone explain this please!! in the beginning we put 1 in the queue and mark it as visited , then inside that for loop we also mark adjacency of node 1 , that is node 2 as visited , now in the second iteration of first for loop it will check if the node 2 is visited or not and found that 2 is already visited during first iteration where we checked adjacency nodes of 1 and found 2 their and marked it as visited ,then it will ignore the if condition and it will check for 3rd iteration.... so how do we find adjancency nodes of node 2 ? please anyone clear my doubt.
This is nice explanation and really helped me to grasp the template to write a BFS traversal code for a give graph. I've a suggestion though, whenever you are referring using 'Queue', try to draw it with a horizontal rectangular box, this vertical box would typically used to represent 'Stack'
On GFG, their test cases have disconnected graphs but they expect the answer only to be the bfs traversal of component containing node numbered 0. Don't waste time. Just run your code without the loop. It will pass the test cases
for visited array, we can use visited arary of type bool instead of type int, this won't change the TC of SC at all, but it will use some lesser space.
Can't believe that this topic was hard for me before i watched the video....but after watching the video it's like the most easy thing ..thank u so much sir ....this video was very helpful 🤩😇
The outer for loop should iterate from 1 to n ..(not from 1 to v) , and the size of vis (visited) vector should also be equal to n ( not v) Correct me if i am wrong .........much needed series striver bhaiyya ...thank you :-)
Anyone explain this please!! in the beginning we put 1 in the queue and mark it as visited , then inside that for loop we also mark adjacency of node 1 , that is node 2 as visited , now in the second iteration of first for loop it will check if the node 2 is visited or not and found that 2 is already visited during first iteration where we checked adjacency nodes of 1 and found 2 their and marked it as visited ,then it will ignore the if condition and it will check for 3rd iteration.... so how do we find adjancency nodes of node 2 ? please anyone clear my doubt.
Thank you Raj bro. However could u pl help me understand why you are telling time complixty is O(n) ? you have outer for loop then while loop and then for loop inside. so time complicity is l*m*n of not n^3 please let me know
Can anyone please help me in this: when instead of auto, I wrote- vector:: iterator it, then I need to replace 'it' in the loop with *it, so I want to ask that if we use auto, does that mean that we can simply use the variable as index? that is 'it' is no longer pointing to the cells of the vector, rather is working as indices?
when iterator is used, you need *it to access value because iterator is just like pointers in C++ for example: suppose we need to print values from key-value pairs in a map //auto can be changed to map::iterator for (auto it = mp.begin(), it!= mp.end(), it++) cout
Why the time complexity is 0(N+E) but not 0(N+NE) because for reaching 1 node it will take 0(1) and in the worst case every node is connected with every node so accessing all adjacent nodes for 1 node will take 0(E) if we repeat the task for N node dont we get 0(1)+0(1)+.......n => 0(N) for all N nodes and for all adjacent nodes it will be N *0(E) so total will be 0(N+NE) ?
No because here we used visited array if adjacent node is already visited then we dont visit it twice so i guess t.c should be o(n) but also don't know why t.c=o(n+e)
The size of the visited array should be (the value of the vertice having maximum value in the graph among all vertices+1) not (number of vertices+1) in the code
@@takeUforward No! It has a Note: One can move from node u to node v only if there's an edge from u to v and find the BFS traversal of the graph starting from the 0th vertex, from left to right according to the graph. Also, you should only take nodes directly or indirectly connected from Node 0 in consideration.
I am taking the input in adjacency list in main function and also making the vis array in main function but when i am passing them in my find bfs function ,it is giving an error.Should I pass the reference??
@@varsha9094 It is fixed that values in graph starts from either 0 or 1!! or else we can subtract the value for example if we want to put the values like a,b,c by traversing the graph we get( Integer)(currchar-'a').
Instead of using array we could use map and insert all the vertices to map and iterate the map and when we vist the vertices make it true in map, so that we can acces it in constant time and TC and SC also will not exceed, also it will work if graph contains character
Bhaiya your code is not working actually you take while loop inside if condition . /*correct code*/ vector bfsOfGraph(int V, vector adj[]) { vectorv; vectorvisited(V+1,0); queueq; q.push(0); visited[0]=1; while(!q.empty()){ int node=q.front(); q.pop(); v.push_back(node); for(auto it:adj[node]){ if(visited[it]==0){ q.push(it); visited[it]=1; } } } return v; }
Plz help me with this doubt. I've always found it difficult to understand why Time and Space complexity is O(V + E) in both BFS as well as DFS? Why not O(V*E) or O(Max(V, E)), etc?
@@letsinevolve6230 @Let's InEvolve no of vertices, but you too didn't mentioned what Vand E are(just kidding), oviously it is vertices yr bcz we are travelling all vertices via edges and also visited array makes sure we won't travel same vertices twice,isn't it>
@@dillitimalsina6003 My bad😅. I got more confused now! You're right, we're not re-visiting any vertex.. so the complexity could be O(V). But I guess cuz we're looping within a recursion, the complexity certainly can't be just O(V) ...right?
Your teaching is really awesome bhai, I have taken GFG dsa course but i unable to understand graphs concepts property but after watching your graph's video series now i can say i can any basic graph, Thank you for your quality content.
TC & SC: 13:26
Java code: 14:16
C++ solution: 17:12
Striver, your explanation is always so good that after watching just 3-4 mins of your explanation I'm able to code and think the rest part on my own. Gives me a lot of confidence .Crystal clear concepts.
Out of all the videos online, yours is the only one that made me understand the algorithm. Thank you! Commenting for the algorithm!
CLEAR CLEAN QUALITY CONTENT.
U are providing a strong foundation for graph.
Thank You
Is it your teaching or my understanding level have raised...haha....Thanks bro, you made it simple.
Anyone explain this please!!
in the beginning we put 1 in the queue and mark it as visited , then inside that for loop we also mark adjacency of node 1 , that is node 2 as visited , now in the second iteration of first for loop it will check if the node 2 is visited or not and found that 2 is already visited during first iteration where we checked adjacency nodes of 1 and found 2 their and marked it as visited ,then it will ignore the if condition and it will check for 3rd iteration.... so how do we find adjancency nodes of node 2 ?
please anyone clear my doubt.
@@madhabkafle8898 check on 2's visit wont be performed immediately after 1's adjacent nodes are put inside the queue
This is the best channel for dsa cp on youtube!
This is nice explanation and really helped me to grasp the template to write a BFS traversal code for a give graph. I've a suggestion though, whenever you are referring using 'Queue', try to draw it with a horizontal rectangular box, this vertical box would typically used to represent 'Stack'
On GFG, their test cases have disconnected graphs but they expect the answer only to be the bfs traversal of component containing node numbered 0. Don't waste time. Just run your code without the loop. It will pass the test cases
Yes exactly i was doing the same using loop but then i dry run and got to know that they only want for vertex 0
Exactly 💯💯 thanks man....
Thanks buddy
Can you please tell me, what will be the difference between the code of the BFS of directed and undirected graph? They are same or not?
@@tanishsharma5440 yes directed or undirected doesn't matter for a normal bfs traversal
for visited array, we can use visited arary of type bool instead of type int, this won't change the TC of SC at all, but it will use some lesser space.
0 Dislikes. Power of Honesty.
Now there are 9🙂
Can't believe that this topic was hard for me before i watched the video....but after watching the video it's like the most easy thing ..thank u so much sir ....this video was very helpful 🤩😇
Quality at its peak as usual ! ♥️
this is the best playlist to learn graphs
This graph is so useful bhaiya Thank you , please make more series like this of different topics too, it's really helpful ...👍🏻
Please please please make a series on tree🙏🙏🙏
The way you explain the topics are fantastic... Please help us in trees also
Great explanation! It is easily understandable with your video. Thank you so much!
Amazing explanation! This topic always went above my head before this video.
Before watching this video I was confused why we used that visited array
The concept is crystal clear now
you are really doing a great work sir ... thank you so much for this playlist !
I will be posting a video every Sunday on the other channel, so bell DABAAAAA dena: ua-cam.com/channels/vEKHATlVq84hm1jduTYm8g.html
What a video series just before internship drive in my college
Very helpful. Thanks for your efforts!
These are some really good lectures 👍, one suggestion/request put timestamp in videos.
TAKE A BOW MAN🙇♀🙇♀🙇♀🙇♀🙇♀
bhai itna sahi padhate ho aapke video dekhta main hu place mera padosi ho gaya hai!
for skip promotion go to 4:22
The outer for loop should iterate from 1 to n ..(not from 1 to v) , and the size of vis (visited) vector should also be equal to n ( not v)
Correct me if i am wrong .........much needed series striver bhaiyya ...thank you :-)
n and v are the same thing(no. of nodes) here lmao
Best explanation. understood , hope this channel reaches more people
Anyone explain this please!!
in the beginning we put 1 in the queue and mark it as visited , then inside that for loop we also mark adjacency of node 1 , that is node 2 as visited , now in the second iteration of first for loop it will check if the node 2 is visited or not and found that 2 is already visited during first iteration where we checked adjacency nodes of 1 and found 2 their and marked it as visited ,then it will ignore the if condition and it will check for 3rd iteration.... so how do we find adjancency nodes of node 2 ?
please anyone clear my doubt.
very great explanation
You are doing Great,Good explanation.
Great Explanation.
I wish I could have watched this video before my Google STEP Intern interview😖. Thankyou bhaiya for amazing explanation.
Thanks for the series bhaiya🙌
this is excellent...can you do the same series for binary tree and linked lists
19:25 the c++ code
Understood! Thank you so much as always!!
nice explanation , thanks
1st comment. Bhaiya U are great ❤️.pls make video on CHEAT sheet on CP for Coding Round pls🙏🙏
Cp sheet striver youtube me search kro
@@takeUforward Mill gya Bhaiya video. Now I will follow it. Thanks bhaiya❤️❤️
Nice explanation
Mauj kardi Bhai 😁
Crystal Clear
Thank you, Striver!!!
Well explained!!
amazing brother
C++ code at 19:26
bhaiya after completeing this can you suggest problems we should try ??
yes
try hackerrank graph theory sums
Heree it goes
For *visited* array,
Why take 'V+1' nodes and start from index 1?
Why not 'V' nodes and start from index 0?
V will also suffice if starting node is 0 else we will have to use V+1
Thank you
understood Thanks
Understood Brother!
Great video. 1 thing, I was checking out your java solution, it doesn't cover disconnected components.
What changes do we need to make if the source node is not 1 but some other node?
Thanks a lot bhaiya ♥️✨
Really great explanation!👍👏👏
Great Explanation btw for loop logic is not working on gfg why is it so ????
yes its not working
thanks a lot lot lot... bhaiya.
code explained and provided in description box is different , I understood but it creates confusion. Anyway loving watch and learn
Code provided is for single component and code explained in video is for multiple component
What changes should we need to make if the graph starts from 0, In for loop if we write i=0;i
The code works at gfg.
Check the code given in description as well
you are crrt it doesnt work with for loop
because the for loop is for multiple components where as in gfg the test case is for single component only
@@aditya14-02 yup you are right
19:27 c++ solution
thanks mate
Concepts are crystal clear but would have been better if a BFS traversal for adjacency matrix was also covered
I think we can apply similar by creating a adjacency list from the adjacency matrix
Thank you Raj bro. However could u pl help me understand why you are telling time complixty is O(n) ? you have outer for loop then while loop and then for loop inside. so time complicity is l*m*n of not n^3 please let me know
Have you got the answer?
itna achha bfs kisi ne nahi samjhaya aaj tak
Thank you!!
Can we initialise the queue before for loop??
adjacency list just doesn't print edges in increasing order. WILL IT AFFEct the PATTERN OF TESTCASES IN ANY PROBLEM OF GRAPHS?? Pls answer...
Can anyone please help me in this: when instead of auto, I wrote- vector:: iterator it, then I need to replace 'it' in the loop with *it, so I want to ask that if we use auto, does that mean that we can simply use the variable as index? that is 'it' is no longer pointing to the cells of the vector, rather is working as indices?
Yes..it is the value itself..
when iterator is used, you need *it to access value because iterator is just like pointers in C++
for example: suppose we need to print values from key-value pairs in a map
//auto can be changed to map::iterator
for (auto it = mp.begin(), it!= mp.end(), it++)
cout
@@chetanraghavv It is very informative. Thanks for sharing.
superb
Constructive criticism: Striver if you explained how the frontier kind of ripples out I would have made sense quicker to me.
whoa !!🤩🤩
thank you sir
Why the time complexity is 0(N+E) but not 0(N+NE) because for reaching 1 node it will take 0(1) and in the worst case every node is connected with every node so accessing all adjacent nodes for 1 node will take 0(E) if we repeat the task for N node dont we get 0(1)+0(1)+.......n => 0(N) for all N nodes and for all adjacent nodes it will be N *0(E) so total will be 0(N+NE) ?
No because here we used visited array if adjacent node is already visited then we dont visit it twice so i guess t.c should be o(n) but also don't know why t.c=o(n+e)
understood
The value of 'i' is a constant incase the starting point is mentioned from earlier.
Right?
plz make more series on other data structures like tree & linkedlist
You're voice became so sweet when you speak Hindi please try some time.
For directed graph just remove the for loop it worked fine!!
which for loop?
The size of the visited array should be (the value of the vertice having maximum value in the graph among all vertices+1) not (number of vertices+1) in the code
It makes sense to use the for loop.
Why is that gfg accepts the solution without the for loop?
Does not have a test case with multiple components
@@takeUforward bhaiya after completeing this can you suggest problems we should try ??
@@takeUforward No! It has a Note: One can move from node u to node v only if there's an edge from u to v and find the BFS traversal of the graph starting from the 0th vertex, from left to right according to the graph. Also, you should only take nodes directly or indirectly connected from Node 0 in consideration.
so we will just do it without for loop
I am taking the input in adjacency list in main function and also making the vis array in main function but when i am passing them in my find bfs function ,it is giving an error.Should I pass the reference??
I think you need to use arr.get(i).get (j) to access the every elements of array list.
understood!!!
Is there any problem in taking the queue just before the start of the first for loop?
you made it so simple vaeya :)
What Happens if the values of nodes in graph doesnt start from 1,what if it starts from 10 or 20??
Even I got the same doubt...you got the answer??
if it starts from 10 then you make vector adj[N+11] and now just traverse from 10 to N+10 like this for(int i=10;i
@@varsha9094 It is fixed that values in graph starts from either 0 or 1!! or else we can subtract the value for example if we want to put the values like a,b,c by traversing the graph we get( Integer)(currchar-'a').
Instead of using array we could use map and insert all the vertices to map and iterate the map and when we vist the vertices make it true in map, so that we can acces it in constant time and TC and SC also will not exceed, also it will work if graph contains character
Bhaiya your code is not working actually you take while loop inside if condition .
/*correct code*/
vector bfsOfGraph(int V, vector adj[]) {
vectorv;
vectorvisited(V+1,0);
queueq;
q.push(0);
visited[0]=1;
while(!q.empty()){
int node=q.front();
q.pop();
v.push_back(node);
for(auto it:adj[node]){
if(visited[it]==0){
q.push(it);
visited[it]=1;
}
}
}
return v;
}
sir how to prevent stack overflow for huge data in recursion ?
bhaiayya, I have a question weather implementation with Adjacency list is good or with vector matrix??
Analyse complexity u will understand
See the 2nd video man ....don't skip any otherwise the base will not build up.
@@jackwalker2947 yeah it happened exactly I did not se sequence of the videos
@@sumitmukharjee5816 Adjacency list
I'm a beginner can some one clear my doubt, I feel this bfs in not universal😅
What if the starting index is 0
What if we want another starting vertex
you can start with any vertex .
i implemented this on gfg, they are not considering multiple components of the graph
Start a series on LLD System Design
20:14 why take array of size v+1???
Because the vertex no.
is starting from 1 and not 0
cannot open your course where u teach pls give me the link
what is that tc in cpp code .what does it mean MULTIPLE GRAPH.
If i complete this series does that mean that i have covered all the topics for graphs that are required for Placements and stuff?
Yes
100% true,but 100 to 150 etra question practice would be required to crack good company beside sde sheet
Plz help me with this doubt. I've always found it difficult to understand why Time and Space complexity is O(V + E) in both BFS as well as DFS? Why not O(V*E) or O(Max(V, E)), etc?
I am confused why not only o(n) why subtitle showed o(n+e),clearly it should be o(n) na
@@dillitimalsina6003 You need to specify what's 'n' when describing time and space complexity. Are you taking about number of vertices or edges?
@@letsinevolve6230 @Let's InEvolve no of vertices, but you too didn't mentioned what Vand E are(just kidding), oviously it is vertices yr bcz we are travelling all vertices via edges and also visited array makes sure we won't travel same vertices twice,isn't it>
@@dillitimalsina6003 My bad😅. I got more confused now! You're right, we're not re-visiting any vertex.. so the complexity could be O(V). But I guess cuz we're looping within a recursion, the complexity certainly can't be just O(V) ...right?
for(auto it: adj[node]) could not understand this line.....can anyone help me out
Its for each loop. Since adj[node] means a vector hence it will iterate in it, and it will be iterating on every integer
didn't get this line i.e auto it:adj[x]. what is the another way of writing this ?
Bhaiya, I have tried to implement bfs recursively:
vector adj[n + 1];
int vis[n + 1] = {0};
queue que;
void bfs(int i) {
vis[i] = 1;
cout