1
00:00:00,870 --> 00:00:02,010
Welcome back.

2
00:00:02,010 --> 00:00:08,340
In this video, let's discuss breadth first search or breadth first traversal, where the graph which

3
00:00:08,340 --> 00:00:11,760
is given to us is stored as an adjacency matrix.

4
00:00:11,760 --> 00:00:16,050
So this is the case the graph is stored as an adjacency matrix.

5
00:00:16,050 --> 00:00:17,820
So this is the graph over here.

6
00:00:17,820 --> 00:00:22,410
Now let's visualize this graph as an adjacency matrix like this right.

7
00:00:22,410 --> 00:00:26,070
So we have these six nodes a b c d e f.

8
00:00:26,070 --> 00:00:29,100
And then we have a b c d e f over here as well.

9
00:00:29,100 --> 00:00:32,130
And then each of these is going to be an array.

10
00:00:32,130 --> 00:00:32,460
Right.

11
00:00:32,460 --> 00:00:35,070
So let's try to write out this adjacency matrix.

12
00:00:35,070 --> 00:00:40,200
So this is how we are going to code this or this is how it's going to be stored in our code.

13
00:00:40,200 --> 00:00:40,650
All right.

14
00:00:40,650 --> 00:00:42,750
So this is adjacency adjacency matrix.

15
00:00:42,750 --> 00:00:44,880
Now this is the zeroth index.

16
00:00:44,880 --> 00:00:46,080
This is index one.

17
00:00:46,080 --> 00:00:49,980
This is index two index three index four index five.

18
00:00:49,980 --> 00:00:51,600
In this array over here.

19
00:00:51,600 --> 00:00:56,850
Now at the zeroth and index in this array we are going to have this array over here.

20
00:00:56,850 --> 00:00:57,330
All right.

21
00:00:57,330 --> 00:01:02,040
So let's just write that out over here 010001.

22
00:01:03,780 --> 00:01:04,140
All right.

23
00:01:04,140 --> 00:01:05,340
So what does this mean.

24
00:01:05,340 --> 00:01:07,950
So we don't have a connection between A and A.

25
00:01:07,950 --> 00:01:09,330
That's why we have a zero over here.

26
00:01:09,330 --> 00:01:11,340
We have a connection between A and B.

27
00:01:11,340 --> 00:01:14,370
That's why we have a one over here which is this connection over here.

28
00:01:14,370 --> 00:01:18,330
We don't have any connection between A and C, A and D and A and E.

29
00:01:18,360 --> 00:01:20,430
But then there is a connection between a and F.

30
00:01:20,430 --> 00:01:21,570
So we have a one over here.

31
00:01:21,570 --> 00:01:22,980
And that is this one over here.

32
00:01:22,980 --> 00:01:26,340
So this is how the adjacency matrix is going to be stored.

33
00:01:26,340 --> 00:01:26,730
Right.

34
00:01:26,730 --> 00:01:28,500
So this is the visualization of it.

35
00:01:28,500 --> 00:01:32,640
And in the code we will have just an array of arrays or a 2D array.

36
00:01:32,850 --> 00:01:36,480
Now what about the next element in this adjacency matrix array.

37
00:01:36,480 --> 00:01:41,190
It will be this array over here which is 101001.

38
00:01:41,190 --> 00:01:41,460
Right.

39
00:01:41,460 --> 00:01:42,690
So let's write that over here.

40
00:01:43,200 --> 00:01:46,200
And again these ones represent the connections.

41
00:01:46,200 --> 00:01:48,570
So there is a connection between B and A.

42
00:01:48,570 --> 00:01:52,500
There is a connection between B and C which is this connection over here.

43
00:01:52,500 --> 00:01:54,570
And then there is a connection between b and f.

44
00:01:54,570 --> 00:01:56,280
So that is this connection over here.

45
00:01:56,280 --> 00:02:01,170
Now similarly the next element in this array will be this array.

46
00:02:01,170 --> 00:02:01,440
Right.

47
00:02:01,440 --> 00:02:02,850
So that would be this array.

48
00:02:02,850 --> 00:02:06,600
And that is 010110.

49
00:02:06,600 --> 00:02:09,330
And then let's just write these three more elements.

50
00:02:09,330 --> 00:02:12,030
So we have 001010.

51
00:02:12,120 --> 00:02:15,990
And then we have 001101.

52
00:02:15,990 --> 00:02:19,170
And finally we have 110010.

53
00:02:19,170 --> 00:02:22,350
So this is going to be the adjacency matrix right.

54
00:02:22,350 --> 00:02:26,910
So this is different from the adjacency list which we saw in the previous videos.

55
00:02:26,910 --> 00:02:27,570
All right.

56
00:02:27,570 --> 00:02:31,650
So again this is this adjacency matrix is an array of arrays.

57
00:02:31,650 --> 00:02:33,300
So these are the elements over here.

58
00:02:33,300 --> 00:02:40,920
Now you can notice that at the zeroth index in this array this adjacency matrix array we have this element.

59
00:02:40,920 --> 00:02:48,420
So this element which is an array represents the neighbors of the node a right.

60
00:02:48,420 --> 00:02:51,390
So that is how the adjacency matrix is stored.

61
00:02:51,390 --> 00:02:58,560
Now let's go ahead and look at how we can implement BFS for a graph which is stored as an adjacency

62
00:02:58,560 --> 00:02:59,130
matrix.

63
00:02:59,130 --> 00:03:00,450
So this is the graph.

64
00:03:00,450 --> 00:03:02,970
Now the algorithm is going to be the same.

65
00:03:02,970 --> 00:03:05,160
We are going to use a queue for BFS.

66
00:03:05,160 --> 00:03:06,630
And we start somewhere.

67
00:03:06,630 --> 00:03:07,980
We push that to the queue.

68
00:03:07,980 --> 00:03:12,840
And then we are going to have this while loop which is the same as we saw in the previous video.

69
00:03:12,840 --> 00:03:17,520
While there is something in the queue, we are going to do these steps which is dequeue from the queue,

70
00:03:17,520 --> 00:03:21,360
push it to the output array and then enqueue the unvisited neighbors.

71
00:03:21,360 --> 00:03:25,800
Now the only difference is how we are going to do this is going to change, right?

72
00:03:25,890 --> 00:03:31,920
How we are going to enqueue unvisited neighbors is going to change, because at this point we have an

73
00:03:31,920 --> 00:03:33,180
adjacency matrix.

74
00:03:33,180 --> 00:03:34,620
We don't have an adjacency list.

75
00:03:34,620 --> 00:03:37,320
So this is the adjacency matrix that we have.

76
00:03:37,320 --> 00:03:41,040
And then we are going to have an array which is called vertices right.

77
00:03:41,040 --> 00:03:43,710
So this is the array a b c d e f.

78
00:03:43,710 --> 00:03:46,860
Now over here you can see a is at index zero.

79
00:03:46,860 --> 00:03:53,250
That's why in the adjacency matrix at index zero we have an array which has the neighbors of A.

80
00:03:53,370 --> 00:03:55,560
Similarly b is at index one.

81
00:03:55,560 --> 00:04:02,160
So we have at index one in the adjacency matrix an array which has the neighbors of b.

82
00:04:02,280 --> 00:04:06,720
Similarly, for example, E will be 234, right E would be at four.

83
00:04:06,720 --> 00:04:08,670
So 01234.

84
00:04:08,670 --> 00:04:09,510
This is four.

85
00:04:09,510 --> 00:04:17,040
So at index four in the adjacency matrix uh array over here we will have an array which has the neighbors

86
00:04:17,040 --> 00:04:17,730
of E.

87
00:04:17,730 --> 00:04:19,590
So this is how this is structured.

88
00:04:19,590 --> 00:04:21,750
And then we also need an object.

89
00:04:21,750 --> 00:04:27,270
Let's call it vertex indices to store the indices of each vertex.

90
00:04:27,270 --> 00:04:30,030
For example a is at zero, b is at one etc..

91
00:04:30,030 --> 00:04:35,610
So if we don't have this, then we it would not be efficient because we would have to again and again

92
00:04:35,610 --> 00:04:39,300
traverse through the array over here and find the index.

93
00:04:39,300 --> 00:04:39,480
Right.

94
00:04:39,480 --> 00:04:43,740
So having an object we can just access the index in constant time.

95
00:04:43,740 --> 00:04:49,050
For example, if I want to know the index of C I can just access it in constant time because this is

96
00:04:49,050 --> 00:04:49,950
a hash table.

97
00:04:49,950 --> 00:04:50,100
Right.

98
00:04:50,100 --> 00:04:55,020
So if I have the key I can take the value out which is the index in this case in constant time.

99
00:04:55,020 --> 00:04:56,670
So we will need these things.

100
00:04:56,670 --> 00:04:58,080
We have the adjacency matrix.

101
00:04:58,080 --> 00:05:01,320
We have an array where the vertices are stored.

102
00:05:01,320 --> 00:05:06,330
And based on this index like for example this is 01234 and five.

103
00:05:06,330 --> 00:05:07,710
So this is zero.

104
00:05:07,710 --> 00:05:11,850
That's why at index zero in the adjacency matrix we have the neighbors of A.

105
00:05:11,850 --> 00:05:12,660
This is one.

106
00:05:12,660 --> 00:05:18,150
So at index one in the adjacency matrix we have the neighbors of B etc..

107
00:05:18,150 --> 00:05:18,870
All right.

108
00:05:18,870 --> 00:05:20,790
So this is the setup.

109
00:05:20,790 --> 00:05:25,080
Now let's just make some space to discuss the algorithm and trace the algorithm.

110
00:05:25,080 --> 00:05:26,760
So we have our vertices array.

111
00:05:26,760 --> 00:05:33,720
Over here we have an object vertex indices so that we can access the index of a particular node in constant

112
00:05:33,720 --> 00:05:34,170
time.

113
00:05:34,170 --> 00:05:38,580
And then we have our adjacency matrix which stores the neighbors.

114
00:05:38,580 --> 00:05:39,120
All right.

115
00:05:39,150 --> 00:05:41,400
Now again we are implementing breadth first search.

116
00:05:41,400 --> 00:05:43,320
So for this we will need a queue.

117
00:05:43,320 --> 00:05:45,870
And let's have a visited object.

118
00:05:45,870 --> 00:05:47,400
So this is going to be a hash table.

119
00:05:47,400 --> 00:05:49,800
I'm just writing it like this to save space.

120
00:05:49,800 --> 00:05:51,630
And then we have our output array.

121
00:05:51,630 --> 00:05:55,470
Let's say we are starting at a and we are implementing the BFS.

122
00:05:55,470 --> 00:06:01,260
Now at this point we are going to push A to our queue and we will mark A as visited.

123
00:06:01,260 --> 00:06:03,030
Now we are going to execute this code.

124
00:06:03,160 --> 00:06:03,580
Over here.

125
00:06:03,580 --> 00:06:05,380
We will check if the queue is empty.

126
00:06:05,410 --> 00:06:06,340
No it's not.

127
00:06:06,340 --> 00:06:07,900
Therefore we will dequeue.

128
00:06:07,900 --> 00:06:11,830
That is, we are taking a out and we are going to put it into our output array.

129
00:06:11,830 --> 00:06:13,240
We are going to push it over here.

130
00:06:13,240 --> 00:06:17,290
And then we are going to enqueue the unvisited neighbours of A.

131
00:06:17,290 --> 00:06:23,200
So it is at this point that there is a slight difference in the implementation when the graph is stored

132
00:06:23,200 --> 00:06:28,330
as an adjacency matrix, compared to the graph being stored as an adjacency list.

133
00:06:28,330 --> 00:06:28,750
All right.

134
00:06:28,750 --> 00:06:29,470
So let's try.

135
00:06:29,590 --> 00:06:31,000
Let's see what's happening over here.

136
00:06:31,000 --> 00:06:33,490
We have the current node is a.

137
00:06:33,550 --> 00:06:38,830
Now we are going to take the index of A from the vertex indices over here.

138
00:06:38,830 --> 00:06:40,750
And we know that that's zero right.

139
00:06:40,750 --> 00:06:42,910
So we access that in constant time.

140
00:06:42,910 --> 00:06:45,400
So we have the index zero at this point.

141
00:06:45,400 --> 00:06:52,240
Now we are going to visit the array in the adjacency matrix at index zero which is this array over here.

142
00:06:52,240 --> 00:06:58,960
And then we are going to loop through the elements of this array and identify at which places we have

143
00:06:58,960 --> 00:06:59,350
one.

144
00:06:59,350 --> 00:07:02,140
So we see that we have one over here and one over here.

145
00:07:02,140 --> 00:07:06,640
Now when we we are at this one we know that this is at index one.

146
00:07:06,640 --> 00:07:06,820
Right.

147
00:07:06,820 --> 00:07:12,400
So let me just write the indexes of this array 01234 and five.

148
00:07:12,400 --> 00:07:14,800
So this one over here is at index one.

149
00:07:14,800 --> 00:07:17,470
And again let's just write the indices over here as well.

150
00:07:17,470 --> 00:07:20,110
So we have 01234 and five.

151
00:07:20,110 --> 00:07:23,470
So we have a one at index one which is this over here.

152
00:07:23,470 --> 00:07:25,540
That's why we know that B is a neighbor.

153
00:07:25,540 --> 00:07:30,190
And then we have a one at index five which is this five over here which is f.

154
00:07:30,190 --> 00:07:34,060
So in this way we know that the neighbors of A are B and f.

155
00:07:34,060 --> 00:07:37,000
And we are going to push B and f to our queue.

156
00:07:37,000 --> 00:07:39,130
And then the process remains the same.

157
00:07:39,130 --> 00:07:39,310
Right.

158
00:07:39,310 --> 00:07:40,720
We are again going to dequeue.

159
00:07:40,720 --> 00:07:44,140
So we take B out and we are going to push it to our output array.

160
00:07:44,140 --> 00:07:45,670
So we have B over here.

161
00:07:45,670 --> 00:07:46,270
All right.

162
00:07:46,270 --> 00:07:51,430
And then we are going to enqueue the unvisited neighbors of B for this again from over here.

163
00:07:51,430 --> 00:07:54,610
From this object we will identify the index of b as one.

164
00:07:54,610 --> 00:07:57,100
Then we visit the array at index one.

165
00:07:57,100 --> 00:07:58,630
In the adjacency matrix.

166
00:07:58,630 --> 00:08:03,970
We are going to loop over this and identify the neighbors by looking at what all is one.

167
00:08:03,970 --> 00:08:06,430
And then those are going to be pushed into the queue.

168
00:08:06,430 --> 00:08:08,410
So just just complete that over here.

169
00:08:08,410 --> 00:08:12,880
So at this point uh, the neighbor is a which is already there in visited.

170
00:08:12,880 --> 00:08:16,600
And again remember we would have added B and F to visited over here already.

171
00:08:16,600 --> 00:08:19,450
Whenever something is added to the queue we mark it as visited.

172
00:08:19,450 --> 00:08:21,820
So we see that A is already visited.

173
00:08:21,820 --> 00:08:27,220
Then we have c, C is not visited, so we add it to the queue and then we have f.

174
00:08:27,220 --> 00:08:28,600
F is already there in the queue.

175
00:08:28,600 --> 00:08:31,360
So we don't add it over here and then c is added to the queue.

176
00:08:31,390 --> 00:08:32,770
We mark it as visited.

177
00:08:32,770 --> 00:08:34,030
So we proceed further.

178
00:08:34,030 --> 00:08:35,320
Now it's the same thing right?

179
00:08:35,320 --> 00:08:40,540
We are going to dequeue from the queue which is F, and we are going to push it to the output array.

180
00:08:40,570 --> 00:08:43,600
Now we are going to check the index of f which is five.

181
00:08:43,600 --> 00:08:46,240
So we visit this element over here.

182
00:08:46,240 --> 00:08:51,400
Now we are going to loop through it and identify the neighbors of F which is a b.

183
00:08:51,400 --> 00:08:52,930
And then we have E right.

184
00:08:52,930 --> 00:08:54,640
So A and B are already visited.

185
00:08:54,640 --> 00:08:56,680
So we're just going to add e over here.

186
00:08:56,680 --> 00:08:58,630
And we mark E as visited.

187
00:08:58,630 --> 00:09:03,190
Again we proceed we dequeue and we are going to push it to the output array.

188
00:09:03,190 --> 00:09:06,430
And over here we see that the index of C is two.

189
00:09:06,460 --> 00:09:11,110
So we visit the element in the adjacency matrix at index two.

190
00:09:11,110 --> 00:09:14,290
And we look at we loop over these elements to identify the neighbors.

191
00:09:14,290 --> 00:09:16,420
So the neighbors are uh b.

192
00:09:16,420 --> 00:09:17,170
This is b.

193
00:09:18,430 --> 00:09:19,330
This is D.

194
00:09:19,330 --> 00:09:20,620
And then this is E right.

195
00:09:20,620 --> 00:09:25,000
So among these B is already there and uh e is already there.

196
00:09:25,000 --> 00:09:26,560
So we just have to add d.

197
00:09:26,560 --> 00:09:28,480
So let's nq d right.

198
00:09:28,480 --> 00:09:30,460
So we nq d and that is done.

199
00:09:30,460 --> 00:09:31,990
So that loop is over again.

200
00:09:31,990 --> 00:09:34,360
We are going to dequeue from the queue.

201
00:09:34,360 --> 00:09:36,220
And we will push it to the output array.

202
00:09:36,220 --> 00:09:39,640
At this point we visit index four over here.

203
00:09:39,640 --> 00:09:39,910
Right.

204
00:09:39,910 --> 00:09:42,130
So this is 01234.

205
00:09:42,130 --> 00:09:44,200
And then we look at its neighbor.

206
00:09:44,200 --> 00:09:45,370
So this is zero one.

207
00:09:45,370 --> 00:09:48,190
This is two this is three and this is five.

208
00:09:48,190 --> 00:09:49,210
So 235.

209
00:09:49,210 --> 00:09:54,190
That's c d and f and c and d are already there.

210
00:09:54,190 --> 00:09:55,480
And f is also there.

211
00:09:55,480 --> 00:09:55,750
Right.

212
00:09:55,750 --> 00:09:58,180
So when we added d we have to add it over here as well.

213
00:09:58,180 --> 00:09:59,890
So all of these are already visited.

214
00:09:59,890 --> 00:10:01,510
So we don't enqueue anything.

215
00:10:01,510 --> 00:10:06,040
And then we just dequeue again D and we push it to our output array.

216
00:10:06,040 --> 00:10:06,580
And that is it.

217
00:10:06,580 --> 00:10:09,070
So this is our BFS output.

218
00:10:09,070 --> 00:10:12,040
So a then b f then c and d.

219
00:10:12,040 --> 00:10:18,160
So this is how we have implemented BFS when the graph was stored as an adjacency matrix.

220
00:10:18,160 --> 00:10:20,890
So the difference as we have discussed is in this part.

221
00:10:20,890 --> 00:10:24,220
So it is a slight difference but it affects the time complexity.

222
00:10:24,220 --> 00:10:26,020
So let's go ahead and look at that.

223
00:10:26,020 --> 00:10:33,220
Now let's see how the change how the space and time complexity change when the breadth first search

224
00:10:33,220 --> 00:10:37,240
is done where the graph is stored as an adjacency matrix.

225
00:10:37,240 --> 00:10:41,740
So we have seen that in the previous case the time complexity was O of v plus e.

226
00:10:41,740 --> 00:10:47,530
But over here the time complexity is going to be O of v square and the space complexity is the same,

227
00:10:47,530 --> 00:10:48,490
which is O of v.

228
00:10:48,490 --> 00:10:52,450
Now let's try to understand why the time complexity is O of v square.

229
00:10:52,450 --> 00:10:54,550
Now we have our pseudocode over here.

230
00:10:54,550 --> 00:10:55,780
This is what we are doing right.

231
00:10:55,780 --> 00:11:00,130
While there was something in the queue, we'd q we pushed to the output array and then we are going

232
00:11:00,130 --> 00:11:02,110
to enqueue the unvisited neighbors.

233
00:11:02,620 --> 00:11:08,650
Now this part over here, that is something being there in the queue will happen v times, which is

234
00:11:08,650 --> 00:11:11,260
the number of node times where v is the number of nodes.

235
00:11:11,260 --> 00:11:11,560
Right.

236
00:11:11,560 --> 00:11:17,560
Because we have seen that every element will come once to the queue and we dequeue from that queue and

237
00:11:17,560 --> 00:11:18,910
we push it to our output array.

238
00:11:18,910 --> 00:11:25,390
So because we are traversing every node once so the queue will have v elements altogether, right.

239
00:11:25,390 --> 00:11:31,450
So in all instances together the queue will have v elements or this loop will happen v times.

240
00:11:31,450 --> 00:11:33,280
Or we are doing v operations over here.

241
00:11:33,280 --> 00:11:35,290
Now the difference is over here right.

242
00:11:35,290 --> 00:11:40,750
So when we are enqueuing unvisited neighbors we are having a for loop.

243
00:11:40,750 --> 00:11:47,620
Now at this point because our matrix, our graph is stored as an adjacency matrix.

244
00:11:47,620 --> 00:11:51,880
Even if there are no neighbors we have to do V operations.

245
00:11:51,880 --> 00:11:53,350
Let's try to understand this.

246
00:11:53,350 --> 00:11:56,140
For example over here this is our adjacency matrix.

247
00:11:56,140 --> 00:12:01,750
Now when we are trying to find the neighbors for example for a the array which we are looking at is

248
00:12:01,750 --> 00:12:02,440
this one over here.

249
00:12:02,440 --> 00:12:02,650
Right.

250
00:12:02,650 --> 00:12:06,160
This one over here which is 010001.

251
00:12:06,160 --> 00:12:11,740
So you can see that even though there are just two neighbors, we have to do five operations with six

252
00:12:11,740 --> 00:12:15,910
operations, which is operations equal to the number of vertices.

253
00:12:15,910 --> 00:12:21,550
So in this way for each of these vertices, irrespective of the number of neighbors which are there,

254
00:12:21,550 --> 00:12:23,980
we have to do V operations over here.

255
00:12:23,980 --> 00:12:30,010
So that is why the time complexity over here is O of v into v which is equal to v square.

256
00:12:30,070 --> 00:12:36,190
So that's the difference between implementing the graph as a adjacency list and as a adjacency matrix.

257
00:12:36,190 --> 00:12:41,050
So time complexity over here is O of V square and the space complexity is still O of v.

258
00:12:41,080 --> 00:12:44,500
We have the output array which has v elements.

259
00:12:44,920 --> 00:12:50,440
And then we have the visited object again that will also have that will also take O of space because

260
00:12:50,440 --> 00:12:53,170
it will have v value key value pairs.

261
00:12:53,170 --> 00:12:55,030
And then we have a queue also.

262
00:12:55,030 --> 00:12:55,240
Right.

263
00:12:55,240 --> 00:12:58,900
And in the worst case there they all all of them may be neighbors.

264
00:12:58,900 --> 00:13:03,640
For example A is connected to B is connected to C and that's connected to D.

265
00:13:03,640 --> 00:13:05,650
And this is connected to E and f.

266
00:13:05,650 --> 00:13:09,340
So in this case we have v minus one elements at a time in the queue.

267
00:13:09,340 --> 00:13:12,460
So the queue also in the worst case can take O of v space.

268
00:13:12,460 --> 00:13:16,420
So we can say that the space complexity is O of a constant into v.

269
00:13:16,420 --> 00:13:21,730
But then we can just remove the constant and hence the space complexity over here is O of V.