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

Find DSA, LLD, OOPs, Core Subjects, 1000+ Premium Questions company wise, Aptitude, SQL, AI doubt support and many other features that will help you to stay focussed inside one platform under one affordable subscription. Have a hassle free one stop solution for up-skilling and preparing.

Checkout the problem link 👇🏼
Breadth-First Search (BFS) | C++ and Java | Traversal Technique in Graphs

[takeUforward]

Hi, hope you are well.


Find DSA, LLD, OOPs, Core Subjects, 1000+ Premium Questions company wise, Aptitude, SQL and many other time saving features under one affordable subscription. Have a hassle free one stop solution for up-skilling and preparing yourself.

[UECSoumyaRay]

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

[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).

[takeUforward]

Let's continue the habit of commenting “understood” if you got the entire video.

Do follow me on Instagram: striver_79

[gourabbhattacharjee]

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

[chitrankusarkar]

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

[creativearts]

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

[nkgautam]

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🙏🙏🙏

[priyadarsinipaikaray]

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

[arthurdark]

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.

[YCCMdigo]

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

[asadeducation]

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

[lavanyaan]

Understood. Thank you so much for your video 🙏🙏🙏

[sreejitkar]

Never seen a hardworking guy like this

[FakePersonNone]

Never seen someone explain better than you man thank you so much!

[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 )

[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.

[tharaniarumugam-zbil]

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

[multiverseofcomputerscience]

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

[Mainak_Dasgupta]

class Solution {
public:
// Function to return Breadth First Traversal of given graph.
vector<int> bfs(vector<vector<int>> &adj) {
int n = adj.size();
bool vis[n] = {0};
vis[0] = 1;
queue<int> q;
q.push(0);
vector<int> bfs;

while(!q.empty()){
int node = q.front();
q.pop();
bfs.push_back(node);

for(auto it : adj[node]){
if(!vis[it]){
vis[it] = 1;
q.push(it);
}
}
}
return bfs;
}
};
for anyone who need it (in c++)