1
00:00:00,710 --> 00:00:01,700
Hi everyone!

2
00:00:01,700 --> 00:00:08,600
Now let's code the BFS traversal solution for this matrix over here, which is given or which is stored

3
00:00:08,600 --> 00:00:10,100
as an adjacency matrix.

4
00:00:10,100 --> 00:00:14,150
So over here we have the relationships right whether there are connections or not.

5
00:00:14,150 --> 00:00:16,910
And you can see that this is just a two dimensional array.

6
00:00:16,910 --> 00:00:22,160
And over here notice that we have an array where it's mentioned as vertices.

7
00:00:22,160 --> 00:00:26,810
So this will give us the vertices and the particular index where the vertex is.

8
00:00:26,810 --> 00:00:31,070
For example we have vertex b at index one right zero one.

9
00:00:31,070 --> 00:00:35,600
So that's how we know that this over here is the connections which are there from B.

10
00:00:35,870 --> 00:00:36,230
All right.

11
00:00:36,230 --> 00:00:39,920
And then we have the object over here which is called vertex indices.

12
00:00:39,920 --> 00:00:42,950
Now we have this object so that we can get this index.

13
00:00:42,950 --> 00:00:48,320
That is the index of b is equal to one, the index of e is equal to four etc. without always having

14
00:00:48,320 --> 00:00:49,730
to traverse this array over here.

15
00:00:49,730 --> 00:00:53,810
And that will help us to have a better time complexity for our solution.

16
00:00:53,810 --> 00:00:54,020
Right.

17
00:00:54,020 --> 00:00:59,090
So we just want to know the index of a particular node with constant time.

18
00:00:59,090 --> 00:01:01,310
So that's why we have this object over here.

19
00:01:01,310 --> 00:01:01,700
All right.

20
00:01:01,700 --> 00:01:04,640
So let's now go ahead and code the solution.

21
00:01:04,640 --> 00:01:08,420
So we will have a function let's call it BFS itself.

22
00:01:08,420 --> 00:01:12,020
So we have to have BFS and that's equal to function.

23
00:01:12,020 --> 00:01:14,300
And we will be passing in the graph.

24
00:01:15,290 --> 00:01:17,030
All right which is that adjacency matrix.

25
00:01:17,030 --> 00:01:18,860
And then we will say where to start.

26
00:01:19,220 --> 00:01:19,670
All right.

27
00:01:19,670 --> 00:01:22,670
So inside this function we will create an array.

28
00:01:22,670 --> 00:01:23,780
Let's call it output.

29
00:01:23,780 --> 00:01:25,910
So this will be an empty array right.

30
00:01:25,910 --> 00:01:28,490
So let's say const output is an empty array.

31
00:01:28,550 --> 00:01:31,730
And then finally we will just return this array over here.

32
00:01:31,730 --> 00:01:32,000
All right.

33
00:01:32,000 --> 00:01:34,070
So that's what we are trying to do.

34
00:01:34,070 --> 00:01:35,000
So return output.

35
00:01:35,000 --> 00:01:37,970
And then we will just call the BFS function over here.

36
00:01:37,970 --> 00:01:39,920
And we will pass the adjacency matrix.

37
00:01:39,920 --> 00:01:42,920
And we will mention where we want to start traversing it.

38
00:01:42,920 --> 00:01:44,600
So this is what we are trying to do.

39
00:01:44,600 --> 00:01:47,840
Now let's go ahead and complete this function over here BFS.

40
00:01:47,840 --> 00:01:54,020
So we also need a visited object to track whether we have visited a node or not.

41
00:01:54,020 --> 00:01:55,580
And we will also need a queue.

42
00:01:55,580 --> 00:01:55,760
Right.

43
00:01:55,760 --> 00:01:58,400
So let's say const queue is equal to.

44
00:01:58,400 --> 00:02:02,540
And then as we are starting at this right we are passing start a.

45
00:02:02,540 --> 00:02:08,420
So we know that we want to start traversing the graph at that node or that vertex.

46
00:02:08,420 --> 00:02:11,240
So we can pass it to the queue over here itself.

47
00:02:11,240 --> 00:02:14,930
Now whenever something is added to the queue, we mark it as visited.

48
00:02:14,930 --> 00:02:17,330
So we can say visited at start.

49
00:02:18,550 --> 00:02:20,020
Is equal to true.

50
00:02:21,310 --> 00:02:21,760
All right.

51
00:02:21,760 --> 00:02:24,400
Now we will have a while loop.

52
00:02:24,400 --> 00:02:29,740
So as long as something is there in the queue, we will keep looping through the while loop again and

53
00:02:29,740 --> 00:02:30,040
again.

54
00:02:30,040 --> 00:02:34,150
So while queue dot length greater than zero that's the condition.

55
00:02:34,150 --> 00:02:37,240
And again let me just have two variables over here.

56
00:02:37,240 --> 00:02:40,120
Let's call it current and current index.

57
00:02:42,030 --> 00:02:42,360
Right.

58
00:02:42,360 --> 00:02:46,560
So current will be the node that we are taking out at every point from the queue.

59
00:02:46,560 --> 00:02:51,480
And then we need to know its index right, which we will find using the vertex indices over here.

60
00:02:51,480 --> 00:02:51,660
Right.

61
00:02:51,660 --> 00:02:57,900
So we can find it, find its index so that we can immediately know at which um row we should take.

62
00:02:57,900 --> 00:02:58,110
Right.

63
00:02:58,110 --> 00:03:04,230
For example, if we take it as zero one, two three, if we if we have the node which is D, then immediately

64
00:03:04,230 --> 00:03:05,640
we get that the index is three.

65
00:03:05,640 --> 00:03:08,160
And then we can come over here 0123.

66
00:03:08,160 --> 00:03:10,980
And we get this array over here which represents its neighbors.

67
00:03:10,980 --> 00:03:13,020
So that's why we need current index over here.

68
00:03:13,200 --> 00:03:13,470
All right.

69
00:03:13,470 --> 00:03:17,850
So while queue dot length is greater than zero that means as long as something is there in the queue.

70
00:03:17,850 --> 00:03:22,410
And again remember over here we have implemented the queue as an array just to save time.

71
00:03:22,410 --> 00:03:24,840
So you need to mention this to your interviewer.

72
00:03:24,870 --> 00:03:30,810
Now ideally we should be implementing it as an as a linked list to get optimum time performance.

73
00:03:30,810 --> 00:03:30,960
Right.

74
00:03:30,960 --> 00:03:35,010
Because we are removing elements from the beginning of the queue and removing something from the beginning

75
00:03:35,010 --> 00:03:36,900
of an array is an O of n operation.

76
00:03:36,900 --> 00:03:41,700
But if we had implemented this queue as a linked list, that would be a constant time operation.

77
00:03:41,700 --> 00:03:42,210
All right.

78
00:03:42,210 --> 00:03:44,640
So let's come back to this while loop over here.

79
00:03:44,640 --> 00:03:49,830
Now while something is there in the queue, what we will do is we will say current is equal to q dot

80
00:03:49,830 --> 00:03:50,280
shift.

81
00:03:50,280 --> 00:03:52,980
So we are taking the first element from the queue.

82
00:03:53,010 --> 00:03:56,340
Now we are going to push this to our output array.

83
00:03:56,340 --> 00:03:59,910
So output dot push and let's just push current to it.

84
00:04:01,070 --> 00:04:01,490
All right.

85
00:04:01,490 --> 00:04:03,290
Now we are going to check its neighbors.

86
00:04:03,290 --> 00:04:03,530
Right.

87
00:04:03,530 --> 00:04:05,690
So for this we need to know the index.

88
00:04:05,690 --> 00:04:10,790
So current index is equal to vertex indices at current.

89
00:04:12,300 --> 00:04:12,540
Right.

90
00:04:12,540 --> 00:04:14,790
So we are using this object over here.

91
00:04:14,790 --> 00:04:20,370
We are passing the, the uh node A, B, C etc. as key over here.

92
00:04:20,370 --> 00:04:22,620
And we will get the index back as value.

93
00:04:22,620 --> 00:04:24,300
So that's what we have done over here.

94
00:04:24,300 --> 00:04:25,770
So we get the current index.

95
00:04:25,770 --> 00:04:27,870
Now we can just take its neighbors right.

96
00:04:27,870 --> 00:04:31,050
So we can say const neighbors which will be an array.

97
00:04:31,050 --> 00:04:31,230
Right.

98
00:04:31,230 --> 00:04:32,070
So neighbors.

99
00:04:33,250 --> 00:04:34,390
Is equal to.

100
00:04:34,390 --> 00:04:35,350
Graph.

101
00:04:37,590 --> 00:04:38,610
Current index.

102
00:04:40,410 --> 00:04:40,800
All right.

103
00:04:40,800 --> 00:04:46,050
So we will get one of these graphs, one of these arrays right as its neighbors depending on what the

104
00:04:46,050 --> 00:04:49,500
index is or what the node is which where we are at currently.

105
00:04:49,500 --> 00:04:50,850
So we get the neighbors.

106
00:04:50,850 --> 00:04:54,720
Now we have to loop through the neighbors and see whether it's already visited.

107
00:04:54,720 --> 00:04:56,670
And if not, we have to push it to the queue.

108
00:04:56,670 --> 00:04:58,110
So that's what we are doing over here.

109
00:04:58,110 --> 00:05:06,540
So for this let's use a for loop for let I is equal to zero I less than neighbors dot length.

110
00:05:07,660 --> 00:05:08,200
And I.

111
00:05:08,200 --> 00:05:09,010
Plus, plus.

112
00:05:11,150 --> 00:05:11,570
All right.

113
00:05:11,570 --> 00:05:13,100
So we are looping through it.

114
00:05:13,100 --> 00:05:17,540
And now let's say that we want to check whether the value is one or not.

115
00:05:17,540 --> 00:05:17,690
Right.

116
00:05:17,690 --> 00:05:22,820
So if there is a one then only we need to be concerned with that particular neighbor because a one indicates

117
00:05:22,820 --> 00:05:25,190
that yes, that particular node has a neighbor.

118
00:05:25,190 --> 00:05:26,990
And again it depends on where it is.

119
00:05:26,990 --> 00:05:27,170
Right.

120
00:05:27,170 --> 00:05:32,180
For example, over here, if we have a as the current node, then this is the array that we would have

121
00:05:32,180 --> 00:05:33,080
got as neighbors.

122
00:05:33,080 --> 00:05:35,090
Now we see that there is a one over here.

123
00:05:35,090 --> 00:05:38,810
So at this point I will be zero one right I will be one.

124
00:05:38,810 --> 00:05:44,630
So I is equal to one means that's node B because we know the um the indices over here.

125
00:05:44,630 --> 00:05:44,780
Right.

126
00:05:44,780 --> 00:05:45,920
So this is zero.

127
00:05:45,920 --> 00:05:46,490
This is one.

128
00:05:46,490 --> 00:05:48,710
So we know that A has a connection with B.

129
00:05:48,710 --> 00:05:51,560
So that's how we make that connection over here.

130
00:05:51,560 --> 00:05:55,250
We have to check whether neighbors at I is equal to one.

131
00:05:55,250 --> 00:05:56,060
So let's do that.

132
00:05:56,060 --> 00:06:02,810
If neighbors at I if this is equal to one and if it's not visited right.

133
00:06:02,810 --> 00:06:04,640
So we have to know whether it's visited or not.

134
00:06:04,640 --> 00:06:06,710
So not visited.

135
00:06:06,710 --> 00:06:09,530
And over here we cannot pass the index.

136
00:06:09,530 --> 00:06:09,740
Right.

137
00:06:09,740 --> 00:06:13,040
So over here neighbors I will be just 0 or 1.

138
00:06:13,040 --> 00:06:14,930
And I will give us the index.

139
00:06:14,930 --> 00:06:15,170
Right.

140
00:06:15,170 --> 00:06:22,550
This is the index of 012345 which is the same index as we have for this vertices array 012345.

141
00:06:22,550 --> 00:06:27,860
But we cannot just but in the visited array like in the visited object over here we are.

142
00:06:27,860 --> 00:06:29,300
We are not passing the index right.

143
00:06:29,300 --> 00:06:31,880
We are passing the the node the value.

144
00:06:31,880 --> 00:06:34,760
So we need to check whether visited.

145
00:06:34,760 --> 00:06:38,630
So for this we have to use vertices this array over here vertices right.

146
00:06:38,630 --> 00:06:40,790
So if we say vertices.

147
00:06:42,460 --> 00:06:44,350
Which is an array at I.

148
00:06:44,950 --> 00:06:50,920
So that will give us, for example, if the index is two, as we saw over here, we see that we have

149
00:06:50,920 --> 00:06:52,690
the index is one as we saw over here.

150
00:06:52,690 --> 00:06:55,480
So when index is one we see that we have a one.

151
00:06:55,480 --> 00:06:59,710
So neighbors at one is equal to true when we have this array right.

152
00:06:59,710 --> 00:07:01,390
So we have this okay.

153
00:07:01,390 --> 00:07:03,970
And then we are going to check vertices at one.

154
00:07:03,970 --> 00:07:05,980
So vertices at one will give us b.

155
00:07:05,980 --> 00:07:09,430
And then we will check whether b is there in the visited object or not.

156
00:07:09,430 --> 00:07:15,010
So if it is not there, then we know that we have to push it to the queue and we have to mark it as

157
00:07:15,010 --> 00:07:15,430
visited.

158
00:07:15,430 --> 00:07:16,720
So let's do that over here.

159
00:07:16,720 --> 00:07:20,530
Queue dot push and we are going to push vertices.

160
00:07:22,050 --> 00:07:26,460
At I, which in the example that we just now discussed is B, right.

161
00:07:26,460 --> 00:07:31,020
And then we are going to mark it visit as true visited at vertices at I.

162
00:07:33,930 --> 00:07:38,400
Will be marked as true because we have pushed it to the Q so what do we push to the Q?

163
00:07:38,430 --> 00:07:40,680
We mark it as visited and that's it.

164
00:07:40,680 --> 00:07:43,650
So we are done with our, um, solution.

165
00:07:43,650 --> 00:07:43,920
Right.

166
00:07:43,920 --> 00:07:49,230
So whatever is uh, where whenever there is a neighbor which is not visited, we push it to the queue

167
00:07:49,230 --> 00:07:51,690
and then we again come to the while loop.

168
00:07:51,690 --> 00:07:55,680
If there is something in the queue we take from its beginning, that is, we shift and then we push

169
00:07:55,680 --> 00:07:57,420
it to the output and that's it.

170
00:07:57,420 --> 00:07:58,950
So we get our output.

171
00:07:58,950 --> 00:08:04,110
So now let's just run this, and then we will walk through the code and see what's happening over here.

172
00:08:04,110 --> 00:08:05,910
So let me just run this now.

173
00:08:06,630 --> 00:08:09,600
So we run it.

174
00:08:10,880 --> 00:08:11,480
See.

175
00:08:12,650 --> 00:08:14,690
Visited is not okay.

176
00:08:14,690 --> 00:08:17,570
So there is a spelling mistake.

177
00:08:17,570 --> 00:08:18,680
V I s t e d.

178
00:08:18,680 --> 00:08:18,890
Right?

179
00:08:18,890 --> 00:08:21,860
So let's just quickly check where we have made that mistake.

180
00:08:22,190 --> 00:08:23,720
Uh, we have visited.

181
00:08:26,470 --> 00:08:27,070
Visited.

182
00:08:27,160 --> 00:08:27,640
All right.

183
00:08:27,640 --> 00:08:28,960
So it should be visited.

184
00:08:28,960 --> 00:08:30,040
So that's the spelling mistake.

185
00:08:30,040 --> 00:08:30,580
All right.

186
00:08:30,580 --> 00:08:31,360
So.

187
00:08:32,180 --> 00:08:33,860
We have visited over here.

188
00:08:35,170 --> 00:08:35,470
All right.

189
00:08:35,500 --> 00:08:36,280
Now it should work.

190
00:08:36,280 --> 00:08:37,090
So let's try.

191
00:08:37,090 --> 00:08:37,510
Yes.

192
00:08:37,510 --> 00:08:39,040
And we get our solution.

193
00:08:39,040 --> 00:08:41,530
We have a, B, F, C, E and d.

194
00:08:41,560 --> 00:08:45,040
Now let's quickly walk through the code and see what's happening over here.

195
00:08:46,260 --> 00:08:46,620
For this.

196
00:08:46,620 --> 00:08:49,710
First, let's try to construct or visualize.

197
00:08:49,710 --> 00:08:53,550
Basically, we're just trying to visualize the graph from what we have over here.

198
00:08:55,220 --> 00:08:55,700
For this.

199
00:08:55,700 --> 00:08:57,110
Let me just take a pen.

200
00:08:57,920 --> 00:08:58,700
All right.

201
00:08:58,700 --> 00:09:01,160
So let's quickly visualize the graph.

202
00:09:01,160 --> 00:09:05,000
So we have a b c d e and f as the vertices.

203
00:09:05,030 --> 00:09:06,380
Now let's look at a.

204
00:09:06,380 --> 00:09:11,630
So this is the array for a right which shows the connections or the neighbors for a.

205
00:09:11,630 --> 00:09:15,170
So we have a over here and it has a connection with B.

206
00:09:15,170 --> 00:09:16,190
This indicates B right.

207
00:09:16,190 --> 00:09:19,820
So we have a b and then we have c d e and f.

208
00:09:19,820 --> 00:09:21,410
So we have a and f.

209
00:09:21,410 --> 00:09:22,820
So let me just write it over here.

210
00:09:22,850 --> 00:09:24,260
Now let's check for b.

211
00:09:24,290 --> 00:09:27,680
B is connected to a which we already have a b c.

212
00:09:27,680 --> 00:09:29,660
So b is connected to C as well.

213
00:09:30,350 --> 00:09:33,530
D, E, and f, so B is connected to F as well.

214
00:09:33,530 --> 00:09:36,110
So let me just write that connection over here like this.

215
00:09:36,140 --> 00:09:37,220
Now let's look at C.

216
00:09:37,220 --> 00:09:38,810
So C is connected to B.

217
00:09:38,810 --> 00:09:41,360
We have that connection c d.

218
00:09:41,390 --> 00:09:42,200
This is d.

219
00:09:42,620 --> 00:09:46,550
So c is connected to d and c is connected to e.

220
00:09:46,550 --> 00:09:49,100
So let's write e over here.

221
00:09:50,680 --> 00:09:51,760
Now let's look at D.

222
00:09:51,790 --> 00:09:52,450
This is D.

223
00:09:52,480 --> 00:09:55,870
So d is connected to a b c which is already there.

224
00:09:55,870 --> 00:09:58,030
Then you have d e.

225
00:09:58,240 --> 00:09:59,980
So d is connected to e as well.

226
00:09:59,980 --> 00:10:01,180
So we have this connection.

227
00:10:01,180 --> 00:10:02,230
Now what about this.

228
00:10:02,230 --> 00:10:03,400
This is e.

229
00:10:03,400 --> 00:10:03,970
This is e.

230
00:10:03,970 --> 00:10:07,900
So e is connected to a b c so e is connected to c.

231
00:10:07,930 --> 00:10:13,090
We already have that and e is connected to d we have that and e is connected to f.

232
00:10:13,090 --> 00:10:15,130
So we need to make this connection over here.

233
00:10:15,130 --> 00:10:16,630
So let's just write it like this.

234
00:10:16,630 --> 00:10:19,750
And finally we check that f f has a connection with A and b.

235
00:10:19,780 --> 00:10:21,340
We already have that over here.

236
00:10:21,340 --> 00:10:23,920
And c d and with e so we already have that.

237
00:10:23,920 --> 00:10:24,820
So this is our graph.

238
00:10:24,820 --> 00:10:27,310
So this is how we can visualize our graph.

239
00:10:27,310 --> 00:10:31,900
Now let's look at um the function over here Trav BFS which we have written.

240
00:10:31,900 --> 00:10:34,660
Let's see what happens over here while we execute it.

241
00:10:34,660 --> 00:10:36,640
So let's just take this down.

242
00:10:38,180 --> 00:10:38,990
A little bit.

243
00:10:39,470 --> 00:10:39,950
Okay.

244
00:10:39,950 --> 00:10:42,170
So let's take a little bit more.

245
00:10:44,030 --> 00:10:47,270
All right, so now let me just clear this up.

246
00:10:51,700 --> 00:10:53,050
Now let's get started.

247
00:10:53,050 --> 00:10:56,530
So we are traversing this graph and we are passing.

248
00:10:57,300 --> 00:10:57,840
Add to it.

249
00:10:57,840 --> 00:10:59,220
So that's what we did.

250
00:10:59,220 --> 00:11:03,630
So let me just also make probably make this a little bit smaller so we can see the screen better.

251
00:11:08,550 --> 00:11:09,270
All right.

252
00:11:12,090 --> 00:11:12,510
Okay.

253
00:11:12,510 --> 00:11:13,260
So we have that.

254
00:11:13,260 --> 00:11:14,550
So let's now continue.

255
00:11:14,550 --> 00:11:15,540
So what happens.

256
00:11:15,540 --> 00:11:17,400
We have passed this graph over here.

257
00:11:17,400 --> 00:11:18,660
And we start at a.

258
00:11:18,690 --> 00:11:20,550
Now we have an output array.

259
00:11:20,550 --> 00:11:22,410
So let this be our output.

260
00:11:23,160 --> 00:11:24,840
Which is at this point empty.

261
00:11:24,840 --> 00:11:26,190
And then we have visited.

262
00:11:26,190 --> 00:11:28,260
So let's just track visited over here.

263
00:11:29,820 --> 00:11:31,770
And then we have a queue, right?

264
00:11:32,010 --> 00:11:32,610
We have a queue.

265
00:11:32,610 --> 00:11:33,990
Let me just write that over here.

266
00:11:33,990 --> 00:11:36,720
We have a queue and we put the start into the queue.

267
00:11:36,720 --> 00:11:37,950
So we have a over here.

268
00:11:38,370 --> 00:11:41,850
Now we come over here we mark it as visited right.

269
00:11:41,850 --> 00:11:43,140
We mark a as visited.

270
00:11:43,140 --> 00:11:45,000
So let me just write a over here.

271
00:11:45,000 --> 00:11:46,230
And then we say true.

272
00:11:46,260 --> 00:11:48,090
That's how our object looks like.

273
00:11:48,570 --> 00:11:51,810
And then we check whether there is something in the queue.

274
00:11:51,810 --> 00:11:54,300
At this point we see that yes A is over there.

275
00:11:54,300 --> 00:11:55,590
So we take it out.

276
00:11:55,590 --> 00:11:58,110
So we shift it and then we put it to the output array.

277
00:11:58,110 --> 00:11:59,190
So we have a over here.

278
00:11:59,400 --> 00:12:00,720
Now what do we do.

279
00:12:00,720 --> 00:12:07,440
We find the current index from uh vertex indices where the current is a.

280
00:12:07,440 --> 00:12:08,970
So current has the value a.

281
00:12:09,000 --> 00:12:15,660
Now in using the object where we stored the key value pair, where the key is the the node value.

282
00:12:15,660 --> 00:12:17,070
And then we get the index right.

283
00:12:17,070 --> 00:12:20,670
So from this we will get that current index at this point is equal to zero.

284
00:12:20,670 --> 00:12:21,090
All right.

285
00:12:21,090 --> 00:12:27,030
So now we are just going to find the neighbors from this adjacency matrix at index zero.

286
00:12:27,030 --> 00:12:27,270
Right.

287
00:12:27,270 --> 00:12:28,890
So that's what we're doing over here.

288
00:12:28,920 --> 00:12:29,970
Graph at zero.

289
00:12:29,970 --> 00:12:34,170
So that gives us this array over here 010001.

290
00:12:34,170 --> 00:12:34,620
All right.

291
00:12:34,620 --> 00:12:36,480
Now we are going to loop through this.

292
00:12:36,480 --> 00:12:41,940
Now initially over here when I is equal to zero neighbors at zero is zero.

293
00:12:41,940 --> 00:12:44,910
So it doesn't pass this condition right.

294
00:12:44,910 --> 00:12:46,140
So we don't go inside.

295
00:12:46,140 --> 00:12:48,060
So I becomes one at this point.

296
00:12:48,060 --> 00:12:48,330
Yes.

297
00:12:48,330 --> 00:12:49,410
This is equal to one.

298
00:12:49,410 --> 00:12:54,030
Now we are going to check whether vertices at one vertices at one gives us b.

299
00:12:54,030 --> 00:12:54,270
Right.

300
00:12:54,270 --> 00:12:56,010
Because we have our vertices array.

301
00:12:56,010 --> 00:12:57,030
So this is equal to b.

302
00:12:57,030 --> 00:12:58,590
And we are going to check whether b is there.

303
00:12:58,590 --> 00:13:00,780
In visited we see that it is not there.

304
00:13:00,780 --> 00:13:03,210
And neighbors at one is also equal to one.

305
00:13:03,210 --> 00:13:05,760
So yes, we come inside and we push it to the queue.

306
00:13:05,760 --> 00:13:06,090
Right.

307
00:13:06,090 --> 00:13:10,140
So we push B to the queue and we mark it as visited.

308
00:13:10,140 --> 00:13:10,350
Right.

309
00:13:10,350 --> 00:13:13,230
So we have B over here as well as visited.

310
00:13:13,230 --> 00:13:16,050
And again it's B and then the value is true.

311
00:13:16,050 --> 00:13:20,370
So I'm not just I'm just writing B over here at this point so that it's easy for us to track.

312
00:13:20,370 --> 00:13:20,820
All right.

313
00:13:20,820 --> 00:13:26,550
So after this again we come to the next uh value of I which is equal to two.

314
00:13:26,550 --> 00:13:26,820
Right.

315
00:13:26,820 --> 00:13:29,160
Again it's zero three, it's zero four, it's zero.

316
00:13:29,160 --> 00:13:30,660
And then at I is equal to five.

317
00:13:30,660 --> 00:13:33,390
Again we have neighbors at five is equal to one.

318
00:13:33,390 --> 00:13:34,290
So this is true.

319
00:13:34,290 --> 00:13:42,630
And over here when the index is five at uh vertices five we will get a b c that the array was a b c

320
00:13:42,660 --> 00:13:45,030
d e right a b c d e f.

321
00:13:45,030 --> 00:13:46,290
So we'll get f over here.

322
00:13:46,290 --> 00:13:48,420
And we are checking whether f is there over here.

323
00:13:48,420 --> 00:13:49,140
It's not there.

324
00:13:49,140 --> 00:13:51,840
So we will put f also into the queue.

325
00:13:51,840 --> 00:13:54,870
And then we will put f over here in the visited object.

326
00:13:54,870 --> 00:13:56,370
That's what is happening over here.

327
00:13:56,370 --> 00:13:58,350
Now we are coming out of the for loop.

328
00:13:58,350 --> 00:13:58,650
Again.

329
00:13:58,650 --> 00:14:00,480
We check whether something is there in the queue.

330
00:14:00,510 --> 00:14:01,680
Yes it's there right.

331
00:14:01,680 --> 00:14:05,250
So let me just check change the pen and we take from the beginning.

332
00:14:05,250 --> 00:14:05,430
Right.

333
00:14:05,430 --> 00:14:09,750
We are shifting and then we put it to the output array and we are going to check its neighbors.

334
00:14:09,750 --> 00:14:12,360
So for that we come to this part over here.

335
00:14:12,360 --> 00:14:12,750
Right.

336
00:14:12,750 --> 00:14:15,900
So that's done over here we get the index which is one.

337
00:14:15,900 --> 00:14:19,560
And then we we check graph at one which gives us this array over here.

338
00:14:19,560 --> 00:14:24,150
Now we get the neighbors one which is a and c and f.

339
00:14:24,150 --> 00:14:26,430
So that's a c and f right.

340
00:14:26,430 --> 00:14:29,760
So among these a and f are already there in the visited array.

341
00:14:29,760 --> 00:14:31,080
So just c is not there.

342
00:14:31,080 --> 00:14:32,160
So what do we do.

343
00:14:32,160 --> 00:14:36,330
We push C to the queue and we mark C as visited.

344
00:14:36,330 --> 00:14:39,420
So that's it right now again the same thing is repeated.

345
00:14:39,420 --> 00:14:41,040
We come back to this place.

346
00:14:41,040 --> 00:14:42,570
We see things are there in the queue.

347
00:14:42,600 --> 00:14:44,250
We take out from the beginning.

348
00:14:44,250 --> 00:14:45,420
We put it over here.

349
00:14:45,420 --> 00:14:46,830
So we have f over here.

350
00:14:46,830 --> 00:14:53,670
Now we have F, we get the index as five and then we come over here we get these are the neighbors of

351
00:14:53,670 --> 00:14:57,780
F, so we have a B and E right A, b and e.

352
00:14:57,780 --> 00:15:01,800
So we see that a and B are already there in the queue or are already there visited.

353
00:15:01,800 --> 00:15:04,140
So we just add e to the queue.

354
00:15:04,140 --> 00:15:04,770
Right.

355
00:15:04,770 --> 00:15:06,990
And we mark E as visited.

356
00:15:06,990 --> 00:15:10,320
We add it to the visited object and then the same thing is repeated.

357
00:15:10,320 --> 00:15:12,120
We take out from the queue which is C.

358
00:15:12,210 --> 00:15:14,790
Now we check the neighbors of C, right.

359
00:15:14,790 --> 00:15:19,500
So over here we can see it has b and then d and e right.

360
00:15:19,500 --> 00:15:22,710
So among these b and d are already there over here.

361
00:15:22,710 --> 00:15:27,690
So we just add d to the visited uh object and we push it to the queue.

362
00:15:27,690 --> 00:15:30,540
Again the we come to the while loop.

363
00:15:30,540 --> 00:15:32,160
We see there are things in the queue.

364
00:15:32,190 --> 00:15:38,040
We take out E, we put it to the output array, and then we check the neighbors of E which is over here.

365
00:15:38,040 --> 00:15:38,490
Right.

366
00:15:38,490 --> 00:15:46,080
So we see that it has c, D and f and c, d and f are already there in the visited object.

367
00:15:46,080 --> 00:15:47,850
So we don't push anything to the queue.

368
00:15:47,850 --> 00:15:53,370
And again we come to this check over here we see that yes queue dot length is one at this point which

369
00:15:53,370 --> 00:15:54,300
is greater than zero.

370
00:15:54,300 --> 00:15:57,060
So we come inside the while loop and we take D out.

371
00:15:57,060 --> 00:15:58,740
We put it to the output array.

372
00:15:58,740 --> 00:16:05,820
And again we are checking the neighbors of D from here right A, B, C and d we get 001010, which is

373
00:16:05,820 --> 00:16:12,330
indicating that its neighbors are C and E, right C and E, so C and E are already there over here.

374
00:16:12,330 --> 00:16:14,640
So we don't put anything to the queue and we are done.

375
00:16:14,640 --> 00:16:18,360
We come out of the while loop because at this point the length of the queue is zero.

376
00:16:18,360 --> 00:16:19,830
And this is our output.

377
00:16:19,830 --> 00:16:22,200
Now let's check the output which we got over here.

378
00:16:23,620 --> 00:16:24,970
You can see it's the same thing, right?

379
00:16:24,970 --> 00:16:27,310
A, B, F, C, E and d.

380
00:16:27,310 --> 00:16:29,050
So that is the output over here.

381
00:16:29,050 --> 00:16:31,060
So that is how our function works.

382
00:16:31,570 --> 00:16:35,560
Let's now quickly check the time and space complexity of this solution.

383
00:16:35,560 --> 00:16:42,250
So the time complexity for breadth first search when it is when the graph is implemented as an adjacency

384
00:16:42,250 --> 00:16:48,280
matrix, is of the order of O of V square, it's of the order of v square, and the space complexity

385
00:16:48,280 --> 00:16:49,450
is of the order of v.

386
00:16:49,480 --> 00:16:51,130
Now let's quickly understand this.

387
00:16:51,130 --> 00:16:55,540
Now especially, let's see why the time complexity of is of the order of V square.

388
00:16:55,720 --> 00:17:01,480
Over here we have this while loop, and this while loop over here will execute v times right.

389
00:17:01,480 --> 00:17:03,730
So this will do v number of operations.

390
00:17:03,730 --> 00:17:04,780
Now why is that.

391
00:17:04,780 --> 00:17:08,260
So this will do operations as long as something is there in the queue.

392
00:17:08,260 --> 00:17:08,590
Right.

393
00:17:08,590 --> 00:17:12,340
And we are taking elements from the queue and putting it to the output array.

394
00:17:12,340 --> 00:17:13,690
So that's what we are doing over here.

395
00:17:13,690 --> 00:17:17,620
So every vertex will at some point come into the queue.

396
00:17:17,620 --> 00:17:17,830
Right.

397
00:17:17,830 --> 00:17:22,810
So I'm saying at some point not at once but at some point definitely it will come into the queue.

398
00:17:22,810 --> 00:17:27,670
So that's why we can say that this while loop over here will do V operations.

399
00:17:27,670 --> 00:17:29,260
So we have V operations over here.

400
00:17:29,740 --> 00:17:31,480
And then we have this for loop over here.

401
00:17:31,480 --> 00:17:31,960
Right.

402
00:17:32,080 --> 00:17:34,060
How many times will this for loop operate.

403
00:17:34,060 --> 00:17:34,600
Now.

404
00:17:34,600 --> 00:17:39,160
Because our graph is represented or stored as an adjacency matrix.

405
00:17:39,160 --> 00:17:45,910
Over here you can see that irrespective of whether a vertex has neighbours or not, for each neighbour

406
00:17:45,910 --> 00:17:47,080
this will run.

407
00:17:47,080 --> 00:17:48,640
This will do V operations right.

408
00:17:48,640 --> 00:17:50,500
For example, let's take f.

409
00:17:50,500 --> 00:17:51,280
This is f right.

410
00:17:51,280 --> 00:17:53,680
This is f in our adjacency matrix.

411
00:17:53,680 --> 00:17:57,280
So you can see f has only three neighbours A, b and e.

412
00:17:57,280 --> 00:18:02,770
But even then the size of this array over here is still six which is equal to v right.

413
00:18:02,770 --> 00:18:09,310
So this for loop will operate v times irrespective of whether a vertex has neighbours or not.

414
00:18:09,310 --> 00:18:16,210
So for each of these v operations that is for each of these let me just write that for each of these

415
00:18:16,240 --> 00:18:21,610
V operations we will do again V operations over here because we are storing the graph as a adjacency

416
00:18:21,610 --> 00:18:22,240
matrix.

417
00:18:22,240 --> 00:18:27,580
So that is why the time complexity is O of v into v or o of v square.

418
00:18:27,580 --> 00:18:29,650
Now what about the space complexity?

419
00:18:29,650 --> 00:18:33,010
The space complexity is O of V because of multiple reasons.

420
00:18:33,010 --> 00:18:37,600
First of all, we are creating this output array which will have v elements, right?

421
00:18:37,600 --> 00:18:39,730
So v is the number of nodes or vertices.

422
00:18:39,730 --> 00:18:41,080
So that is one reason.

423
00:18:41,080 --> 00:18:47,020
Now even if we did not have the output array, we still have this visited object which will have v number

424
00:18:47,020 --> 00:18:47,950
of elements.

425
00:18:47,950 --> 00:18:48,190
Right.

426
00:18:48,190 --> 00:18:49,120
Because there are v nodes.

427
00:18:49,120 --> 00:18:51,280
So this also will take v space.

428
00:18:51,280 --> 00:18:53,080
And then we have the queue right.

429
00:18:53,080 --> 00:18:53,440
The queue.

430
00:18:53,440 --> 00:18:59,050
Also in the worst case like for example if the graph is something like this you have a then b, c,

431
00:18:59,080 --> 00:19:01,210
d, e and f in this manner.

432
00:19:01,780 --> 00:19:03,340
Then at one point.

433
00:19:03,340 --> 00:19:10,180
So at one point let me write that at one point, or at the same time, there can be of the order of

434
00:19:10,180 --> 00:19:11,410
v elements in the queue.

435
00:19:11,410 --> 00:19:11,620
Right.

436
00:19:11,620 --> 00:19:14,380
So that's the worst case in terms of space utilization.

437
00:19:14,380 --> 00:19:15,940
So that's why we have that.

438
00:19:15,940 --> 00:19:19,030
The space complexity of this solution is O of V.

439
00:19:19,060 --> 00:19:25,570
Now let's quickly compare this and contrast this with the adjacency list implementation of the graph.

440
00:19:25,570 --> 00:19:30,160
So in this case the time complexity we have seen is O of v plus e.

441
00:19:31,610 --> 00:19:34,310
And the space complexity is O of V.

442
00:19:34,370 --> 00:19:37,970
Now y is the time complexity over here O of v plus e.

443
00:19:38,000 --> 00:19:40,370
That's because again over here we have a while loop.

444
00:19:40,370 --> 00:19:42,440
So that will do V operations.

445
00:19:42,440 --> 00:19:42,830
Right.

446
00:19:42,830 --> 00:19:45,050
But inside the while loop we have a for loop.

447
00:19:45,050 --> 00:19:48,650
But over here it will not do V operations for every neighbor.

448
00:19:48,650 --> 00:19:49,790
It will for every node.

449
00:19:49,790 --> 00:19:52,400
It will depend on the number of neighbors it has right.

450
00:19:52,400 --> 00:19:59,210
For example, if you have a you have a then let me just write that over here B, c, D, e and f.

451
00:19:59,210 --> 00:20:00,890
So we have the nodes over here.

452
00:20:01,310 --> 00:20:03,050
Now we have a over here.

453
00:20:03,050 --> 00:20:05,150
So A has only two neighbors right.

454
00:20:05,150 --> 00:20:06,800
So over here this for loop.

455
00:20:06,800 --> 00:20:10,460
When the current node is a it will I it will iterate two times.

456
00:20:10,460 --> 00:20:12,500
Now for B it will do 123.

457
00:20:12,500 --> 00:20:13,790
It will do it three times.

458
00:20:13,790 --> 00:20:15,950
For C it will do one two, three.

459
00:20:15,950 --> 00:20:17,690
So that's three times for C.

460
00:20:17,720 --> 00:20:19,940
For D it will do one, two two times.

461
00:20:19,940 --> 00:20:20,420
Right.

462
00:20:20,420 --> 00:20:23,300
For E it will do one, two, three, three times.

463
00:20:23,630 --> 00:20:28,580
And for F it will do three iterations one, two, three because it has three neighbors.

464
00:20:28,580 --> 00:20:33,440
Now if we sum this up we'll get two plus three, five and then three plus three plus two.

465
00:20:33,440 --> 00:20:35,180
This is ten plus three plus three.

466
00:20:35,180 --> 00:20:37,040
This the sum over here is 16.

467
00:20:37,040 --> 00:20:39,470
And you will see that when we drew this right.

468
00:20:39,470 --> 00:20:41,960
When we visualize this this has eight edges.

469
00:20:41,960 --> 00:20:45,470
So this 16 over here is nothing but two into the number of edges.

470
00:20:45,590 --> 00:20:46,760
And that's happening.

471
00:20:46,760 --> 00:20:49,130
So because this is a undirected graph.

472
00:20:49,130 --> 00:20:54,020
So if there is a edge between A and B that will be counted over here as well as over here.

473
00:20:54,020 --> 00:20:58,040
So that's why if we sum this up we will get two into E which is equal to 16.

474
00:20:58,040 --> 00:21:03,230
So that is why we say that the time complexity is this v plus this two into e.

475
00:21:03,230 --> 00:21:04,430
And this is just a constant.

476
00:21:04,430 --> 00:21:05,780
So we can just avoid this.

477
00:21:05,780 --> 00:21:09,950
So that's why over here we get the time complexity as O of v plus e.