G-5. Breadth-First Search (BFS) | C++ and Java | Traversal Technique in Graphs

[@takeUforward]

Let's continue the habit of commenting “understood” if you got the entire video. Do follow me on Instagram: striver_79

[@GauravThinks]

Bhaiya next bideo🥺 pls

[@amarjeetkumar-hk2jl]

US

[@BhavyaJain-qz8jg]

understood

[@sanketatmaram]

👍🏻

[@memeset048]

understood

[@UECSoumyaRay]

I can proudly say that this summer I watched more tUf lectures than Netflix episodes.

[@aniket6858]

Because your placement season is here

[@Moch117]

@@aniket6858 What is placement? Is this india

[@joseph2073]

@@Moch117 no, its pakistan.

[@congdatt]

what is the result ?

[@montynathan3318]

Yoh Netfilix ke hovey?😶‍🌫️

[@HARSHKAJALKHANEIIIIIIII]

THOSE WHO ARE WORDERING WHY IT IS O(N) + O(2E) NOT O(N*2E) For each node, the while loop runs multiple times based on the number of edges connected to that node. Here's how it works: In the first iteration, the loop runs for e1 edges, plus one extra operation for pushing and popping the node. In the second iteration, it runs for e2 edges, plus one extra operation for pushing and popping, and so on. Thus, the total time complexity is the sum of all iterations: (e1 + e2 + ... + en) + (1 + 1 + ... n times). The sum of all the edges connected to each node is equal to the total number of edges, which is 2E (since each edge is counted twice in an undirected graph). Adding the n push/pop operations gives the final complexity: O(V + 2E) because e1 + e2 + ... + en = 2E. So, the overall complexity is O(V + 2E), which simplifies to O(V + E).

[@moneshc6887]

Was searching for this thanks ... Just to summerize ... the inner for loop runs in O(2E) in total and not for each iteration of while so its O(V) + o(2E)

[@deepakdas4513]

@@moneshc6887 perfect

[@gourabbhattacharjee2128]

Just some simple words! No one can beat your DSA teaching style!!

[@chitrankusarkar7278]

17:04 i was still wondering where the heck vis[n] came from. edited like a pro

[@nextnotification9857]

same bro

[@poetrystation3178]

this code is not running editor is a pro for sure

[@devilkingyt07]

vis[V] = {0}

[@vipinrana5544]

same, didn't expect this from him

[@YeaOhYeahh]

If u r confused about time complexity part, then see the following dry run of the while loop of the qs. he has solved.. This is how nodes are connected(assuming undirected graph) : 0 -> 1 ,2, 3 1 -> 0 2 -> 0, 4 3 -> 0 4 -> 2 So, total no. of edges = E = 4 For first while loop , node = 0, edges = 3 Now, before going to the for loop part, u see a constant time operation O(1) --> q.pop( ) This step will be executed every time we enter into while loop. So, for first while loop how many times for loop will execute ?? It will be equal to the no. of edges , here it will be 3. Therefore, total = ( 1 + 3 ) Similarly for all other nodes, this is how it will look : ( 1 + 3 ) + ( 1 + 1 ) + ( 1 + 2 ) + ( 1 + 1 ) + ( 1 + 1 ) = 13 = O ( V + 2 * E ) = O ( 5 + 2 * 4 )

[@sumerrawat6947]

Very well explained !

[@Saurav_Kumar514]

Awesome 👌👌

[@mypowerlevelisover9000]

Thank you

[@YeaOhYeahh]

@@mypowerlevelisover9000 🙂

[@shaikhfaisal2423]

but at the worst case it will be O(n^2) right? since a complete graph have all the vertex with (n-1) edges. which will lead [(1+(n-1))=n] at each while and for loop. since after n times it will become n square. Please confirm this. BTW thanks for the explaination

[@creativearts6406]

I like the way you explain time and space complexities, which actually helps me to analyze my code complexities. Thanks for the explanation.

[@somz21ad]

Hey Striver! Thank you for creating outstanding content and helping people interested in coding problems worldwide! Please don’t stress yourself out, take a break after this one. It’s not easy to work full time and dedicate time for this.

[@nkgautam6161]

you are great striver. Explain such a complex topic in very easy manner. Your method of teaching is unique, a unique lecture by a unique teacher🙏🙏🙏

[@asadeducation9513]

understood..awesome..most of the youtuber's don't explain a topic in depth... great video

[@arthurdark3945]

Are you going to teach leetcode questions just like you did in DP series? It would be very helpful if you can teach commonly asked good questions covering different graph patterns and not just the basic ones.

[@takeUforward]

Yups, this one is going to be 50+ videos.

[@pranavsharma7479]

@@takeUforward bro try to cover as max you can till 15 aug, thnks for helping

[@YCCMdigo]

Thank you man from the bottom of my heart for this video. You're one of the greatest instructors i've ever seen

[@priyadarsinipaikaray4998]

You are amazing 🤩 Guru wo hota h jo muskil si cheez ko v Asan karde tushi great ho ji striver ❤

[@prakharjain6611]

17:02 the code he wrote has errors , 17:06 the errors are gone .

[@multiverseofcomputerscience]

after seeing your post on LinkedIn that you are launching graph series 2.0 i used to see your KZbin playlist daily now I am very happy thank you very much 💗

[@anuraggoswami3534]

57 +videos trurly 🇮🇳 biggest graph series Ironically GOAT 🐐 is teaching GRAPH 🤩

[@supriyamanna715]

coded on my own! Got an error, resolved the issue, all TC passed! Note taken

[@futurev14]

Toh tujhe kya lg rha bada jhanda gaad diya tune saale itne chappal maruga

[@tharaniarumugam-zb9il]

Your videos never fail to save us anytime :) Undhan rasigaiyee naaum unaken puriyavillai...

[@raghvendrakhatri5848]

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.

[@foziezzz1250]

how does adj[node] an int is iterable ? shouldnt it be vector adj in the function definition too?

[@simmi641]

Thank you so much stiver. Happy Teachers dayy

[@atharvamore342]

14:30 program starts

[@shreyyyc]

Thanks a lot stiver for putting all these playlists out. i can't imagine getting a job if you were not on youtube. i have a little doubt that in "bfsOfGraph" function the syntax of adj[ ] should be this "Vector> adj [ ]" but it is "vector adj[ ]" instead and this is a 1D vector not a vector of vector.

[@iitbhuvictim]

Here you're creating an array of vector.... basically number of vector is fixed....that is the way to create array of vectors

[@lakshsinghania]

there is a similar comment in the video number G-2 check that out

[@ayushmishra9758]

Hence, vectoradj[n] n is no of vertices.(0 based) . adj creates an array where each adj[i] is a vector itself. Array of VECTORS.

[@prachi1112]

Same doubt. if we're storing an array at each index of the vector, shouldn't it be vector adj instead of vectoradj??

[@ShivamTh405]

@@prachi1112 We are storing vector in array index, i.e array of vectors. Every node of array denotes an array . Eg -> if we write int arr[] , here data type is int , so it is array of integers, but if we write vector arr[] , here data type is vector , so it is array of vector

[@siddharthpatil3046]

Time complexity of BFS may be different depending upon representation of graph. Adjacency List: O(V+E) Adjacency Matrix: O(V^2) where V=no of vertex and E = no of edges

[@kulkarnisoham]

Awesome Space & Time Analysis 🔥🔥🔥🔥🔥🔥🔥🔥

[@devByDash]

00:01 Breadth-First Search (BFS) is a traversal technique in graphs. 02:16 Breadth-first search (BFS) traversal of the graph 04:25 Breadth-First Search (BFS) is a traversal technique in graphs. 06:37 Breadth-First Search (BFS) is a traversal technique in graphs. 08:54 Performing BFS traversal on a graph using adjacency list representation 11:35 BFS traversal of graph 14:04 Implementing Breadth-First Search (BFS) in C++ and Java 16:01 Breadth-First Search (BFS) is a traversal technique used in graphs. 18:04 BFS algorithm runs on all the neighbors of each node Crafted by Merlin AI.

[@RanjeetKumar-dr5ds]

understood

[@crazybro4383]

This guy teachers so fuckin good that if I try seeing DSA related video from any other utube channel it feels something is missing, he's not striver

[@aniketshukla2426]

I'm confused on the Time complexity, If we know the while loop runs N times and the size of the adjacency list is 2E, It is alright to add them to get the time complexity? like, the while loop runs N times and the for loop overall runs 2E times..??

[@jatinkumar4410]

Amazing explanation! I have a doubt regarding time complexity 18:34 . For loop is running inside while loop right? So shouldn't we multiply both as: O(n*(2E)) instead of adding both as: O(n) + O(2E). Thanks for the content.

[@amanbhadani8840]

No,it would have been multiplied only when for each node total number of adjacent node is 2*e,but this is not the case,here ultimately we are overall visiting n nodes and for each node,visiting its adjacent nodes,which is total of 2e for total nodes.

[@himanshupoddar1395]

@@amanbhadani8840 2E or E, shouldn't be the number of edges, which was E here in this example?

[@ayushgarg9099]

@@amanbhadani8840 very well addressed brother!!

[@ayushgarg9099]

@@himanshupoddar1395 No, in the case of undirected graph you have to traverse 2*E edges.

[@syedfaheem1185]

I am having a question regarding the TC. How can it be O(N+2E). Since, the outer loop runs as long as the queue isn't empty, which means it will run exactly N times and for each vertex or node, we check if the neighbours are visited and if not, we add them to the queue. Now, at each node, we're checking whether it's neighbours are visited or jot which is itself an O(1) operation. So, for N nodes, we are performing operations equal to the degree of a node. How can the TC not be O(n*avg. degree).

[@DevanshuAugusty]

17:03 i see what you did there 🤣🤣

[@alina8023]

no one commented on this :(

[@test-nature]

I was happy to say that I will do and understand first graph problem.🎉

[@ancycoding]

BEST DSA TEACHER FOR ME

[@ronnie3357]

16:56 if the start node is not 0 then the list corresponding to node 0 will be empty hence the queue will become empty after 0 is processed and since node 0 do not have neighbours so the for each loop will not be executed so queue will remain empty and bfs will only contain 0 please address this doubt sir

[@amithmagajikondi69]

Exactly my thoughts! The implementation seems wrong. It should be q.add(V) & visited[V] = true

[@cinime]

Understood! Awesome explanation as always, thank you so much!

[@yashrawat5158]

those who are doing on Codestudio we first have to create adjlist first so here the easy solution to it using set #include void prepareList(unordered_map &adjlist,vector &edges){ for(int i=0;i

[@aniketshukla2426]

What about Directed Graphs, It applies for them too? I think yes, because the adjacency list will only have those edges so we only traverse those edges

[@GeneralistDev]

9:39 ASMR moments

[@doingdifferent7714]

Wont Time Complexity be O(n*2E)?? Since for each node n we are traversing 2E

[@takeUforward]

But once you have travelled for all nodes, all are visited, you won’t again traverse na. Overall you will travel everyone once only

[@CuriousAnonDev]

nooo!!! you don't know what E is!! E is total no of edges of whole graph in V + E in your n*E, E is no of neighbours of a particular node!!! see... for every node(while loop) you are running "for" loop for number of times==number of its neighbours so in that case you can say n*e but the thing is this -> for every node number of neighbours are different hence we don''t write complexity like you have written while loop n times run karega aur andar wala for loop jo hai, woh in total, sab while loop ka milake, E(total edges in whole graph) times run karega isliye toh add kiya N aur E ko ab clear ho jana chahiye me bhi atka tha ispe 3-4 dinse same concept dijkstra, prims me bhi apply hoga so make sure you understand it!

[@dhananjayvaish3276]

@@CuriousAnonDev thanks for indepth explaination !

[@Lullurluli]

@@CuriousAnonDev naam dekh kar mai bhi atak gaya

[@Maunil2k]

Nice and crystal clear explanation !!

[@p38_amankuldeep75]

great content loving this after completing dp series💙💛💙

[@sourabhkushwah9711]

Haha I see how you swithed the code between 17:02~17:05 but you should have told the audience rather than chaging the frame. I bet most of them were confused why thier code was not working until they saw you changed the vis[n] with vis[V] because initally I was confused how does your code worked when litrally N is not defined anywhere. and its push_back how does push worked for queue. then I saw the immidiate frame change😂😂 that was sneaky.

[@Tbm4545]

Yup u get confused if u pause the video in between, even i got confused then i just watched even i saw that frame where he changed it to V and ya its ohk. We understood it.

[@farazjawaid2982]

a well explained and organised lecture !!!

[@addictedtocricket8827]

how can someone be so perfect in explianing concept

[@shashankdesai8650]

Ohoo masthhh bhaiyaaaa Woohoo

[@satishsingh8297]

Thankyou striver bhaiya! ❤️

[@alt-f4gaming222]

congrats bhaiya for 300k ek din apan sath me 1m jayenge

[@hashcodez757]

"UNDERSTOOD BHAIYA!!"

[@rameshbabuy9254]

please also explain space and time complexities

[@akshaikumar7966]

i loved it sir , what a beautiful explanation

[@aditya_raj7827]

You are amazing striver ❣️

[@MischievousSoul]

There was some sound glitch for 30 sec.. Was weird but Loved the way you teach and i am here after conpleting your trees playliat... ❤

[@rajsekhardutta8891]

What an amazing explanation! Understood! 🤩❤‍🔥

[@Sillysmiles76]

Understood, Happy Learning🤗

[@paullater6230]

understood!! Explained beautifully!!

[@udaypratapsingh8923]

here we go !

[@ayushagrawal6700]

I think bool data type will be better than int data type for visited array because bool data type takes 1 byte whereas int data type takes 4 bytes. And If I am wrong pls correct me :)

[@infinityzero2321]

ya no issue ... just taking int as it would help with weighted graphs as well and generalize the approach

[@PCCOERCoder]

Lecture successfully completed on 03/12/2024 🔥🔥

[@tanaysingh5348]

very well explained with all the minute details

[@stith_pragya]

Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@Highlights_Point]

Thanks Bhaiya

[@ramanpareek5218]

Liked the video, notes taken, understood

[@codeofcoffee8722]

There is a small correction between 16:56 and 17:05 , pls re-edit . It will help the beginners, remaining everything is cool stuff ., Striver.

[@oqant0424]

5/56 done(3.12.22)

[@lexeve5298]

at 8:40 i think if we are writing 0 -> {} it will be a component of graph, its just the single node, someone please correct me if I am wrong

[@raiusamaakram]

brilliantly explain thanks sir and neeed complete playlist of DSA from you for cracking google like companies

[@likhitbhogadi]

hats off to ur hard work.

[@dhananjayg8332]

crystal clear.. excellent explanantion

[@its_kundan]

what if the graph have different components? the solution seems to solve the connected components only.

[@ashish2736]

Hi @TakeUforward, I had a doubt, when the for loop is inside the while loop, shouldn't we multiply the time complexities instead of adding them?

[@IITians]

understand with the following explanation (just copy-pasted) This is how nodes are connected(assuming undirected graph) : 0 -> 1 ,2, 3 1 -> 0 2 -> 0, 4 3 -> 0 4 -> 2 So, total no. of edges = E = 4 For first while loop , node = 0, edges = 3 Now, before going to the for loop part, u see a constant time operation O(1) --> q.pop( ) This step will be executed every time we enter into while loop. So, for first while loop how many times for loop will execute ?? It will be equal to the no. of edges , here it will be 3. Therefore, total = ( 1 + 3 ) Similarly for all other nodes, this is how it will look : ( 1 + 3 ) + ( 1 + 1 ) + ( 1 + 2 ) + ( 1 + 1 ) + ( 1 + 1 ) = 13 = O ( V + 2 * E ) = O ( 5 + 2 * 4 )

[@vip-qg1zl]

​@@IITiansgreat

[@AryanVerma-y3m]

you are the best stiver

[@sreehithathatwadi5210]

Isn't the TC is O(N* 2E)? Because we run for loop on each node's degree.

[@YupIam-f4t]

yeah, I got the same doubt. Its multiplication only .

[@NitishKumar-yy9kn]

@@YupIam-f4t not, it will be adding only because 2E is equal to degree of all nodes, not 1 node. so we can't think like for each node, it is taking 2E time and hence it will not be n*2E

[@AbhishekGupta-kn3cz]

This was great, wandering about traversing Graph with starting nodes somewhere in middle. Should that be traversed wrt to levels or some-other way?

[@hemachel175]

Thanks for the video buddy. I understood everything except the point where you sum the O(N) and O(sum of degrees of nodes) to find the time complexity. why the sum is there? I think the inner loop will be running 2E times which should be the complexity only. can you please elaborate on why the sum of O(N) is also needed here?

[@ayat_middya]

Wonderful bhaiya.....

[@atharvameher5880]

07:08 "someone has been touched, wait"💀💀

[@unfamousgaayak4838]

At 16:09 queue declaration is not clear. How it is new linkedlist ? Can anyone help?

[@yashpadiyar4952]

Thankuu sooo muchhh broooo🤗🤗🤗❤❤❤❤❤

[@abhichi]

Understood..next please ✌🏻

[@paulangelp7099]

Fantastic 🎉 Understood

[@atharvameher5880]

My favourite algorithm so far, Breast First Search

[@NarenderMajoka]

TC: 17:32

[@phlox22]

helllo , i am confused in this line "vis[n]" when i run the program it's saying "n" not declared but when i corrected it with vis[V-1] V being no. of vertices of graph it worked fine , so my question is , what is n here exactly ? number of edges or vertices used for declaring visited array?

[@phlox22]

i got the same error as well , he did a mistake on declaring visited array first time ,it should be "Visited[V]" not "visited[n]" ,so what you did was correct

[@sripriyapotnuru5839]

Thank you, Striver

[@subhamoybera6456]

Great explanation

[@codeman3828]

Great series

[@umeshkaushik710]

Great work. Thanks for doing this.

[@kartikshukla5018]

Thanks sir .... best solutions

[@morganyu3391]

Understood bhaiya!

[@rishabhagarwal8049]

Understood Sir, Thank you very much

[@samuelfrank1369]

Understood. Thanks a lot.

[@gunahawk6893]

Woah nice explanation

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@hopelessboys3004]

love you from bangladesh

[@karthik-varma-1579]

Telugu people attendance❤

[@vasachisenjubean5944]

Really bro ? This is what you do online ?

[@harshdeep7312]

bhaiya space complexity will be O(2n) not 3n because we have to return bfs vector correct me if i am wrong

[@mahaprasadm9770]

brilliant explanation!

[@jatilyadav4000]

Great video Loved it

[@prasangsayzzhii]

3:43 Understand BFS in Depth !