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 )
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
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).
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.
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.
after seeing your post on LinkedIn that you are launching graph series 2.0 i used to see your UA-cam playlist daily now I am very happy thank you very much 💗
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
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
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.
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.
@@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
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).
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
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..??
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.
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 :)
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 )
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!
Let's continue the habit of commenting “understood” if you got the entire video.
Do follow me on Instagram: striver_79
Bhaiya next bideo🥺 pls
US
understood
👍🏻
understood
I can proudly say that this summer I watched more tUf lectures than Netflix episodes.
Because your placement season is here
@@aniket6858 What is placement? Is this india
@@Moch117 no, its pakistan.
what is the result ?
Yoh Netfilix ke hovey?😶🌫️
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 )
Very well explained !
Awesome 👌👌
Thank you
@@mypowerlevelisover9000 🙂
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
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).
Just some simple words! No one can beat your DSA teaching style!!
17:04 i was still wondering where the heck vis[n] came from. edited like a pro
same bro
this code is not running editor is a pro for sure
vis[V] = {0}
same, didn't expect this from him
I like the way you explain time and space complexities, which actually helps me to analyze my code complexities. Thanks for the explanation.
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🙏🙏🙏
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.
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.
Yups, this one is going to be 50+ videos.
@@takeUforward bro try to cover as max you can till 15 aug, thnks for helping
understood..awesome..most of the youtuber's don't explain a topic in depth... great video
coded on my own! Got an error, resolved the issue, all TC passed! Note taken
Toh tujhe kya lg rha bada jhanda gaad diya tune saale itne chappal maruga
You are amazing 🤩
Guru wo hota h jo muskil si cheez ko v Asan karde tushi great ho ji striver ❤
Thank you man from the bottom of my heart for this video. You're one of the greatest instructors i've ever seen
after seeing your post on LinkedIn that you are launching graph series 2.0 i used to see your UA-cam playlist daily now I am very happy thank you very much 💗
57 +videos trurly 🇮🇳 biggest graph series Ironically GOAT 🐐 is teaching GRAPH 🤩
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
Your videos never fail to save us anytime :) Undhan rasigaiyee naaum unaken puriyavillai...
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
17:02 the code he wrote has errors , 17:06 the errors are gone .
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 was happy to say that I will do and understand first graph problem.🎉
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.
Here you're creating an array of vector.... basically number of vector is fixed....that is the way to create array of vectors
there is a similar comment in the video number G-2 check that out
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.
Same doubt. if we're storing an array at each index of the vector, shouldn't it be vector adj instead of vectoradj??
@@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
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... ❤
BEST DSA TEACHER FOR ME
Thank you so much stiver. Happy Teachers dayy
here we go !
how can someone be so perfect in explianing concept
Awesome Space & Time Analysis 🔥🔥🔥🔥🔥🔥🔥🔥
"UNDERSTOOD BHAIYA!!"
My favourite algorithm so far, Breast First Search
complexity : O(V + 2E)
let say,
adjacency list :
1 - {2,3}
2 - {1,4,5,6}
3 - {1,7,8}
4 - {2}
5 - {2}
6 - {2}
7 - {3}
8 - {3}
for node 1, way = 2
for node 2, way = 4
for node 3, way = 3
for node,4 way = 1
for node 5, way = 1
for node 6, way = 1
for node 7, way = 1
for node 8 , way = 1
total way = 2 + 4 + 3 + 1 + 1 + 1 + 1 +1 = 14
Node = 8
total = 14 + 8 = 22
where, O(V + 2E)
V = 8
E = 7
total = 8 + 2*7 = 22
O(V + 2E) = 22
please also explain space and time complexities
Understood, Happy Learning🤗
9:39 ASMR moments
5/56 done(3.12.22)
congrats bhaiya for 300k
ek din apan sath me 1m jayenge
Thankyou striver bhaiya! ❤️
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).
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
Nice and crystal clear explanation !!
a well explained and organised lecture !!!
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Understood! Awesome explanation as always, thank you so much!
17:03 i see what you did there 🤣🤣
no one commented on this :(
you are the best stiver
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..??
very well explained with all the minute details
Liked the video, notes taken, understood
14:30 program starts
what if the graph have different components?
the solution seems to solve the connected components only.
You are amazing striver ❣️
brilliantly explain thanks sir and neeed complete playlist of DSA from you for cracking google like companies
i loved it sir , what a beautiful explanation
understood!! Explained beautifully!!
crystal clear.. excellent explanantion
Ohoo masthhh bhaiyaaaa Woohoo
great content loving this after completing dp series💙💛💙
hats off to ur hard work.
Telugu people attendance❤
Thank you, Striver
understood
Thank you sir
made it simple to understand
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.
Understood bhaiya!
Fantastic 🎉 Understood
Wonderful bhaiya.....
Great explanation
Understood. Thanks a lot.
Great series
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 :)
ya no issue ... just taking int as it would help with weighted graphs as well and generalize the approach
love you from bangladesh
Thanks sir .... best solutions
Understood Bhaiya
Understood..next please ✌🏻
What an amazing explanation! Understood! 🤩❤🔥
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?
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 )
@@IITiansgreat
Understood Sir, Thank you very much
Thankuu sooo muchhh broooo🤗🤗🤗❤❤❤❤❤
Thanks Bhaiya
Understood, Sire!
UNDERSTOOD!
Thank you very much. You are a genius.
understood very well...
Interesting that you have to set 0 as visited missed that when I first tried it!
Thank you so much.
Great work. Thanks for doing this.
Woah nice explanation
all clear thank u bro
Wont Time Complexity be O(n*2E)?? Since for each node n we are traversing 2E
But once you have travelled for all nodes, all are visited, you won’t again traverse na. Overall you will travel everyone once only
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!
@@CuriousAnonDev thanks for indepth explaination !
@@CuriousAnonDev naam dekh kar mai bhi atak gaya
thx striver. Understood.
striver you didn't explained why it would work for a directed graph
thanks Raj
understood
thankyou very much
Thank you, understood!
Thankyou striver!
just thank you 🙏
Great Content
brilliant explanation!