Hi, the topic is breadth first search and depth first search. In this video I'll cover these two traversal methods by taking various examples. Breadth first search and depth first search are graph traversal methods.
So we'll understand quickly the difference between them through this small example. Then afterward I'll take another example and I will explain you in detail. Now for quick understanding I have taken a simple graph actually it's a tree but a tree is also a graph.
So let us see. So for traversal both of these traversal we have to know these two terms. Now for understanding these traversals we should know two terms. One is visiting a vertex means going on a particular vertex. Second term is exploration of vertex.
Exploration means if I am on some particular vertex then visiting all its adjacent vertices is called as exploration. So based on these two terms we can understand traversals. So first I will explain you breadth first search. See I am selecting vertex 1 as the starting vertex to find out breadth first search.
You can select any vertex as a starting vertex. Now vertex 1, I will visit the vertex 1. Now once the vertex is visited this vertex I will start exploring means I will visit all adjacent vertices. So who are those? 5, 4 and 2. In which order I can visit?
I can visit them in any order. So I will take 2 first then 4 then 5. Next I should select the next vertex for exploration. So these are already visited vertices.
After one I have visited 2, 4, 5. Then I should explore. Explore what? I will explore 2. So who are adjacent to 2?
Adjacent to 2 are 7, 6, 3. In which order you can take? You can take them in any order. 7, then 3, then 6. In any order you can take.
That's all. All the vertices are visited and there is no vertex remaining for exploration. This is breadth-first search.
Now let us look at depth first search. I will start from vertex 1. Then from 1, I have to start its exploration. So I will go to vertex 2. Now who are other adjacent vertices 4 and 5?
No, don't visit them. You have reached a new vertex. So you start exploring that vertex.
Okay, I will start exploring 2. Then who are adjacent? to this 7, 6 and 3 so I want to go to 3 ok go to 3 then shall I visit 6 and 7 also no this is depth first search start exploring 3 so if I start exploring 3 there is nothing connected to 3 ok so it means 3 is completely explored then come back and then continue the exploration of 2 so who are there 6 explore 6 nothing is there come back go to 7 explore 7 visit 7 explore 7 there is nothing so come back to 1 now and continue the exploration of 1 who are adjacent to it 4 visit 4 and explore 4 there is nothing come back then go to 5 5 now in this way all are explored so the traversals are different results are different. So in breadth first search we will explore a vertex then we go to the next vertex for exploration. But in depth first search once we started exploring once we visited a new vertex we will suspend this vertex and start its exploration. So from one we got two so we started exploring two then from two we went on three so we'll start exploring three like this.
So in depth first search approach is different and breadth first search approach is different. different. So I will take one more example and explain you what is the difference between breadth first search and depth first search with a simple example.
One more example. Let us find breadth first search. Actually this is a binary tree.
Tree is also a graph. So let us perform breadth first search and see. So as per binary tree I will perform level order 1 then 2 3 Then 4, 5, 6, 7. 4, 5, 6, 7. This is breadth-first search. Means breadth-first search is just like a level order on a binary tree. Then what is a depth-first search?
Visit 1. Okay. Explore 1. So we got 2. So stop exploring 1 and start exploring 2. So 4. Stop exploring 2 and continue exploration of 4. There is nothing. So go back. and come to 5. Now nothing is remaining. So go back to 1 and come on this side.
Then 6, then go back and 7. So this is like pre-order. So breadth first search is just like level order and depth first search is just like pre-order traversal of a graph. I have taken a bigger graph now.
We will learn about breadth-first search and depth-first search in detail. First of all, breadth-first search. For performing breadth-first search, I will take one data structure that is Q.
I have taken a Q. Now I will explain you initial step then I will explain you repeating step. So what is the initial step? Start exploration from any one of the vertex. So which vertex I should select as a starting vertex for breadth-for-search?
You can select any vertex you like. So I will select vertex 1. So in the answer you show it 1, in the graph you draw here again then add it to Q. This is the first step, initial step. Now we will perform repeating steps.
So what are those repeating steps? Take out a vertex from Q and start exploring it. So vertex 1, who are adjacent to 1? 4 and 2. So explore them.
So first I want to visit 4. Okay, add it to result and also add it to Q. Next I want to go to 2. Okay, add it to result and also add it to Q. Now 1 is completely explored.
There is no adjacent vertex remaining for vertex 1. This is for search. iteration completed. Now repeat the procedure.
What to do next? Select next vertex for exploration from Q that is 4. Start exploring 4. So who is adjacent to 4? 3. So I am drawing it like a tree here.
So 3 is adjacent. So add it to Q. Any other adjacent for 4? Nothing is adjacent for 4. So 4 is completely explored. Now select next vertex for exploration that is 2. Who are adjacent to to 2, 3, 5, 7, 8. I can visit them in any order if I check 3 it's already explored so then I will prefer going on 5 first so 5, 5. Next I want to go on 8. 8, so 8 and 8. Next I will go on 7, so 7 and add 7 here.
Now 2 is completely explored. Now select next vertex for exploration. Who is that? 3. Is there any adjustment vertices for 3?
Yes, 2, 8, 9 and 10. So 2 is already visited. So first I will take 10, 10, 10. And then 9. 9 added to queue completed 3 is completely explored now select next vertex for exploration 5 anybody adjacent to 5 yes 8 and 7 and 6 so 8 already visited 7 already visited 6. This is 6. So 6 and 6. 5 is completely explored. Select the next vertex for exploration. 8. Who is adjacent to 8? 2 and 7. 2 actually we came from there 7 draw a dotted line so vertex which is already visited we are drawing a dotted line then next vertex for exploration 7 7 is already explored so is there anything remaining for 7 no 10 there is nothing nearer to 10 no nothing adjacent to 10 there is nothing as adjacent to 9 and there is nothing adjacent to 6 so that's all this is breadth first search completed and the tree that we got here is breadth-first search spanning tree.
Dotted edges that we got here they are called as cross edges. They are called as cross edges. Let us see what are the things that we have learned. First thing is you can start breadth-first search from any vertex you like. First point.
Second thing is when you are exploring any vertex, one, then you can visit this adjacent vertices in any order you like. This was the second thing. Then both are leniency is given, freedom is given to select any vertex. Then what is the rule here? Rule is when you are selecting a vertex for exploration, you must visit all its adjacent vertices.
Then only you should go to next vertex. For exploration, so if I am exploring one then I should visit four as well as two then only I should select four for exploration. this is the rule the next thing is last thing is you should select the next vertex for exploration from a queue only so queue and exploration should be completely done these are the two important points about breadth first search follow this one then you can get many answers I will write few more valid breadth first searches here First one, I will start from vertex 1 then I will explore the adjacent vertices.
So first I will explore 2 then 4. Then I have to start exploring 2 because I have visited 2 first. So who are adjacent to 2? So I will take 8 then 5 then 7 then 3 these are adjacent to 2 all these are adjacent to 2 then I should explore which one 4 so who are adjacent to 4 3 is already over then explore 8 who is adjacent to 8 5 and 7 both are visited now explore 7 So this is 6. Now explore 3. So 10 and 9. So 10 and 9. This one is also a valid answer. Then one more.
I will start exploration from 5. From 5 who are adjacent to 8, 7 and 6. Now explore 2. Who are adjacent to 2, 3 and 1. Now explore 8. 7 is already visited. 7. 7 everything is visited 6 nothing is there so everything is visited explore 3 so 9 and 10 and 4 so for 3 9 10 and 4 I have visited now explore 1 nothing is remaining 9 10 4 all are visited so this is also valid so like this you can start from any vertex and you can visit the adjacent in any order so you can form numerous number of valid breadth first search. Next we will see depth first search. Now next is depth first search. For this I will take a stack.
Stack is a data structure used here. Let us start. I can start the traversal from any vertex I like.
So I want to start from vertex 1. So 1 is visited. This is the initial step. Now the repeating step.
What I have to do every time. As this new vertex is visited start exploring it. So who are adjacent to that 4 and 2. So visit Now the rule in depth first search is once you have visited one vertex, still one more is remaining. Leave that.
We will see it afterwards. First you start exploring 4. So this is the rule. Once you have reached a new vertex, start exploring that new vertex.
What about that one? Suspend it and keep it in the step so that we can explore it later. Now, start exploring 4. So, from 4, I can go on 3. So, okay, go to 3. 3. is visited. Now what to do?
Suspend 4 and start exploring 3. From 3 I can go on 10. So 10. Suspend 3 start exploring 10. There is no adjacent vertex of 10. So go back to 3. So how to know where I have to go back? This stack will give me their value. So this 3. Continue exploring 3. So I can go on 9. 9. And again suspend 3 and start exploring 9. From 9 I cannot go anywhere.
Then go back to 3 and start exploring 3. So who is adjacent to 3? 2. So 2 is visited. Then from 2 who is adjacent?
Suspend 2 and start exploring 2. So from 2 8 is adjacent. So take 8. Now start exploring 8. So from there I can go on 7. So suspend 8. So 7 is visited. Now we have to explore 7. From 7 I can go on 5. So 5 is newly visited.
Now we have to start exploring 5. So suspend 7 and push it into the stack. stack then from 5 who is adjacent 6 so visit 6 suspend 5 and continue exploration of 6 there is nothing adjacent to 6 so go back to 5 from 5 where i can go further so i can visit 2 which is already completed right i can visit 8 which is already completed So there is nothing remaining for 5. So what happens in this way is we are going deep and deep. Right.
So in this way, almost all vertices are visited only. They are completely explored. So 5 is completely explored.
Go back to the previous word. Who is that? 7. From 7 where I can go?
From 7 I can go on 2 which is already visited. Then go back to 8. From 8 nothing is remaining. So from 2 where I can go? I can go to 1. Right? Then nothing is remaining.
So go back to 4. From 4 I cannot go anywhere. From 3, 1 I cannot visit anywhere. So that's all right so here is the depth first search traversal result and this is a DFS spanning tree this is depth first search spanning tree and these edges are called as back edges.
So for this graph we can make a tree like and perform pre-order. So this is the pre-order of this tree. See 1, 4, 3, 10, then 9, then 2, 8, 7, 5, 6. 1, 4, 3, 9, 8, 2. So 9, 2, 8, 7, 5, 6. So this is like pre-order traversal.
Now I will write few more valid depth first search directly looking into the graph. I'll start from vertex 1. 1. This is the first one. From 1 I'll go to 2. From 2 I'll go to 8. From 8 I will go to 7. From 7 I'll go to 5. Then 6. From 6 I cannot go anywhere.
come back to 5, 2 is already completed, 7 also completed so what was the root I have taken, so come back to 7, 7 is completely explored, come back to 8, nothing remaining, come back to 2, so from 2 I will go to 3, then 9, nothing is there come back and go to 10, then go back to 3 and go to 4, then 1 is already explored, so return back to 4, then 3, then 2, then 1, finished So this is one answer. Then one more I'll show. I'll start from vertex 3. First is 3. Then I'll visit to 4. Then 1. Then 2. Then 5. Then 6. From 6 I cannot go anywhere. Come back to 5. Come back to 5. and go to 7, then 8. Right? From 8, I am back on 2, but it's already over.
So, complete, go back to 7, then 5, then come back to 2, then 2. From there, I have already gone to 1. 1 is is already completed right. So come back to 4 then come back to 3. So from 3 who are remaining? 10 and 9. So 10 then 9. This is also valid. So you can start from any vertex you like and you can visit any neighboring vertex.
But only thing is once you have visited a new vertex, suspend the exploration of current vertex and start exploring new vertex. That's all about deferred search and breadth first search and the time complexity of both these methods is order of n. n is number of vertices.