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.
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
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.
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'
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 🤩😇
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.
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
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; }
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)
@@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.
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
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
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??
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?
@@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, i have written the code same to same as you had explain in this video, but i found this code is giving segmentation fault. But the code that you have gave us in github that was working. Why the code that was explained is not working? plzz explain
Can we do without queue.. I used recursion and recursion itself does the work what queue does here... void bfs(ll node, vector *arr, ll *visited){ if(!visited[node]){ cout
