BFS & DFS | Breadth First Search | Depth First Search | Graph Traversing | DAA

BFS & DFS | Breadth First Search | Depth First Search | Graph Traversing | DAA

BFS & DFS | Breadth First Search | Depth First Search | Graph Traversing | DAA

👉Subscribe to our new channel:   / @varunainashots  

👉Links for DAA Notes:

đź”—File-1: https://rb.gy/2byrg
🧑‍🎓Contributed by: Junaid Gazi

đź”—File-2: https://rb.gy/gibu5
🧑‍🎓Contributed by: Mannu Garg

Introduction to Graph traversal
* The process of visiting and exploring a graph for processing is called graph traversal.
* Breadth First Search(BFS)
* Depth First Search(DFS)

â–şDesign and Analysis of algorithms (DAA) (Complete Playlist):
   • Design and Analysis of algorithms (DAA)  

Other subject-wise playlist Links:
--------------------------------------------------------------------------------------------------------------------------------------
â–ş Operating System :
   • Operating System (Complete Playlist)  
â–şDatabase Management System:
   • DBMS (Database Management system) Com…  
â–ş Theory of Computation
   • TOC(Theory of Computation)  
â–şArtificial Intelligence:
   • Artificial Intelligence (Complete Pla…  
â–şComputer Networks (Complete Playlist):
   • Computer Networks (Complete Playlist)  
â–şComputer Architecture (Complete Playlist):
   • Computer Organization and Architectur…  
â–şStructured Query Language (SQL):
   • Structured Query Language (SQL)  
â–şDiscrete Mathematics:
   • Discrete Mathematics  
â–şCompiler Design:
   • Compiler Design (Complete Playlist)  
â–şNumber System:
   • Number system  
â–şCloud Computing \u0026 BIG Data:
   • Cloud Computing \u0026 BIG Data  
â–şSoftware Engineering:
   • Software Engineering  
â–şData Structure:
   • Data Structure  
â–şGraph Theory:
   • Graph Theory  
â–şProgramming in C:
   • C Programming  
â–şDigital Logic:
   • Digital Logic(Complete Playlist)  

---------------------------------------------------------------------------------------------------------------------------------------
Our social media Links:
► Subscribe to us on YouTube:    / gatesmashers  
►Subscribe to our new channel:    / @varunainashots  
â–ş Like our page on Facebook: https://www.facebook.com/gatesmashers
â–ş Follow us on Instagram: https://www.instagram.com/gate.smashers
â–ş Follow us on Instagram: https://www.instagram.com/varunainashots
â–ş Follow us on Telegram: https://t.me/gatesmashersofficial
â–ş Follow us on Threads: https://www.threads.net/@gate.smashers
--------------------------------------------------------------------------------------------------------------------------------------
â–şFor Any Query, Suggestion or notes contribution:
Email us at: [email protected]
#breadthfirstsearch #depthfirstsearch #algorithm


Content

0 -> Dear students, welcome to Gate Smashers
2.02 -> In this video I am going to explain
3.54 -> Graph Traversal Methods
5.36 -> In which we have two most important methods
7.78 -> Breath First Search i.e. BFS
9.8 -> and Depth First Search i.e. DFS
12.82 -> If we talk about these two methods
15.84 -> then these two methods are very important
18.36 -> from your placement point of view
20.38 -> and from your competitive exams point of view
22.4 -> So I will explain these two methods
24.42 -> with real life examples and the easiest way
28.42 -> So guys like the video and subscribe the channel
30.44 -> If you haven't done it yet
32.46 -> then you can subscribe with other devices
34.48 -> Subscriber is very important
36.5 -> So let's start
37.52 -> First of all what is the definition of graph traversal?
40.54 -> The process of visiting and exploring
43.56 -> A graph for processing is called a graph traversal
47.58 -> You can talk about graph traversal
49.6 -> You can also talk about tree traversal
51.62 -> because every graph is a tree
53.64 -> But tree may or may not be a graph
55.66 -> But every graph is what a tree
57.66 -> Because in a graph, cycle is allowed but not in a tree
61.68 -> So graph is a big term
62.699 -> So here we are focusing on two main things
66.72 -> One is visiting our vertex
69.74 -> and second is exploring our vertex
72.759 -> Means in a graph you know that vertex is edges
76.78 -> Now what I have to do is
78.8 -> I will do two things here
80.82 -> One is visit
81.84 -> Visit means reaching that vertex
85.84 -> When I reached that vertex
87.86 -> Now what I have to do is explore
89.88 -> Explore means who is it connected with?
92.9 -> Who are its neighbors?
94.42 -> So these two things are your main things
96.44 -> So here we see these two things one by one
98.96 -> So first of all if we talk about
101.98 -> What is the basic difference between breadth for search and depth for search?
105.5 -> Breadth means this way
107.52 -> Means what does it do?
108.54 -> It follows all the levels one by one
111.06 -> If I talk about the diagram
112.08 -> Like a tree is made here because I have already told you
114.58 -> Every tree is a graph so you can take this too
117.6 -> So here if we talk about breadth for search
120.62 -> So how does it work?
122.64 -> It works breadth wise
124.66 -> Like this
125.679 -> And then one by one it covers the level
129.699 -> So remember
130.72 -> It will cover one level first
132.74 -> When that level is complete
134.76 -> Then it will go to the second level
137.78 -> And depth for search means towards depth
140.8 -> Means you have to go towards depth down
142.8 -> So if we talk about depth for search
144.82 -> So we walk like this
146.84 -> If we start walking from here
148.86 -> Then go in one direction
150.88 -> Then go down again
152.9 -> Then go down again
153.92 -> Means depth wise
154.94 -> Till I get the way I will keep walking
157.96 -> When I didn't get the way
159.98 -> I didn't get the way ahead of this
161.5 -> Then what do I do?
163.02 -> I backtrack
164.04 -> Then I go back to the last node
166.06 -> So backtracking is in DFS
168.58 -> There is no backtracking in BFS
170.6 -> It goes one by one like this
172.6 -> If we talk about example
174.62 -> So if you want to understand DFS
176.64 -> So the fund is simple
178.66 -> Like we took non medical of plus 2
180.68 -> After that I know I chose path
183.7 -> Let's say B.Tech CSE
185.72 -> After that I know what I did next
187.74 -> Let's say I selected a job of software engineering
190.26 -> So I am going in one direction
192.28 -> Although in plus 2 along with non medical
194.299 -> You had commerce and arts too
197.32 -> If we talk about B.Tech CSE
199.34 -> You could have done MBA too
201.34 -> You could have done UPSE too
202.86 -> There are many options
203.88 -> But I am going in one direction
205.9 -> And when I feel dead end has come
207.92 -> Then what do I do?
209.44 -> I backtrack
210.46 -> So this is the simple story
211.98 -> And if we want to understand BFS
215 -> Then its simple example is Marys
217.02 -> This is an example of Marys
218.54 -> Means if you go to Marys
219.56 -> At the food stall
220.58 -> So there you don't go in one direction
222.6 -> What we do there
223.62 -> First at one stall
225.14 -> Means first go to the snacks one
226.16 -> Completed that
227.68 -> Then the snacks of Golgappay
229.7 -> Completed that
230.7 -> When that is over
231.72 -> Then go to the food stall
233.239 -> Then in the food stall also
234.26 -> Explore all the options
236.28 -> So what we do there
237.299 -> We are going breadth wise
238.82 -> Rather than depth wise
239.839 -> That I am eating only one thing
241.359 -> And I am not getting full from that
242.88 -> We go there breadth wise
245.399 -> So as an example I am explaining you
247.42 -> That there we go breadth wise
249.44 -> And here we work depth wise like this
251.459 -> This is the main difference
252.98 -> So that's why BFS
255 -> Is called level by level or level ordering
257.519 -> Because when one level is over
259.519 -> Then only we go to the other level
261.539 -> There is no such thing in DFS
263.06 -> In DFS you go in depth
265.08 -> And now we
266.099 -> Here with one more example
268.12 -> I will show you in action
269.64 -> That if I want to write BFS
271.159 -> Then how do I write it?
272.88 -> Ok?
273.4 -> If I want to write the order here
274.919 -> Of BFS then how do I write it?
276.419 -> So see you can start from any node
278.44 -> There is no such problem that
279.96 -> You have to start from this
281.479 -> You can start from any node
283 -> So let's say I start from 1
285.02 -> Ok?
286.039 -> So here which data structure we use
288.04 -> Here we use Queue data structure
291.06 -> First in first out
292.58 -> So the first visit I did
294.6 -> I kept that
296.12 -> Someone will visit, right?
297.14 -> They will start from somewhere
298.16 -> There will be no source of their own
299.68 -> So our source is 1
301.7 -> So we started from 1
303.72 -> Now we started from 1
305.24 -> Now what am I doing?
306.26 -> Means I visited 1
307.78 -> So now take it out
309.8 -> Now explore it
311.82 -> Explore means
313.34 -> Who is connected with it?
314.86 -> Who is connected? 2 and 3
316.38 -> You can write in any order
317.88 -> Whether you write 2 first or 3 first
319.9 -> It doesn't matter
321.42 -> That's why the BFS that you will get
323.44 -> They can also be multiple
325.46 -> It's not just unique
326.98 -> They can also be multiple
328.5 -> So I explored it
330.02 -> Now I reached to whom?
331.04 -> Let's say I reached to 2
332.56 -> Now I will explore 2
334.58 -> Who is connected with 2?
336.1 -> 2 is connected with 4
337.32 -> So whatever is connected
338.84 -> Keep putting it in Queue
340.36 -> And first in first out
341.38 -> Keep putting it in Queue
342.4 -> Keep taking it out from the front
343.42 -> Keep putting it from the rear
344.94 -> So which is next? 3
346.44 -> Explore 3
348.26 -> Who is connected with 3? 4 and 7
350.28 -> 4 is already put in
352.3 -> 7 is put in from the back
354.32 -> Now next is 4
356.34 -> Which is next? 4
357.86 -> So explore 4
359.38 -> Who is connected with 4?
360.9 -> 5 and 6
362.42 -> So whatever is connected
363.94 -> Keep putting it in
365.46 -> Next which is next? 7
367.48 -> Take out 7 and explore it
370.5 -> When we explored it
372.02 -> No one is connected with it
373.54 -> So leave it
375.04 -> Take out 5 and explore it
377.06 -> No one is connected with it
378.58 -> If it was there, we would have put it in Q
380.1 -> But it's okay
381.12 -> After that take out 6 and explore it
383.14 -> No one is connected with it
384.66 -> So this is your final BFS traversal
386.68 -> Which will be written like this
389.2 -> But it can also be multiple
390.72 -> Like I put 2, 3
392.22 -> If you put 3, 2, it will come out
393.74 -> Similarly I put 5, 6
395.26 -> If you put 6, 5, it will come out
396.78 -> The main thing is to understand it
398.8 -> To understand its working
400.32 -> So this is level by level
401.84 -> See first we did 1
403.36 -> After that 2, 3
404.86 -> Covered 2, 3
406.18 -> Then see here 4, 7
408.2 -> See 4, 7 were at one level
409.72 -> Then after that 5, 6
411.24 -> 5, 6 at one level
412.26 -> So level by level
413.78 -> It works like this
415.8 -> Okay?
416.82 -> Now comes your DFS
418.84 -> So in DFS
420.86 -> We use our data structure
425.86 -> That is stack
427.88 -> Now stack is last in first out based
430.9 -> So here also we can start with any node
432.9 -> Let's say I start with 1
434.919 -> So I started with 1
436.94 -> So first we visited 1
438.96 -> Now after visiting 1
440.979 -> What I am doing?
443 -> I am exploring
444.02 -> So I have 2 options
445.039 -> 2 is there and 3 is also there
446.56 -> But you have to go to any one place
448.58 -> So let's say I go to 2
450.599 -> So what happened here?
452.12 -> I am going from 1 to 2
453.64 -> Here I will go in depth
455.659 -> So when I went from 1 to 2
457.679 -> So I went from 1 to 2
459.7 -> So what happened to 1?
461.7 -> It got suspended, inactive
463.719 -> Okay?
464.74 -> So what did we do to it?
465.76 -> We put it in the stack
467.78 -> Now we are on 2
468.8 -> I will go from 2 to 4
470.82 -> What is the option from 2?
471.84 -> There is an option to go to 4
473.86 -> So you go and suspend 2 in a way
476.88 -> Because you went from 2 to 4
478.9 -> Now you are standing on 4
479.919 -> So you put 2 in it
481.94 -> From 4
482.96 -> You have option 5 or 6
484.98 -> But you will go to any one
486.5 -> See you are going in depth
488.52 -> So you went to 5
490.02 -> When you went to 5
492.039 -> So you suspended 4 in a way
494.56 -> Okay?
495.58 -> After 5 you don't have any option
498.599 -> So after 5 you don't have any option
500.62 -> So what I said was
501.64 -> We backtrack
502.659 -> We see if there is any other path for me
504.68 -> We have to backtrack only
506.7 -> We have to jump only
507.719 -> When you don't have any option left
510.74 -> We backtrack only when there is no option left
512.76 -> If there is an option
513.78 -> Then we don't backtrack
514.799 -> But there is no option here
516.819 -> So now what we will do is backtrack
518.82 -> Means from 5 to 4
520.84 -> But how do I know that going from 5 to 4
522.86 -> Will help stack
524.88 -> Here the last inactive was 4
527.9 -> So obviously last in first out
529.92 -> So from 4 we got to know
531.94 -> That in last we went to 4
533.96 -> So from 4 we got back
535.98 -> And from 4 what option I have?
538 -> 6 option is there
539.02 -> So from 4 where did I go?
541.04 -> I went to 6
542.56 -> From 4 where did I go?
543.58 -> I went to 6
544.6 -> So what happened to 4?
545.62 -> It got suspended
546.64 -> So put it again
547.64 -> We put 6 in this
549.66 -> In the sequence that will be made
551.18 -> From 4 I went to 6
552.699 -> So I suspended 4
554.22 -> So again I came to this
555.74 -> Now there is no option from 6
557.76 -> Now there is no option from 6
559.78 -> So what I will do is
561.3 -> I will backtrack again from 6
562.819 -> How do I know where I was last?
564.84 -> Check again last
566.36 -> I was on 4
567.38 -> Now again I came back to 4 and stood
569.9 -> Now see if there is any option
571.92 -> Yes from 4 I can go to 3
573.939 -> Because 2 is done
574.96 -> So from 4 I went to 3
577.46 -> So from 4 I went to 3
579.48 -> Now 4 again got suspended
581.5 -> Put it again in one way
583.52 -> Because from 4 you went to 3
585.54 -> So write in sequence
586.56 -> And with it suspend 4
588.58 -> Now is there any other option from 3?
590.6 -> Yes there is an option from 3 to 7
592.62 -> So what happened to 3?
594.14 -> It got suspended
595.16 -> So put the suspended one
596.68 -> Put it in the stack
598.2 -> Ok, we reached 7
599.72 -> Now what to do?
600.74 -> Is there any option after 7?
602.26 -> There is no option
603.28 -> So what I will do is
604.3 -> I will backtrack
605.32 -> How do I know backtrack?
606.82 -> Is there any option after 7?
608.64 -> This is visible in the diagram
610.16 -> But what does the algorithm say?
611.68 -> Algorithm says that you check this
613.2 -> So I took it out from this
614.22 -> I reached 3
615.24 -> After 3 is there any other option?
617.26 -> There is no other option
618.78 -> So obviously I am on 4
620.3 -> Is there any new option from 4?
621.82 -> No
622.84 -> Then I reached 2
624.36 -> Is there any other option from 2?
625.88 -> No
626.9 -> So I reached 1
627.92 -> So your final sequence is ready
630.94 -> So what are we doing here?
632.46 -> We are going depthwise
633.98 -> There we are going breadthwise
635.48 -> So both have the same time complexity
638 -> Order of V plus E
639.52 -> Because what are we doing?
640.74 -> We are traversing all the vertex and edges
644.76 -> So what can be the maximum?
646.28 -> Order of V plus E
648 -> Total number of vertex and total number of edges
650.32 -> So the difference between the story of both is very important
654.34 -> Because their real life applications are very high
656.86 -> Talk about web crawlers
658.38 -> Talk about social media, Facebook etc.
660.6 -> Talk about networking
662.32 -> You have to check whether there is a cycle in the graph or not
664.82 -> You have to check minimum cost spending tree
667.34 -> So in all those things you use the technique of DFS and BFS
671.36 -> There are many real life applications for this
674.182 -> Thank You.

Source: https://www.youtube.com/watch?v=N2P7w22tN9c