1
00:00:00,860 --> 00:00:01,820
Hi everyone.

2
00:00:01,820 --> 00:00:09,140
In this question, let's try to learn how to implement a breadth first search or breadth first traversal

3
00:00:09,140 --> 00:00:09,980
in a graph.

4
00:00:09,980 --> 00:00:11,420
Let's read the question.

5
00:00:11,420 --> 00:00:18,290
You are given an undirected graph stored as an adjacency list in the first case, and as an adjacency

6
00:00:18,290 --> 00:00:19,820
matrix in the second case.

7
00:00:19,820 --> 00:00:25,280
Write functions to traverse this graph using the breadth first search approach.

8
00:00:25,280 --> 00:00:31,280
As you traverse the graph, store the values of the vertices in an array and return this array.

9
00:00:31,280 --> 00:00:37,340
So over here we are implementing the BFS or breadth first traversal approach for a graph.

10
00:00:37,340 --> 00:00:43,730
Now there are two cases we have seen in the previous videos that we can store a graph either as an adjacency

11
00:00:43,730 --> 00:00:45,950
list or as an adjacency matrix.

12
00:00:45,950 --> 00:00:48,290
Now we are going to do both the cases over here.

13
00:00:48,290 --> 00:00:53,510
We are going to implement BFS first when the graph is stored as an adjacency list.

14
00:00:53,510 --> 00:00:58,490
And second we are going to implement BFS when the graph is stored as an adjacency matrix.

15
00:00:58,490 --> 00:01:02,060
Now we have already seen BFS in the case of a binary tree.

16
00:01:02,060 --> 00:01:06,980
Now the logic or the algorithm is going to be pretty similar to what we have seen over there.

17
00:01:06,980 --> 00:01:08,270
Let's get started.

18
00:01:08,840 --> 00:01:11,690
Let's say this is the graph which is given to us.

19
00:01:11,690 --> 00:01:18,200
Now if we represent this graph as or store this graph as an adjacency list, it would look like this.

20
00:01:18,200 --> 00:01:18,380
Right?

21
00:01:18,380 --> 00:01:20,000
We have already seen how to do that.

22
00:01:20,000 --> 00:01:24,740
So we have these six nodes A, B, C, D, e and f.

23
00:01:24,740 --> 00:01:29,660
And we are just storing the neighbors of that particular node as an array over here.

24
00:01:29,660 --> 00:01:32,450
So the neighbors for node A or b and f.

25
00:01:32,450 --> 00:01:34,430
That's why we have b and F over here.

26
00:01:34,430 --> 00:01:40,790
And because we are dealing with an undirected graph you can see that you have this link a to b in B

27
00:01:40,790 --> 00:01:41,030
also.

28
00:01:41,030 --> 00:01:41,210
Right.

29
00:01:41,210 --> 00:01:44,120
So over here you have A as a neighbor of B as well.

30
00:01:44,120 --> 00:01:47,360
That's because we have we are dealing over here with an undirected graph.

31
00:01:47,360 --> 00:01:53,150
Now if it was a directed graph we have seen before, in that case we would not have this type of link,

32
00:01:53,150 --> 00:01:53,300
right?

33
00:01:53,300 --> 00:01:57,710
For example, if the link was from A to B, then we only have B over here.

34
00:01:57,710 --> 00:01:59,090
We wouldn't have A over here.

35
00:01:59,090 --> 00:01:59,600
All right.

36
00:01:59,600 --> 00:02:00,530
So let's proceed.

37
00:02:00,530 --> 00:02:05,210
So we have this graph and this is the adjacency list which stores this graph.

38
00:02:05,210 --> 00:02:08,660
Now first let's try to understand BFS again.

39
00:02:08,660 --> 00:02:10,670
For this I am just modifying this link.

40
00:02:10,670 --> 00:02:15,170
I'm removing this link over here so that we can understand the meaning of BFS better.

41
00:02:15,170 --> 00:02:15,590
All right.

42
00:02:15,590 --> 00:02:23,000
So this is the graph which we have now when it comes to breadth first search or breadth first traversal.

43
00:02:23,000 --> 00:02:28,910
The idea is that we have to visit neighbors of a node before we visit children of a node.

44
00:02:28,910 --> 00:02:31,280
So let's say we start at node A.

45
00:02:31,280 --> 00:02:34,250
And this is a difference between the case of a binary tree.

46
00:02:34,250 --> 00:02:37,040
There we already have a root and we just start from the root.

47
00:02:37,040 --> 00:02:42,050
But over here in the case of a graph, we have to mention from where we want to start the traversal.

48
00:02:42,080 --> 00:02:45,080
Now let's say we are starting from this node over here.

49
00:02:45,080 --> 00:02:46,850
So we are starting from a.

50
00:02:46,880 --> 00:02:48,980
Now again let's read this.

51
00:02:48,980 --> 00:02:51,980
We have to visit the neighbors first before the children.

52
00:02:51,980 --> 00:02:52,340
All right.

53
00:02:52,340 --> 00:02:54,350
So over here A does not have any neighbors.

54
00:02:54,350 --> 00:02:56,750
So let's go ahead and look at its children.

55
00:02:56,750 --> 00:02:58,040
We have B and F.

56
00:02:58,040 --> 00:02:58,460
All right.

57
00:02:58,460 --> 00:03:04,250
So again we also in this question we want to print the uh values of the graph.

58
00:03:04,250 --> 00:03:04,430
Right.

59
00:03:04,430 --> 00:03:05,690
So we have visited a.

60
00:03:05,690 --> 00:03:10,850
So let's just store it somewhere else so we can see the way we are traversing the graph.

61
00:03:10,850 --> 00:03:12,740
Also this will be helpful in that respect.

62
00:03:12,740 --> 00:03:16,130
So after we have visited a we go to the next level.

63
00:03:16,130 --> 00:03:19,220
So you can see that the the children of A or B and F.

64
00:03:19,220 --> 00:03:22,580
So we will visit these two nodes after we visit A.

65
00:03:22,580 --> 00:03:24,140
So we have b and f.

66
00:03:24,140 --> 00:03:28,520
Now again how does this apply to visiting neighbors before visiting children.

67
00:03:28,520 --> 00:03:32,090
Now after we have visited B, we could have gone to C, right?

68
00:03:32,090 --> 00:03:36,950
Which is a child of B, but before we visit this child, we have to visit neighbors.

69
00:03:36,950 --> 00:03:39,770
And that's why after B we have F over here.

70
00:03:39,770 --> 00:03:43,340
Now once B and F are done, now we go to the children.

71
00:03:43,340 --> 00:03:48,440
So B has a child C so we visit child C and there is no other child right.

72
00:03:48,440 --> 00:03:52,190
So that is why after that we go to the child of F which is E.

73
00:03:52,280 --> 00:03:53,570
Now if.

74
00:03:54,170 --> 00:03:55,520
Be had a child.

75
00:03:55,520 --> 00:03:58,280
So in this case be does not have another child other than C.

76
00:03:58,280 --> 00:04:03,320
So that's why after C we go to E which is the child of F, but let's say there was one more child over

77
00:04:03,320 --> 00:04:04,250
here C two.

78
00:04:04,250 --> 00:04:10,250
Then after this we would have visited C two or it could the the order can change but we're just seeing

79
00:04:10,250 --> 00:04:10,910
the levels right.

80
00:04:10,910 --> 00:04:14,390
So we have we would have visited the neighbors before we visit child.

81
00:04:14,390 --> 00:04:17,150
So we are not going to D which is the child of C.

82
00:04:17,150 --> 00:04:17,720
All right.

83
00:04:17,720 --> 00:04:21,380
So over here we are visiting C, then we visit E.

84
00:04:21,380 --> 00:04:24,560
And after this we go to the next level which is D.

85
00:04:24,560 --> 00:04:28,850
So you can see that this is one level B and f c and d is the next level.

86
00:04:28,850 --> 00:04:30,170
And then we go to D.

87
00:04:30,200 --> 00:04:33,440
Now this is very much different from depth first search.

88
00:04:33,440 --> 00:04:37,310
In that case we would have gone as deep first as possible.

89
00:04:37,310 --> 00:04:40,220
That is we visit children first before neighbors.

90
00:04:40,220 --> 00:04:46,910
But in the case of breadth first search or breadth first traversal, we visit neighbors before we visit

91
00:04:46,910 --> 00:04:47,600
child nodes.

92
00:04:47,600 --> 00:04:49,640
So this is the idea of BFS.

93
00:04:49,640 --> 00:04:56,120
Now let's go ahead and think about the algorithm which we can use to implement BFS in a graph.

94
00:04:56,120 --> 00:04:59,810
Now we have this graph and it is stored as an adjacency list.

95
00:04:59,810 --> 00:05:02,090
And we have the adjacency list over here.

96
00:05:02,090 --> 00:05:09,320
Now the algorithm for BFS over here is going to be very much similar to the algorithm which we saw before

97
00:05:09,320 --> 00:05:12,260
in the case of a binary tree for BFS.

98
00:05:12,260 --> 00:05:14,360
So again we are going to use a queue.

99
00:05:14,360 --> 00:05:15,530
So let's write that.

100
00:05:15,530 --> 00:05:17,210
So initially the queue is empty.

101
00:05:19,270 --> 00:05:25,570
And we also need an output array because as per the question, we are going to return an output array

102
00:05:25,570 --> 00:05:28,120
with the nodes right with the value of the nodes.

103
00:05:28,120 --> 00:05:31,720
So as we visit nodes, we're just going to push values to the output array.

104
00:05:31,720 --> 00:05:37,660
And then to know that we have visited something, visited a node or not, we will need a visited object

105
00:05:37,660 --> 00:05:39,490
so that we don't get into a loop.

106
00:05:39,490 --> 00:05:41,260
And we never come out of it.

107
00:05:41,260 --> 00:05:41,410
Right.

108
00:05:41,410 --> 00:05:44,050
So we don't want to visit something again and again.

109
00:05:44,050 --> 00:05:46,390
We only want to visit a node one time.

110
00:05:46,390 --> 00:05:46,960
All right.

111
00:05:46,960 --> 00:05:49,060
Now let's say we want to start at a.

112
00:05:49,090 --> 00:05:55,300
Now this has to be specified for the BFS algorithm because unlike a tree there is no root over here.

113
00:05:55,300 --> 00:05:57,490
So let's say we want to start at a.

114
00:05:57,490 --> 00:05:59,290
So we have visited a.

115
00:05:59,290 --> 00:06:01,180
So we push that to our queue.

116
00:06:01,180 --> 00:06:01,600
All right.

117
00:06:01,600 --> 00:06:05,110
So we push it to our queue and we mark it as visited.

118
00:06:05,110 --> 00:06:07,660
So over here we say a is visited.

119
00:06:07,660 --> 00:06:08,740
So we say a true.

120
00:06:08,740 --> 00:06:09,220
All right.

121
00:06:09,220 --> 00:06:12,940
So we make this entry this key value pair in our visited object.

122
00:06:12,940 --> 00:06:15,280
Now let's have the pseudo code over here.

123
00:06:15,280 --> 00:06:19,510
It's going to be very much similar to what you've seen in the case of the binary tree.

124
00:06:19,510 --> 00:06:25,840
We are going to have a while loop, and the steps inside the while loop are going to repeat as long

125
00:06:25,840 --> 00:06:27,460
as there is something in the queue.

126
00:06:27,460 --> 00:06:31,750
So while queue dot length is greater than zero, we are going to repeat these steps.

127
00:06:31,750 --> 00:06:34,690
So at this point we have a in our queue.

128
00:06:34,690 --> 00:06:36,430
So yes this is true right?

129
00:06:36,430 --> 00:06:38,500
Q dot length is one which is greater than zero.

130
00:06:38,500 --> 00:06:39,820
So we come inside.

131
00:06:39,820 --> 00:06:41,980
Now we are going to dequeue from the queue.

132
00:06:41,980 --> 00:06:45,310
So we take the first element out which is a at this point.

133
00:06:45,310 --> 00:06:47,440
And we are going to push it to the output array.

134
00:06:47,440 --> 00:06:50,920
So we push it over here and we have a coming to the output array.

135
00:06:50,950 --> 00:06:56,980
Now we are going to enqueue all the unvisited neighbours of this particular node.

136
00:06:56,980 --> 00:06:59,080
So enqueue unvisited neighbors.

137
00:06:59,080 --> 00:07:00,640
So that is the next step.

138
00:07:00,640 --> 00:07:06,820
So in this case for this we will use our adjacency list and the neighbors of A or b and f.

139
00:07:06,820 --> 00:07:08,740
And we will take b right.

140
00:07:08,740 --> 00:07:10,090
Which is the first element over here.

141
00:07:10,090 --> 00:07:12,700
We will check whether it is in the visited object.

142
00:07:12,730 --> 00:07:13,690
No it's not there.

143
00:07:13,690 --> 00:07:17,260
So we make an entry and we add it to the queue.

144
00:07:17,260 --> 00:07:17,530
Right.

145
00:07:17,530 --> 00:07:19,960
So we enqueue it and then we mark it as visited.

146
00:07:19,960 --> 00:07:23,350
So whatever gets into our queue will be marked as visited.

147
00:07:23,350 --> 00:07:24,790
So let's add it to our queue.

148
00:07:24,790 --> 00:07:26,380
And we mark B as visited.

149
00:07:26,380 --> 00:07:30,610
And then we take the next neighbor of A which is F right.

150
00:07:30,610 --> 00:07:33,040
So f is also not there in our visited object.

151
00:07:33,040 --> 00:07:34,330
So we make an entry.

152
00:07:34,330 --> 00:07:36,910
So we have f and we say f is true.

153
00:07:37,330 --> 00:07:37,750
All right.

154
00:07:37,750 --> 00:07:39,250
So there is no other neighbor.

155
00:07:39,250 --> 00:07:40,510
So we are done with this step.

156
00:07:40,510 --> 00:07:44,740
And again we come to this check and we see that there are two elements in the queue.

157
00:07:44,770 --> 00:07:45,010
Right.

158
00:07:45,010 --> 00:07:46,870
So q dot length is greater than zero.

159
00:07:46,870 --> 00:07:47,890
So we proceed.

160
00:07:47,890 --> 00:07:50,800
We again d queue which is b at this point.

161
00:07:50,800 --> 00:07:51,220
Right.

162
00:07:51,220 --> 00:07:53,470
And we push it to our output array.

163
00:07:53,470 --> 00:08:00,160
So you can see after A we have taken B and then we are going to enqueue the neighbors the unvisited

164
00:08:00,160 --> 00:08:01,180
neighbors of B.

165
00:08:01,180 --> 00:08:04,450
So at this point again we check our adjacency list.

166
00:08:04,450 --> 00:08:07,690
We can see that the neighbors of b, r, a, f and c.

167
00:08:07,780 --> 00:08:10,990
So we take the first element a, but it's already visited.

168
00:08:10,990 --> 00:08:12,010
So we skip.

169
00:08:12,010 --> 00:08:15,520
We move ahead and then we take the next neighbor which is f.

170
00:08:15,520 --> 00:08:17,170
F is also already visited.

171
00:08:17,170 --> 00:08:19,990
So we proceed further and we have c over here right.

172
00:08:19,990 --> 00:08:21,310
And C is not visited.

173
00:08:21,310 --> 00:08:25,390
So we push that to our queue and we mark it as visited.

174
00:08:25,390 --> 00:08:28,720
So we push C to our queue and we mark C as visited.

175
00:08:28,720 --> 00:08:30,460
And then we proceed again.

176
00:08:30,460 --> 00:08:32,950
Queue dot length at this point is equal to two right.

177
00:08:32,950 --> 00:08:37,570
So again we dequeue and push f to our output array.

178
00:08:37,570 --> 00:08:41,170
And then we are going to enqueue the unvisited neighbors of f.

179
00:08:41,170 --> 00:08:46,990
At this point the neighbors of f are a, b and e and a and B are already there right within the visited

180
00:08:46,990 --> 00:08:49,960
object or the hash table, so only E remains.

181
00:08:49,960 --> 00:08:53,680
So we push e to the queue and we mark e as visited.

182
00:08:53,680 --> 00:08:57,730
Now over here remember we are doing BFS or breadth first search.

183
00:08:57,730 --> 00:08:59,980
And we want neighbors before children.

184
00:08:59,980 --> 00:09:04,210
So to ensure that you can see over here what's happening is in the queue.

185
00:09:04,240 --> 00:09:06,490
We are pushing neighbors before children.

186
00:09:06,490 --> 00:09:12,370
So over here when we were at A we pushed B and F together right one after the other.

187
00:09:12,370 --> 00:09:19,750
And later when we get to B only at that point we are pushing C, which is a child of B, right.

188
00:09:19,750 --> 00:09:22,510
So this is the way that we are ensuring that.

189
00:09:22,510 --> 00:09:24,220
And then we are removing from the beginning.

190
00:09:24,220 --> 00:09:24,400
Right?

191
00:09:24,400 --> 00:09:26,740
We are dequeuing that is, we are taking from the beginning.

192
00:09:26,740 --> 00:09:28,780
So it's a Fifo data structure.

193
00:09:28,780 --> 00:09:30,340
The queue first in first out.

194
00:09:30,340 --> 00:09:34,420
So in this way we ensure that we get neighbors before children.

195
00:09:34,420 --> 00:09:35,110
All right.

196
00:09:35,140 --> 00:09:36,880
Now let's again proceed.

197
00:09:37,360 --> 00:09:40,930
So we have uh we have F in our output array.

198
00:09:40,960 --> 00:09:43,360
Now we added e right.

199
00:09:43,360 --> 00:09:44,110
We added e.

200
00:09:44,140 --> 00:09:45,580
Now this is over again.

201
00:09:45,580 --> 00:09:46,630
There is something in the queue.

202
00:09:46,630 --> 00:09:47,590
So we dequeue right.

203
00:09:47,590 --> 00:09:48,340
So we dequeue.

204
00:09:48,340 --> 00:09:51,700
So we take out C and we add add it to the output array.

205
00:09:51,700 --> 00:09:54,760
And then we check the neighbors of c, b, e and d.

206
00:09:54,790 --> 00:09:56,200
These are the neighbors of C.

207
00:09:56,230 --> 00:10:00,100
Now among this b and e are already there in our hash table.

208
00:10:00,100 --> 00:10:01,420
So only d remains.

209
00:10:01,420 --> 00:10:05,710
So let's add it to the visited object or the hash table and we enqueue it.

210
00:10:05,710 --> 00:10:07,150
So we have D over here.

211
00:10:08,240 --> 00:10:08,750
All right.

212
00:10:08,750 --> 00:10:12,050
Again, the queue is still not empty.

213
00:10:12,050 --> 00:10:15,530
So we de queue and we push E to our output array.

214
00:10:16,870 --> 00:10:20,590
And we are going to check the neighbors of E, which is D, C, and F.

215
00:10:20,590 --> 00:10:25,510
Now D, C and F are already visited, so we don't enqueue anything.

216
00:10:25,510 --> 00:10:28,990
But again, when we come over here we see that the queue is not empty.

217
00:10:28,990 --> 00:10:30,370
There is still one element.

218
00:10:30,370 --> 00:10:33,160
So we'd queue and push it to our output array.

219
00:10:33,160 --> 00:10:38,140
And then we are going to check the neighbors of D, which is C and E, and you can see that C and D

220
00:10:38,140 --> 00:10:41,140
are already there in our visited hash table or object.

221
00:10:41,140 --> 00:10:42,790
So we don't enqueue anything.

222
00:10:42,790 --> 00:10:48,370
And again when we come again and check over here, we see that the queue is empty or the length is zero

223
00:10:48,370 --> 00:10:49,930
and zero is not greater than zero.

224
00:10:49,930 --> 00:10:50,680
So we are done.

225
00:10:50,680 --> 00:10:54,730
And this is our breadth first search or breadth first traversal.

226
00:10:54,730 --> 00:10:56,200
So we go from A.

227
00:10:56,200 --> 00:10:58,990
Then we have b and f which are in the same level.

228
00:10:58,990 --> 00:11:01,900
Then we have C and E which are in the same level.

229
00:11:01,900 --> 00:11:04,360
And then we go to D which is the last level.

230
00:11:04,360 --> 00:11:10,930
So in the breadth first search we have seen that we take neighbors before children and we use a queue

231
00:11:10,930 --> 00:11:12,490
to implement the BFS.

232
00:11:12,490 --> 00:11:18,820
And again notice this is very much similar to the implementation of BFS in the case of a binary tree.

233
00:11:18,820 --> 00:11:21,790
And we have done that question in the case of a binary search tree.

234
00:11:21,790 --> 00:11:21,970
Right.

235
00:11:21,970 --> 00:11:25,300
So the same applies in the case of a binary tree as well.

236
00:11:25,300 --> 00:11:25,840
All right.

237
00:11:25,870 --> 00:11:30,850
Now let's proceed and look at the space and time complexity of this solution.

238
00:11:31,670 --> 00:11:35,150
Now first, let's look at the time complexity.

239
00:11:35,180 --> 00:11:42,170
The time complexity of this solution is of the order of V plus E, where v is the number of vertices.

240
00:11:42,170 --> 00:11:46,220
In this case we have six vertices and e is the number of edges.

241
00:11:46,220 --> 00:11:47,150
Right over here.

242
00:11:47,150 --> 00:11:48,350
What's the number of edges?

243
00:11:48,350 --> 00:11:49,790
Let's just check this is one.

244
00:11:49,790 --> 00:11:50,480
This is two.

245
00:11:50,510 --> 00:11:51,230
This is three.

246
00:11:51,230 --> 00:11:53,600
This is four, five, six, seven and eight.

247
00:11:53,600 --> 00:11:54,920
So we have eight edges.

248
00:11:54,920 --> 00:11:58,610
So the time complexity is of the order of V plus e.

249
00:11:58,640 --> 00:12:01,700
Now let's try to understand why that is over here.

250
00:12:01,700 --> 00:12:04,760
This algorithm is to traverse the graph.

251
00:12:04,760 --> 00:12:08,030
So traverse means we are going to visit every node once right.

252
00:12:08,030 --> 00:12:12,980
So because we visit every node once we definitely do V operations.

253
00:12:12,980 --> 00:12:15,200
So that is why we have v over here.

254
00:12:15,200 --> 00:12:21,140
Now when we look at the algorithm this is done by this part over here right while q dot length greater

255
00:12:21,140 --> 00:12:21,710
than zero.

256
00:12:21,710 --> 00:12:28,970
So at if you take all the instances together you can see that we will get all the nodes at least once

257
00:12:28,970 --> 00:12:29,930
and exactly once.

258
00:12:29,930 --> 00:12:30,140
Right.

259
00:12:30,140 --> 00:12:31,190
All the nodes will be there.

260
00:12:31,190 --> 00:12:32,900
Exactly once in our queue.

261
00:12:32,900 --> 00:12:34,010
So you can see that over here.

262
00:12:34,010 --> 00:12:34,280
Right.

263
00:12:34,280 --> 00:12:40,880
So this while loop over here will happen v number of times because we will have v elements in the queue.

264
00:12:40,880 --> 00:12:41,270
Right.

265
00:12:41,270 --> 00:12:44,420
So this is what takes care of this v over here.

266
00:12:44,420 --> 00:12:46,880
Again remember we are traversing every vertex.

267
00:12:46,880 --> 00:12:49,280
So we have to do v operations.

268
00:12:49,280 --> 00:12:51,380
So that is why we have our v over here.

269
00:12:51,380 --> 00:12:53,300
Now what about this e over here.

270
00:12:53,300 --> 00:12:59,870
This is for because of the for loop which is which will be used to enqueue all the unvisited neighbours.

271
00:12:59,870 --> 00:13:00,080
Right.

272
00:13:00,080 --> 00:13:02,120
So that is why we have e over here.

273
00:13:02,120 --> 00:13:04,160
Now how does this turn out to be E.

274
00:13:04,190 --> 00:13:06,350
So let's take a look at the algorithm.

275
00:13:06,350 --> 00:13:08,330
So we have this pseudocode over here.

276
00:13:08,330 --> 00:13:13,040
So this part of the code takes care of enqueuing unvisited neighbors.

277
00:13:13,520 --> 00:13:15,500
Now when we are at a right.

278
00:13:15,500 --> 00:13:18,080
So this part over here will loop two times.

279
00:13:18,080 --> 00:13:18,260
Right.

280
00:13:18,260 --> 00:13:20,630
Because there are two neighbors for a.

281
00:13:20,660 --> 00:13:26,060
Similarly, when we are at node B this part will loop three times because there are three neighbors

282
00:13:26,060 --> 00:13:26,480
of B.

283
00:13:26,480 --> 00:13:27,980
So let me just write that over here.

284
00:13:27,980 --> 00:13:33,590
So this this does it three times when we are at node C, this part over here will loop three times because

285
00:13:33,590 --> 00:13:34,940
there are three neighbors for C.

286
00:13:34,940 --> 00:13:36,110
So again that's three.

287
00:13:36,110 --> 00:13:38,660
When we are at node D it has two neighbors.

288
00:13:38,660 --> 00:13:41,690
So over here this will check it two times right.

289
00:13:41,690 --> 00:13:44,480
The for loop will be going for two iterations.

290
00:13:44,480 --> 00:13:47,570
And when we are at E again it will be three times.

291
00:13:47,570 --> 00:13:50,180
And when we are at F the for loop will happen.

292
00:13:50,180 --> 00:13:52,100
Three will do three iterations, right.

293
00:13:52,100 --> 00:13:57,560
So the total number of operations which is happening over here is two plus three plus three plus two

294
00:13:57,560 --> 00:13:58,790
plus three plus three.

295
00:13:58,790 --> 00:14:01,310
So two and three is five three and two is five.

296
00:14:01,310 --> 00:14:04,100
So five and five is ten and ten and six.

297
00:14:04,100 --> 00:14:05,840
That's 16 operations.

298
00:14:05,840 --> 00:14:09,140
And we have seen that in this graph over here we have eight edges.

299
00:14:09,140 --> 00:14:11,810
So 12345678.

300
00:14:11,810 --> 00:14:13,280
So we have eight edges.

301
00:14:13,280 --> 00:14:19,100
Now therefore this over here this is actually two times this is actually two times the number of edges

302
00:14:19,100 --> 00:14:19,940
operations.

303
00:14:19,940 --> 00:14:20,240
Right.

304
00:14:20,240 --> 00:14:25,130
So we can say that the time complexity is actually O of V plus two e.

305
00:14:25,190 --> 00:14:28,220
But because two is a constant we just avoid it.

306
00:14:28,220 --> 00:14:30,230
And that's how we get e over here.

307
00:14:30,230 --> 00:14:33,440
So the time complexity is O of v plus e.

308
00:14:33,470 --> 00:14:35,660
And again we have a two over here.

309
00:14:35,660 --> 00:14:39,770
Because the graph which we dealt with over here is an undirected graph.

310
00:14:39,770 --> 00:14:44,360
If it was a directed graph then if it is stored as an adjacency list.

311
00:14:44,360 --> 00:14:47,870
So the total of all these would be equal to the number of edges.

312
00:14:47,870 --> 00:14:53,180
So in that case also the time complexity is O of v plus e if we implement BFS.

313
00:14:53,210 --> 00:14:53,690
All right.

314
00:14:53,690 --> 00:14:58,010
So we have understood why the time complexity is of the order of V plus e.

315
00:14:58,040 --> 00:15:01,010
So we are doing operations of the order of V plus e.

316
00:15:01,040 --> 00:15:04,220
So this v is accounted by this while loop over here.

317
00:15:04,220 --> 00:15:10,640
And then this E is the total of the of the operations that will be performed by the for loop over here.

318
00:15:10,640 --> 00:15:13,340
And we have seen how we get to E in this case.

319
00:15:13,340 --> 00:15:13,640
Right.

320
00:15:13,640 --> 00:15:19,340
Because at every node we will be doing a for loop to traverse the neighbors of that particular node.

321
00:15:19,340 --> 00:15:19,850
All right.

322
00:15:19,880 --> 00:15:22,190
Now we have understood the time complexity.

323
00:15:22,190 --> 00:15:23,750
Let me just clear this up.

324
00:15:23,750 --> 00:15:27,230
Now let's take a look at the space complexity of this solution.

325
00:15:27,230 --> 00:15:31,130
For this, let's try to think what takes up auxiliary space.

326
00:15:31,130 --> 00:15:31,580
Right.

327
00:15:31,580 --> 00:15:35,750
Again remember this adjacency list over here is given as part of the question.

328
00:15:35,750 --> 00:15:38,930
So we are we we are only dealing with auxiliary space.

329
00:15:38,930 --> 00:15:44,510
So when it comes to space complexity it is equal to of of the order of V.

330
00:15:44,510 --> 00:15:48,560
Because only this visited object takes extra space.

331
00:15:48,560 --> 00:15:48,740
Right.

332
00:15:48,740 --> 00:15:50,270
And again we have this output array.

333
00:15:50,270 --> 00:15:58,400
Now if we did not want an output array then also space would be taken up by the visited object and then

334
00:15:58,400 --> 00:15:59,180
also by the queue.

335
00:15:59,180 --> 00:16:00,440
So let's just write that out.

336
00:16:00,440 --> 00:16:04,850
So what are the elements that take up auxiliary space or extra space.

337
00:16:04,850 --> 00:16:06,860
We have the visited object over here.

338
00:16:06,860 --> 00:16:10,490
We have our output array and we have the queue over here.

339
00:16:10,490 --> 00:16:11,120
All right.

340
00:16:11,120 --> 00:16:17,180
Now the visited object clearly will take v number of key value entries.

341
00:16:17,180 --> 00:16:17,600
Right.

342
00:16:17,600 --> 00:16:21,170
Because for every node we will have one entry.

343
00:16:21,170 --> 00:16:24,710
So that's why this is going to take space of the order of V.

344
00:16:24,710 --> 00:16:25,100
All right.

345
00:16:25,100 --> 00:16:27,290
So this takes space of the order of V.

346
00:16:27,290 --> 00:16:31,070
Again the output array is also going to have every vertex right.

347
00:16:31,070 --> 00:16:31,250
So.

348
00:16:31,380 --> 00:16:31,680
Again.

349
00:16:31,680 --> 00:16:34,800
This also takes up O of V space and the queue.

350
00:16:34,830 --> 00:16:39,300
The queue we have seen in this case takes up less than O of V space.

351
00:16:39,300 --> 00:16:45,150
But if we take the worst case possibility of the graph, let's take a graph that looks something like

352
00:16:45,150 --> 00:16:45,330
this.

353
00:16:45,330 --> 00:16:45,540
Right.

354
00:16:45,540 --> 00:16:49,860
So we have node A and this node over here is connected to every other node.

355
00:16:49,860 --> 00:16:57,750
So when we enqueue the neighbors of node A we will have b, c, d, e and f at the same time in our

356
00:16:57,750 --> 00:16:57,930
queue.

357
00:16:57,960 --> 00:16:58,230
Right.

358
00:16:58,230 --> 00:17:01,560
And that is equal to v minus one elements.

359
00:17:01,560 --> 00:17:08,280
So we can say that in the worst case the queue also will take o of v -1 or 1 is just a constant.

360
00:17:08,280 --> 00:17:09,570
So we avoid that.

361
00:17:09,570 --> 00:17:13,140
And in the worst case the queue itself can take O of v space.

362
00:17:13,140 --> 00:17:16,260
So each of these take up O of v space.

363
00:17:16,260 --> 00:17:20,730
And hence we say that the space complexity of this solution is O of v.

364
00:17:20,730 --> 00:17:26,700
Again, remember we could say o of a constant into v, but then we remove a, we remove constants and

365
00:17:26,700 --> 00:17:30,240
therefore the space complexity of the solution is O of v.

366
00:17:31,660 --> 00:17:39,100
In the next video we will see how we implement BFS when the graph is stored as an adjacency matrix.

367
00:17:39,100 --> 00:17:42,460
And there you will see that this time complexity changes.

368
00:17:42,460 --> 00:17:44,290
Let's see that in the next video.