1
00:00:00,810 --> 00:00:01,830
Welcome back.

2
00:00:01,830 --> 00:00:05,610
Let's now code the breadth first search approach for this graph.

3
00:00:05,610 --> 00:00:08,160
Now we will traverse this graph which is given over here.

4
00:00:08,160 --> 00:00:10,500
And it's stored as an adjacency list.

5
00:00:10,500 --> 00:00:13,530
Now we will traverse this using the BFS approach.

6
00:00:13,530 --> 00:00:15,060
All right so let's get started.

7
00:00:15,060 --> 00:00:18,720
So we will write a function let's call it traverse BFS.

8
00:00:18,720 --> 00:00:19,200
All right.

9
00:00:19,200 --> 00:00:24,180
So let's say const traverse BFS is equal to function.

10
00:00:24,180 --> 00:00:28,110
And when we call this function we will pass the graph right.

11
00:00:28,110 --> 00:00:30,750
So this is the graph the adjacency adjacency list.

12
00:00:30,750 --> 00:00:32,340
So let's just call it graph.

13
00:00:32,340 --> 00:00:35,610
And then we will also mention where we have to start.

14
00:00:35,610 --> 00:00:36,300
All right.

15
00:00:36,300 --> 00:00:41,370
Now over here inside this function we will have an output array right.

16
00:00:41,370 --> 00:00:42,390
So that's the question right.

17
00:00:42,390 --> 00:00:43,980
So let's just call it output.

18
00:00:43,980 --> 00:00:45,840
And this will be an empty array.

19
00:00:45,840 --> 00:00:48,870
And at the end we will just return this output.

20
00:00:48,870 --> 00:00:50,910
So that's how we are going to do this.

21
00:00:51,120 --> 00:00:56,700
And when we call this function we will have to pass this adjacency list and the starting point.

22
00:00:56,700 --> 00:01:00,030
So from where do we want to start the BFS traversal.

23
00:01:00,030 --> 00:01:07,140
So let's say graph BFS and we pass the graph uh or sorry over here it's called the adjacency list.

24
00:01:07,140 --> 00:01:07,350
Right.

25
00:01:07,350 --> 00:01:09,360
So we pass the adjacency list.

26
00:01:09,360 --> 00:01:11,340
And let's say we want to start at eight.

27
00:01:11,640 --> 00:01:12,120
All right.

28
00:01:12,120 --> 00:01:14,310
So this is how we are going to do this.

29
00:01:14,310 --> 00:01:16,470
Now let's get started with the function.

30
00:01:16,470 --> 00:01:22,050
So once we are inside this so we have defined the empty array which will be the output.

31
00:01:22,050 --> 00:01:28,140
Now we need an object let's call it visited so that we can track whether we have visited a vertex.

32
00:01:28,140 --> 00:01:28,500
All right.

33
00:01:28,500 --> 00:01:30,270
So let's call it visited.

34
00:01:30,270 --> 00:01:33,180
And we also need a queue right.

35
00:01:33,180 --> 00:01:34,560
So we'll need a queue const.

36
00:01:34,560 --> 00:01:36,060
Let's just call it queue itself.

37
00:01:36,060 --> 00:01:38,760
And initially itself because we are starting over here.

38
00:01:38,760 --> 00:01:39,060
Right.

39
00:01:39,060 --> 00:01:41,100
Whatever is the start which is passed to it.

40
00:01:41,100 --> 00:01:44,730
So we can fill the start into the queue over here itself.

41
00:01:45,180 --> 00:01:49,410
And whenever we are filling something into the queue, we mark it as visited.

42
00:01:49,410 --> 00:01:49,590
Right?

43
00:01:49,590 --> 00:01:53,580
So we can say visited at start is true.

44
00:01:55,320 --> 00:01:55,890
All right.

45
00:01:55,920 --> 00:01:58,050
Now we also need a variable.

46
00:01:58,050 --> 00:02:01,230
Let's call it just current so that we can track where we are.

47
00:02:01,230 --> 00:02:06,000
And I don't want to put it inside the while loop so that we don't initialize it again and again.

48
00:02:06,000 --> 00:02:08,280
So over here we'll have the while loop.

49
00:02:08,280 --> 00:02:12,420
And this will keep going as long as something is there in the queue.

50
00:02:12,420 --> 00:02:12,600
Right.

51
00:02:12,600 --> 00:02:17,070
So we can say while queue dot length is greater than zero right.

52
00:02:17,250 --> 00:02:22,320
Or you can just say queue dot length also because zero as you know is falsy in JavaScript.

53
00:02:22,320 --> 00:02:22,710
All right.

54
00:02:22,710 --> 00:02:26,250
So while while queue dot length is greater than zero let's continue.

55
00:02:26,250 --> 00:02:27,840
So what is it that we're going to do.

56
00:02:27,840 --> 00:02:32,970
We are going to first we are going to shift or take from the beginning what is there in the queue.

57
00:02:32,970 --> 00:02:35,970
So we can say current is equal to Q dot shift.

58
00:02:35,970 --> 00:02:41,280
Now remember when you're implementing this in the interview you should mention that over here we are

59
00:02:41,280 --> 00:02:44,070
implementing the queue as an array just to save time.

60
00:02:44,070 --> 00:02:44,340
All right.

61
00:02:44,340 --> 00:02:48,060
So the queue over here is implemented as an array just to save time.

62
00:02:48,060 --> 00:02:52,860
Ideally you should be implementing it as a linked list to get the optimum performance.

63
00:02:52,860 --> 00:02:57,720
Because over here you can notice that we are taking or we are removing an element from the beginning

64
00:02:57,720 --> 00:02:58,320
of the queue.

65
00:02:58,320 --> 00:03:03,870
So if we implement the queue as an array and if we do this over here, that's an O of n operation.

66
00:03:03,870 --> 00:03:04,020
Right.

67
00:03:04,020 --> 00:03:05,160
So it's not efficient.

68
00:03:05,160 --> 00:03:09,420
So if we had implemented the queue as a linked list then that would be a O of one operation.

69
00:03:09,420 --> 00:03:10,020
All right.

70
00:03:10,020 --> 00:03:11,040
So let's proceed.

71
00:03:11,040 --> 00:03:13,350
And remember queue is a Fifo data structure.

72
00:03:13,350 --> 00:03:17,520
So we take out from the queue what was first input.

73
00:03:17,520 --> 00:03:17,700
Right.

74
00:03:17,700 --> 00:03:20,190
So what came in first comes out first.

75
00:03:20,190 --> 00:03:20,640
All right.

76
00:03:20,640 --> 00:03:21,360
So let's proceed.

77
00:03:21,360 --> 00:03:24,630
So we have we take out the element from the beginning of the queue.

78
00:03:24,630 --> 00:03:26,580
And then we push it to the output array.

79
00:03:26,580 --> 00:03:27,930
So output dot push.

80
00:03:27,930 --> 00:03:29,400
And then we say current.

81
00:03:29,400 --> 00:03:31,800
So we push the current element to the output array.

82
00:03:31,980 --> 00:03:37,170
Now once we are done with this we need to identify the neighbors of this current node.

83
00:03:37,170 --> 00:03:37,590
All right.

84
00:03:37,590 --> 00:03:42,150
So for this we will make use of the adjacency list or in this case inside the function.

85
00:03:42,150 --> 00:03:43,470
It's called the graph right.

86
00:03:43,470 --> 00:03:46,020
So let's say const neighbors.

87
00:03:47,130 --> 00:03:48,360
And that will give us an array.

88
00:03:48,360 --> 00:03:48,510
Right.

89
00:03:48,510 --> 00:03:50,490
So it will give us the value over here.

90
00:03:50,490 --> 00:03:54,840
You can see that in this list in this object actually the value is an array.

91
00:03:54,840 --> 00:03:56,190
So this will give us an array.

92
00:03:56,190 --> 00:03:58,860
So const neighbors is equal to graph.

93
00:03:59,650 --> 00:04:01,570
And graph at current.

94
00:04:01,570 --> 00:04:02,830
So we say current.

95
00:04:03,100 --> 00:04:06,670
So we're going to pass current which is going to be a in this case in the beginning.

96
00:04:06,670 --> 00:04:06,970
Right.

97
00:04:06,970 --> 00:04:09,610
And later it's going to be one of these vertices.

98
00:04:09,610 --> 00:04:11,830
So we will pass that that as the key.

99
00:04:11,830 --> 00:04:14,140
And we get the value as this array over here.

100
00:04:14,170 --> 00:04:14,650
All right.

101
00:04:14,650 --> 00:04:18,070
So we say graph at current is neighbors.

102
00:04:18,070 --> 00:04:21,700
Now once we are done this with this we need to loop through this array.

103
00:04:21,700 --> 00:04:22,090
Right.

104
00:04:22,090 --> 00:04:27,820
And we have to check whether that particular vertex in the array is already in the visited object.

105
00:04:27,820 --> 00:04:29,380
If not we will push it to the queue.

106
00:04:29,380 --> 00:04:32,500
So that's how we are going to do this, right as we discussed in the previous video.

107
00:04:32,500 --> 00:04:34,390
So let's go ahead and implement this.

108
00:04:34,390 --> 00:04:38,560
So for this I'm just going to write for let I is equal to zero.

109
00:04:38,560 --> 00:04:44,770
Now as long as I less than neighbors dot length I plus plus.

110
00:04:45,660 --> 00:04:46,290
All right.

111
00:04:46,290 --> 00:04:53,550
Now, once we are inside this, let's identify what is the vertex at I at index I of this array over

112
00:04:53,550 --> 00:04:58,500
here, right of these arrays at whatever particular array based on the key which you have passed in.

113
00:04:58,500 --> 00:05:01,440
So over here we can say const neighbor.

114
00:05:03,320 --> 00:05:06,860
Is equal to neighbors at I.

115
00:05:07,640 --> 00:05:08,240
Right.

116
00:05:08,390 --> 00:05:10,610
So this will give us one of these vertices.

117
00:05:10,610 --> 00:05:10,970
Right.

118
00:05:10,970 --> 00:05:12,980
So let's say we are taking this array.

119
00:05:12,980 --> 00:05:14,870
We are we passed in a as the key.

120
00:05:14,900 --> 00:05:16,490
We would have got this array over here.

121
00:05:16,490 --> 00:05:19,430
Now when I is equal to zero we will get neighbor as b.

122
00:05:19,430 --> 00:05:22,250
And when I is equal to one we will get neighbor as f.

123
00:05:22,250 --> 00:05:22,760
All right.

124
00:05:22,760 --> 00:05:24,230
So we got a neighbor.

125
00:05:24,230 --> 00:05:29,090
Now we have to check whether this neighbor is there in the visited object or not.

126
00:05:29,090 --> 00:05:29,300
Right.

127
00:05:29,300 --> 00:05:32,330
So that we can know whether we have visited it or not.

128
00:05:32,330 --> 00:05:34,340
So let's say if not.

129
00:05:35,530 --> 00:05:37,150
If not visited.

130
00:05:37,630 --> 00:05:38,500
Neighbor.

131
00:05:39,880 --> 00:05:43,180
If so, that means it's not there in the visited object.

132
00:05:43,180 --> 00:05:44,770
That means we have not yet visited it.

133
00:05:44,770 --> 00:05:47,020
In this case, we have to push it to the queue, right?

134
00:05:47,020 --> 00:05:52,060
So we say queue dot push and we push the neighbor to the queue.

135
00:05:52,840 --> 00:05:53,230
All right.

136
00:05:53,260 --> 00:05:56,680
Now once we have pushed it to the queue we have to mark it as visited.

137
00:05:56,680 --> 00:05:59,560
So we say visited at neighbor.

138
00:06:00,880 --> 00:06:02,890
And we have to mark that as true.

139
00:06:02,890 --> 00:06:04,450
So this is equal to true.

140
00:06:05,200 --> 00:06:05,830
All right.

141
00:06:05,830 --> 00:06:06,640
And we are done.

142
00:06:06,640 --> 00:06:07,030
Right.

143
00:06:07,030 --> 00:06:13,330
So by this, uh, we come out of the while loop when there is nothing in the queue, and then we just

144
00:06:13,330 --> 00:06:14,740
return the output array.

145
00:06:14,740 --> 00:06:15,160
All right.

146
00:06:15,160 --> 00:06:16,720
So let's go ahead and test it.

147
00:06:16,720 --> 00:06:20,440
So we are we are calling the traverse function over here.

148
00:06:20,440 --> 00:06:24,310
We are passing this graph over here which is stored as an adjacency list to it.

149
00:06:24,310 --> 00:06:26,170
And then we are mentioning where to start.

150
00:06:26,170 --> 00:06:27,880
So let's look at the output.

151
00:06:28,560 --> 00:06:33,870
So I'm running this and you can see we are getting the output A, B, F, C, E and D.

152
00:06:33,960 --> 00:06:36,990
Now let's quickly take a look at what is happening over here.

153
00:06:36,990 --> 00:06:39,060
First let's analyze the output.

154
00:06:39,060 --> 00:06:41,940
So over here I'm just going to write over here itself.

155
00:06:41,940 --> 00:06:44,040
So let me just take a pen.

156
00:06:44,310 --> 00:06:45,000
All right.

157
00:06:45,670 --> 00:06:51,580
Now let's try to represent first this adjacency list as a graph so that it's easy for us to visualize.

158
00:06:51,580 --> 00:06:55,960
So I have a so I have a over here and it's connected to B and F right.

159
00:06:55,960 --> 00:06:58,810
So this is B and this is f.

160
00:06:59,460 --> 00:07:03,300
Now I have B which is connected to A, so we already have that connection.

161
00:07:03,300 --> 00:07:05,010
Then B is connected to F and C.

162
00:07:05,010 --> 00:07:08,070
So we have b and f and b and c.

163
00:07:08,100 --> 00:07:11,940
Now we come to c c is connected to B which we have already have over here.

164
00:07:11,940 --> 00:07:13,950
And c is connected to E and D.

165
00:07:13,950 --> 00:07:15,930
So let's just call it e over here.

166
00:07:15,930 --> 00:07:17,760
And I have D over here.

167
00:07:17,790 --> 00:07:21,480
Now we come to D d is connected to C and d is connected to E.

168
00:07:21,480 --> 00:07:22,920
So we make this connection.

169
00:07:22,920 --> 00:07:25,530
And when it comes to e is connected to D.

170
00:07:25,530 --> 00:07:29,100
And e is connected to C which we already have and e is connected to f.

171
00:07:29,100 --> 00:07:34,470
So we make this connection and f is connected to a, f is connected to b, and f is connected to E,

172
00:07:34,470 --> 00:07:35,280
which we already have.

173
00:07:35,280 --> 00:07:36,510
So this is our graph.

174
00:07:36,510 --> 00:07:39,150
And we started to traverse it from a right.

175
00:07:39,150 --> 00:07:40,230
So we passed in a.

176
00:07:40,320 --> 00:07:43,200
So let's check what's happening in the code.

177
00:07:44,410 --> 00:07:46,120
So let me just expand this a little bit.

178
00:07:46,120 --> 00:07:49,390
So we have our output over here and we have the graph over here.

179
00:07:49,390 --> 00:07:51,910
So I'm just taking the function into view.

180
00:07:51,910 --> 00:07:52,240
All right.

181
00:07:52,240 --> 00:07:53,650
So let's continue.

182
00:07:54,190 --> 00:07:54,550
All right.

183
00:07:54,550 --> 00:07:55,510
So let's proceed.

184
00:07:55,510 --> 00:08:01,060
So when we have called the function we are over here and we have passed the adjacency list which is

185
00:08:01,060 --> 00:08:01,570
this over here.

186
00:08:01,570 --> 00:08:02,260
And the start.

187
00:08:02,260 --> 00:08:03,310
So we are starting at a.

188
00:08:03,340 --> 00:08:05,170
Now we have output which is empty.

189
00:08:05,170 --> 00:08:06,580
So let's this is the output.

190
00:08:06,580 --> 00:08:07,090
All right.

191
00:08:07,090 --> 00:08:08,710
So output is empty.

192
00:08:08,710 --> 00:08:11,290
And we have visited which is also empty.

193
00:08:11,290 --> 00:08:12,880
So let's just track it over here.

194
00:08:12,880 --> 00:08:15,610
So I have visited over here and visited is empty.

195
00:08:15,610 --> 00:08:17,290
And we have the queue.

196
00:08:17,290 --> 00:08:18,310
So we have the queue.

197
00:08:18,310 --> 00:08:19,150
This is the queue.

198
00:08:19,150 --> 00:08:21,820
And we push the start right.

199
00:08:21,820 --> 00:08:25,120
So a is put into the queue at this point over here.

200
00:08:25,120 --> 00:08:25,450
Right.

201
00:08:25,450 --> 00:08:26,800
Cons queue is equal to start.

202
00:08:26,800 --> 00:08:29,350
So we have already the starting point in the queue.

203
00:08:29,350 --> 00:08:31,210
Now we are saying visited start true.

204
00:08:31,210 --> 00:08:34,240
So we are saying a and then we are giving the value true to it.

205
00:08:34,240 --> 00:08:36,490
So A is visited at this point.

206
00:08:36,520 --> 00:08:41,170
Now we are over here, we see that the length of the queue is greater than zero because we have this

207
00:08:41,170 --> 00:08:42,130
element over here, right?

208
00:08:42,130 --> 00:08:45,520
So we come over here and we take the first element out.

209
00:08:45,520 --> 00:08:48,520
So we take this out and we put it into the output.

210
00:08:48,520 --> 00:08:49,600
So we put it over here.

211
00:08:49,600 --> 00:08:50,050
All right.

212
00:08:50,050 --> 00:08:52,000
Now we are going to check its neighbors.

213
00:08:52,000 --> 00:08:53,980
So we are going to check the neighbors.

214
00:08:53,980 --> 00:08:56,830
And for this we are making use of the adjacency list.

215
00:08:56,830 --> 00:08:59,080
So let's just look at that for for a moment.

216
00:09:00,080 --> 00:09:02,060
So we are looking over here, right?

217
00:09:02,060 --> 00:09:08,510
So we can see that the neighbors of R, B and F over here, neighbors will be equal to this array over

218
00:09:08,510 --> 00:09:09,890
here B and f.

219
00:09:09,890 --> 00:09:10,250
Right.

220
00:09:10,250 --> 00:09:14,000
So again visually we can see that we are getting b and f which are the neighbors of A.

221
00:09:14,000 --> 00:09:17,900
Similarly when we have b we will get this array over here right which is a f.

222
00:09:17,900 --> 00:09:19,850
And see this a f and c.

223
00:09:19,880 --> 00:09:20,120
Right.

224
00:09:20,120 --> 00:09:21,620
So those are the neighbors of B.

225
00:09:21,620 --> 00:09:26,300
So over here neighbors is going to give us uh the neighbors of A.

226
00:09:26,300 --> 00:09:26,780
All right.

227
00:09:26,780 --> 00:09:28,160
So let's proceed.

228
00:09:29,490 --> 00:09:31,770
Uh, wait, let me just bring that back.

229
00:09:32,040 --> 00:09:33,660
So we need this over here, right?

230
00:09:33,660 --> 00:09:35,250
So let's continue from where we are.

231
00:09:35,250 --> 00:09:41,220
I'm just, uh, uh, clearing up a little bit of what we've written so that whatever is not clear,

232
00:09:41,220 --> 00:09:44,220
because I've shifted this, so that doesn't confuse us.

233
00:09:44,220 --> 00:09:45,300
So let's continue.

234
00:09:45,300 --> 00:09:47,670
So we have taken we are now over here.

235
00:09:47,670 --> 00:09:47,850
Right.

236
00:09:47,850 --> 00:09:53,430
We have we have got the neighbors of A now for the we are getting this array right B and F.

237
00:09:53,430 --> 00:09:57,090
Let me just write that over here so that we are very clear what we have.

238
00:09:57,090 --> 00:09:58,410
So we got B and F.

239
00:09:58,410 --> 00:10:02,610
So I'm just writing it over here we have this array b comma f.

240
00:10:04,000 --> 00:10:05,800
All right, now let's proceed.

241
00:10:06,160 --> 00:10:06,580
Um.

242
00:10:07,910 --> 00:10:08,240
This is.

243
00:10:08,240 --> 00:10:08,990
Come back.

244
00:10:08,990 --> 00:10:09,710
All right.

245
00:10:11,850 --> 00:10:12,240
All right.

246
00:10:12,240 --> 00:10:13,560
So we have the neighbors.

247
00:10:13,560 --> 00:10:16,890
Now for I is equal to zero I less than neighbors dot length.

248
00:10:17,010 --> 00:10:18,780
So the length of neighbors is two over here.

249
00:10:18,780 --> 00:10:21,510
So I is equal to zero and I is equal to one.

250
00:10:21,510 --> 00:10:23,640
For these two values the for loop will run right.

251
00:10:23,640 --> 00:10:24,750
So we take the neighbor.

252
00:10:24,750 --> 00:10:28,080
So we get first the neighbor as b and we are checking whether B is there.

253
00:10:28,080 --> 00:10:30,030
In visited we see that it is not there.

254
00:10:30,030 --> 00:10:31,770
So we put so what do we do.

255
00:10:31,770 --> 00:10:32,700
We push it to the queue.

256
00:10:32,700 --> 00:10:33,990
So we put B to the queue.

257
00:10:33,990 --> 00:10:35,430
So we have B over here.

258
00:10:35,430 --> 00:10:37,980
We put it to the queue and then we mark it as visited.

259
00:10:37,980 --> 00:10:40,020
So we have B as visited also.

260
00:10:40,020 --> 00:10:41,670
And then what do we do again.

261
00:10:41,670 --> 00:10:43,350
We come when I is equal to one right.

262
00:10:43,350 --> 00:10:47,070
So again we check whether f is there, f is not there, f is not there in visited.

263
00:10:47,070 --> 00:10:48,270
So we push it to the queue.

264
00:10:48,270 --> 00:10:49,530
So we have f over here.

265
00:10:49,620 --> 00:10:52,200
And then uh we mark f as visited.

266
00:10:52,200 --> 00:10:52,860
So I'm not writing.

267
00:10:52,890 --> 00:10:53,070
True.

268
00:10:53,070 --> 00:10:55,380
I'm just writing the element over here.

269
00:10:55,380 --> 00:10:56,940
And then we are out of the for loop.

270
00:10:56,940 --> 00:10:58,920
And again we come to the while loop over here.

271
00:10:58,920 --> 00:10:59,340
All right.

272
00:10:59,340 --> 00:11:03,720
So once we are over here again we are checking whether there is something in the queue we see.

273
00:11:03,720 --> 00:11:04,590
Yes it's there.

274
00:11:04,590 --> 00:11:06,270
So we have B and F in the queue.

275
00:11:06,270 --> 00:11:06,480
Right.

276
00:11:06,480 --> 00:11:09,060
So we we take the element from the beginning.

277
00:11:09,060 --> 00:11:13,260
So we take B out and we put it over here which is the output array.

278
00:11:13,260 --> 00:11:14,400
So output dot push current.

279
00:11:14,400 --> 00:11:16,020
So we get B over here.

280
00:11:16,770 --> 00:11:17,250
All right.

281
00:11:17,250 --> 00:11:19,620
Now we are checking the neighbors of B.

282
00:11:19,620 --> 00:11:23,880
So similarly when we check the neighbors of B we will get an array a f and c right.

283
00:11:23,880 --> 00:11:26,280
So let's take a look at that over here.

284
00:11:26,280 --> 00:11:27,570
Let's just go up.

285
00:11:27,900 --> 00:11:29,610
So we have a F and c.

286
00:11:29,610 --> 00:11:31,290
So let me just write that over here.

287
00:11:33,340 --> 00:11:34,180
Uh.

288
00:11:34,180 --> 00:11:37,210
All right, so I'm just removing this.

289
00:11:38,490 --> 00:11:38,790
All right.

290
00:11:38,790 --> 00:11:42,420
So the array that we are getting over here is f f and c.

291
00:11:42,570 --> 00:11:44,370
So that's the array we have.

292
00:11:44,880 --> 00:11:46,170
Now let's come back.

293
00:11:51,510 --> 00:11:52,230
All right.

294
00:11:52,500 --> 00:11:53,430
So.

295
00:11:54,160 --> 00:11:56,200
We are again inside the while loop.

296
00:11:56,590 --> 00:11:58,090
So let me clear this up.

297
00:12:02,340 --> 00:12:04,650
Okay, so we are inside the wire loop a while loop.

298
00:12:04,650 --> 00:12:09,570
So we are over here and uh, we, we took B, we pushed it to current.

299
00:12:09,570 --> 00:12:11,610
And then over here we are checking the neighbor.

300
00:12:11,610 --> 00:12:14,070
So we got a F and C as the neighbors of B.

301
00:12:14,070 --> 00:12:18,090
So inside this we are going to loop from I is equal to zero one and two.

302
00:12:18,120 --> 00:12:18,480
Right.

303
00:12:18,480 --> 00:12:20,250
So the length over here is three.

304
00:12:20,250 --> 00:12:22,800
So now first we take the first neighbor which is a.

305
00:12:22,830 --> 00:12:24,750
We see that it is already there in visited.

306
00:12:24,750 --> 00:12:26,010
So we don't push it to the queue.

307
00:12:26,010 --> 00:12:30,030
Then we check the next neighbor which is F we see it's there in the visited.

308
00:12:30,030 --> 00:12:30,300
Right.

309
00:12:30,300 --> 00:12:32,250
So we don't, uh, process this.

310
00:12:32,250 --> 00:12:36,000
Then we come over here and we see that visit C is not there in visited.

311
00:12:36,000 --> 00:12:39,300
So we put it into visited and we put it to the queue.

312
00:12:39,300 --> 00:12:39,510
Right.

313
00:12:39,510 --> 00:12:42,360
So we put it to the queue and we push it, put it to visited over here.

314
00:12:42,360 --> 00:12:43,860
And then we come out.

315
00:12:43,860 --> 00:12:43,980
Right.

316
00:12:43,980 --> 00:12:48,930
So we come out of this for loop and again we, we see that yes, we have stuff in the queue.

317
00:12:48,930 --> 00:12:49,860
So what do we do.

318
00:12:49,860 --> 00:12:53,280
We take the element from the beginning and we push it to the output.

319
00:12:53,280 --> 00:12:56,850
So we have F over here you can see that we are building the output a, b, f.

320
00:12:56,850 --> 00:12:58,590
That's what you're getting over here a, b.

321
00:12:58,590 --> 00:13:05,130
And then we got F right now again we come uh again we come over here we have we are now at the neighbors

322
00:13:05,130 --> 00:13:05,520
of F.

323
00:13:05,520 --> 00:13:08,670
We see that the neighbors of F are A, B and E, right.

324
00:13:08,670 --> 00:13:11,700
So again we will check whether A is there in visited.

325
00:13:11,700 --> 00:13:12,930
It's there B is also there.

326
00:13:12,930 --> 00:13:14,400
So only E is not there.

327
00:13:14,400 --> 00:13:15,570
So what do we do.

328
00:13:15,570 --> 00:13:17,580
So if E is not there we put it to the queue.

329
00:13:17,580 --> 00:13:21,090
So we get E over here and we mark E as visited.

330
00:13:21,090 --> 00:13:23,070
So we have E also as visited.

331
00:13:23,070 --> 00:13:26,490
Again we see that there are, there is, there are things in the queue.

332
00:13:26,520 --> 00:13:26,700
Right.

333
00:13:26,700 --> 00:13:28,440
So let me just take another pen.

334
00:13:28,440 --> 00:13:30,870
So over here we shift.

335
00:13:30,870 --> 00:13:34,290
So we take the first element and then we push it to the current element.

336
00:13:34,290 --> 00:13:35,340
So we have C over here.

337
00:13:35,340 --> 00:13:37,350
Now we check the the neighbors of C.

338
00:13:37,350 --> 00:13:40,320
So the neighbors of C are b D and E right.

339
00:13:40,320 --> 00:13:44,010
So we can see that we already have b and e in visited.

340
00:13:44,010 --> 00:13:45,210
So only d is remaining.

341
00:13:45,210 --> 00:13:48,660
So we put D to visited and we push it to the queue as well.

342
00:13:49,170 --> 00:13:49,560
Right.

343
00:13:49,560 --> 00:13:52,710
So again we see that there are there is things in the queue.

344
00:13:52,710 --> 00:13:55,110
So again we are, we are, we are over here.

345
00:13:55,110 --> 00:13:56,820
So again we come into the while loop.

346
00:13:56,820 --> 00:14:00,600
We take the current element which is the beginning from the beginning of the queue.

347
00:14:00,600 --> 00:14:00,840
Right.

348
00:14:00,840 --> 00:14:02,160
So all of these are already out.

349
00:14:02,160 --> 00:14:03,690
So only E is at the beginning.

350
00:14:03,690 --> 00:14:06,600
We take it from the queue and we put it to the output.

351
00:14:06,600 --> 00:14:13,080
And then we are going to check the neighbors of E which is C, D and f and C, D and f are already there

352
00:14:13,080 --> 00:14:15,330
in visited, so we don't add anything to the queue.

353
00:14:15,330 --> 00:14:18,630
Again we come over here, we see there is still one element in the queue.

354
00:14:18,630 --> 00:14:21,750
So we take it out, we shift it and we put it to the output.

355
00:14:21,750 --> 00:14:21,960
Right.

356
00:14:21,960 --> 00:14:23,250
We push it to the output array.

357
00:14:23,250 --> 00:14:27,540
And then for the neighbors of D, C and E are already there.

358
00:14:27,540 --> 00:14:31,950
So we don't add anything to the visited or um, object or to the queue.

359
00:14:31,950 --> 00:14:32,610
And we are done.

360
00:14:32,610 --> 00:14:38,700
So we come out and we just return this array over here which is A, B, F, C, E and d, and that is

361
00:14:38,700 --> 00:14:39,510
our output.

362
00:14:40,950 --> 00:14:46,860
Now when it comes to the time and space complexity, we can see that over here we are.

363
00:14:47,070 --> 00:14:49,380
What are the things that consume space?

364
00:14:49,380 --> 00:14:51,390
So one is this visited object.

365
00:14:51,390 --> 00:14:53,610
And then we have this output array.

366
00:14:53,610 --> 00:14:54,900
And then we have this queue.

367
00:14:54,900 --> 00:14:57,690
So these are the things that take additional space right.

368
00:14:57,690 --> 00:15:02,280
So you can see that the space complexity is O of V right.

369
00:15:02,280 --> 00:15:03,750
Which is the number of nodes.

370
00:15:03,750 --> 00:15:06,420
Again over here we have v elements in this array.

371
00:15:06,420 --> 00:15:09,810
Even if we were not asked to give the output as an array.

372
00:15:09,810 --> 00:15:12,270
And suppose we were not building this even then.

373
00:15:12,270 --> 00:15:16,020
Over here you can see that our visited object consumes V space, right?

374
00:15:16,020 --> 00:15:18,000
And the queue also the.

375
00:15:18,030 --> 00:15:22,500
In the worst case, as we have seen in the previous video, it can take up to v elements, right.

376
00:15:22,500 --> 00:15:25,440
So in that case also this also could consume v space.

377
00:15:25,440 --> 00:15:28,320
So the space complexity of this solution is O of V.

378
00:15:28,320 --> 00:15:30,210
And what about the time complexity.

379
00:15:30,210 --> 00:15:33,450
The time complexity of this solution is O of e plus v.

380
00:15:33,450 --> 00:15:33,960
Right.

381
00:15:33,960 --> 00:15:34,800
So why is that.

382
00:15:34,800 --> 00:15:39,960
So now over here you can see that we are visiting every node once right.

383
00:15:39,960 --> 00:15:41,130
So or every vertex once.

384
00:15:41,130 --> 00:15:44,010
So that's why we have v over here which is every vertex.

385
00:15:44,010 --> 00:15:47,340
And then when we have this for loop when we are checking the neighbors.

386
00:15:47,340 --> 00:15:50,220
Actually the neighbors of A are actually these edges, right.

387
00:15:50,220 --> 00:15:53,730
So the neighbors of A is a and b f and b.

388
00:15:53,730 --> 00:15:56,220
So that's indicated by these two edges.

389
00:15:56,220 --> 00:16:00,930
So again when we check the neighbors of c for example we go to b d and e right.

390
00:16:00,930 --> 00:16:02,610
So those are these edges right.

391
00:16:02,610 --> 00:16:08,310
So the um the time complexity over here will be a multiple of the number of edges which we have.

392
00:16:08,310 --> 00:16:12,630
So that's why we get that the time complexity of this solution is O of e plus v.