1
00:00:00,920 --> 00:00:03,290
Hi everyone, let's do this question.

2
00:00:03,290 --> 00:00:08,750
You are given a graph with n vertices to indicate the connections in the graph.

3
00:00:08,750 --> 00:00:16,190
You are given an array of edges whose each element is an array of the form u comma v u v indicates that

4
00:00:16,190 --> 00:00:21,410
there is an edge between u and v, where u and v denote two vertices or nodes.

5
00:00:21,440 --> 00:00:27,770
Write a function that takes in n and the edges array, and returns the number of connected components

6
00:00:27,770 --> 00:00:28,580
in the graph.

7
00:00:28,580 --> 00:00:31,850
So this is the question over here we are given n vertices.

8
00:00:31,850 --> 00:00:34,220
So we will be given this number n.

9
00:00:34,220 --> 00:00:34,610
All right.

10
00:00:34,610 --> 00:00:36,800
And then we will be given an edges array.

11
00:00:36,800 --> 00:00:42,320
So for example if n is equal to four and the edges array which is given to us is this over here.

12
00:00:42,320 --> 00:00:45,650
So this indicates there is an edge between 0 and 1.

13
00:00:45,650 --> 00:00:48,230
So there is another edge between 3 and 1.

14
00:00:48,230 --> 00:00:50,600
And there is an edge between 1 and 2.

15
00:00:50,600 --> 00:00:54,140
Now because n is equal to four the edges are zero.

16
00:00:54,170 --> 00:00:57,530
The vertices are zero, one, two and three.

17
00:00:57,530 --> 00:00:58,040
All right.

18
00:00:58,040 --> 00:01:00,080
So these are the four vertices.

19
00:01:00,080 --> 00:01:04,550
And over here this edges array gives the connections between these vertices.

20
00:01:04,550 --> 00:01:05,930
So let's draw this out.

21
00:01:05,930 --> 00:01:09,860
So we have a connection between 0 and 1 which is this over here.

22
00:01:09,860 --> 00:01:10,910
So that's this link.

23
00:01:10,910 --> 00:01:14,540
Then there is a connection between 3 and 1 which is this link over here.

24
00:01:14,540 --> 00:01:18,410
And then there is a connection between 1 and 2 which is this link over here.

25
00:01:18,410 --> 00:01:20,660
And again this is an undirected graph.

26
00:01:20,660 --> 00:01:21,110
All right.

27
00:01:21,110 --> 00:01:26,720
So over here if this is the graph which is given to us, we can see that all of these nodes are connected

28
00:01:26,720 --> 00:01:27,500
to each other.

29
00:01:27,500 --> 00:01:30,410
Therefore this makes up just one component.

30
00:01:30,410 --> 00:01:33,950
So the number of components in this case is equal to one.

31
00:01:33,950 --> 00:01:35,960
Now let's say n is equal to four.

32
00:01:35,960 --> 00:01:41,120
And the array which is given to us the edges array is this one over here, which indicates there is

33
00:01:41,120 --> 00:01:42,740
a connection between 0 and 1.

34
00:01:42,740 --> 00:01:45,080
And there is a connection between 2 and 3.

35
00:01:45,080 --> 00:01:49,700
So because n is equal to four the vertices are zero one, two and three.

36
00:01:50,300 --> 00:01:56,150
And we can see that the connections are between 0 and 1 which is indicated by this array over here.

37
00:01:56,150 --> 00:01:59,570
And then there is a connection between 2 and 3 which is this connection over here.

38
00:01:59,570 --> 00:02:04,400
Now in this case we can see that this is one component and this is another component right.

39
00:02:04,400 --> 00:02:06,530
So these are not connected with each other.

40
00:02:06,530 --> 00:02:12,710
So if this was the edges array and n is equal to four then this function should return the number of

41
00:02:12,710 --> 00:02:15,230
components as equal to two which is.

42
00:02:15,230 --> 00:02:18,110
This is one component and this is the second component.

43
00:02:18,110 --> 00:02:18,620
All right.

44
00:02:18,620 --> 00:02:20,390
So we have understood this question.

45
00:02:20,390 --> 00:02:24,440
Now let's go ahead and try to think about how we can solve this question.

46
00:02:24,440 --> 00:02:28,010
Now for this let's say that this is the graph which is given to us.

47
00:02:28,010 --> 00:02:30,680
So in this case n would be equal to seven.

48
00:02:30,680 --> 00:02:34,880
So that's why the vertices are zero, one, two three, four, five and six.

49
00:02:34,880 --> 00:02:36,380
So n would be equal to seven.

50
00:02:36,380 --> 00:02:40,250
And then each of these connections would be mentioned in the edges array.

51
00:02:40,250 --> 00:02:46,460
Now before we proceed and think about how to solve this question, let's try to make a few observations.

52
00:02:47,060 --> 00:02:50,990
The first observation is that let's for example, take this node.

53
00:02:50,990 --> 00:02:58,490
And if you call if you do a breadth first traversal or a depth first traversal starting from this node,

54
00:02:58,490 --> 00:03:03,650
then you can notice that we would visit all these nodes which are connected to it.

55
00:03:03,650 --> 00:03:03,950
Right.

56
00:03:03,950 --> 00:03:07,460
So you can do either breadth first search or DFS or depth first search.

57
00:03:07,460 --> 00:03:07,730
Right.

58
00:03:07,730 --> 00:03:08,960
So this is just traversing.

59
00:03:08,960 --> 00:03:09,110
Right.

60
00:03:09,110 --> 00:03:12,860
We have seen BFS or DFS is a method to traverse a graph.

61
00:03:12,860 --> 00:03:19,880
So if we call BFS or DFS which we already discussed with this node, then all of these nodes would also

62
00:03:19,880 --> 00:03:20,450
be visited.

63
00:03:20,450 --> 00:03:20,660
Right.

64
00:03:20,660 --> 00:03:23,720
We would traverse this node, this node, this node and this node.

65
00:03:23,720 --> 00:03:27,230
So it's it's we can do it in either way because these are connected.

66
00:03:27,230 --> 00:03:28,700
So this is the first observation right.

67
00:03:28,700 --> 00:03:30,920
So let's say the graph was something like this.

68
00:03:30,920 --> 00:03:37,250
So if all of them are connected then if we just call BFS or DFS with any of these nodes we would visit

69
00:03:37,250 --> 00:03:38,390
all these nodes.

70
00:03:38,810 --> 00:03:39,140
Right.

71
00:03:39,140 --> 00:03:40,580
So that's the first observation.

72
00:03:40,580 --> 00:03:47,420
So if we call BFS or DFS that is breadth first search or traversal or depth first search or traversal

73
00:03:47,420 --> 00:03:48,260
on any node.

74
00:03:48,260 --> 00:03:51,950
Then we can visit all the nodes which are connected to it.

75
00:03:51,950 --> 00:03:52,370
All right.

76
00:03:52,370 --> 00:03:54,050
So this is an interesting observation.

77
00:03:54,530 --> 00:03:57,500
Now let's say this is the graph which is given to us.

78
00:03:57,500 --> 00:04:04,550
If we just do BFS or DFS on this particular node, then the second observation is that we would not

79
00:04:04,550 --> 00:04:10,070
be visiting this node, and we will not be visiting these two nodes because they are not connected to

80
00:04:10,070 --> 00:04:10,460
this node.

81
00:04:10,460 --> 00:04:10,760
Right.

82
00:04:10,760 --> 00:04:11,990
So that's the second observation.

83
00:04:11,990 --> 00:04:17,720
The first was that if we call BFS or DFS on this node, everything that is connected to it will be visited.

84
00:04:17,720 --> 00:04:22,370
And the second thing is that everything that is not connected to it will not be visited.

85
00:04:22,370 --> 00:04:25,760
So these are the two important things that we should notice over here.

86
00:04:25,760 --> 00:04:28,190
Now let's see how we can solve this question.

87
00:04:28,190 --> 00:04:33,560
We just have to iterate from 0 to 6 right from the nodes 0 to 6.

88
00:04:33,560 --> 00:04:39,320
And we can just call BFS or DFS if that particular node is not yet visited.

89
00:04:39,320 --> 00:04:43,580
So this will ensure that we will also visit the unconnected parts.

90
00:04:43,580 --> 00:04:49,460
So for example when we call BFS or DFS with node zero we have seen all these will be visited.

91
00:04:49,460 --> 00:04:53,150
And when we call BFS or DFS with two this one will be visited.

92
00:04:53,150 --> 00:04:56,030
And when we call it with 4 or 6 these two will be visited.

93
00:04:56,030 --> 00:04:56,360
Right?

94
00:04:56,360 --> 00:05:00,290
So whenever we see a non visited node all we have to do.

95
00:05:00,570 --> 00:05:05,490
We have to mark it as visited and we can increment the count because we are seeing a new component,

96
00:05:05,490 --> 00:05:05,760
right?

97
00:05:05,760 --> 00:05:08,580
So let's try to trace this and think about this algorithm.

98
00:05:08,580 --> 00:05:12,270
So we are going to iterate from the nodes 0 to 6.

99
00:05:12,270 --> 00:05:14,070
So we have 0 to 6 over here.

100
00:05:14,610 --> 00:05:18,480
Now initially the count of the number of components is set to zero.

101
00:05:18,480 --> 00:05:18,930
All right.

102
00:05:18,960 --> 00:05:21,000
Now let's say we call DFS.

103
00:05:21,000 --> 00:05:23,220
Let's try to solve this question with DFS.

104
00:05:23,220 --> 00:05:25,170
Now again we can solve it in either way.

105
00:05:25,170 --> 00:05:27,630
But in this video let's just solve it with DFS.

106
00:05:27,630 --> 00:05:28,080
All right.

107
00:05:28,080 --> 00:05:30,270
And let's try to do it in a recursive manner.

108
00:05:30,270 --> 00:05:34,590
Now let's say we are calling the DFS function with node zero.

109
00:05:34,590 --> 00:05:38,640
So at that point we will visit 013 and five.

110
00:05:38,640 --> 00:05:40,200
So these will be visited.

111
00:05:40,200 --> 00:05:44,370
Now again when we come to one when we are iterating from 0 to 6 right.

112
00:05:44,370 --> 00:05:45,840
So after zero we come to one.

113
00:05:45,840 --> 00:05:48,060
At that point we will see that it is visited.

114
00:05:48,060 --> 00:05:50,640
So we will not call DFS on that node.

115
00:05:50,640 --> 00:05:51,000
All right.

116
00:05:51,000 --> 00:05:54,270
And again once we visited these we got one component.

117
00:05:54,270 --> 00:05:55,470
So this is one component.

118
00:05:55,470 --> 00:05:57,870
So that's why the count has been incremented to one.

119
00:05:57,870 --> 00:05:58,380
All right.

120
00:05:58,380 --> 00:05:59,640
So zero is done.

121
00:05:59,640 --> 00:06:02,730
Now we came to one over here we see one is already visited.

122
00:06:02,730 --> 00:06:04,020
So we don't go inside.

123
00:06:04,020 --> 00:06:05,100
We don't call DFS.

124
00:06:05,130 --> 00:06:06,360
We again increment.

125
00:06:06,360 --> 00:06:07,170
We come to two.

126
00:06:07,200 --> 00:06:09,210
We see that two is not yet visited right.

127
00:06:09,210 --> 00:06:11,550
So we will call the DFS function on two.

128
00:06:11,550 --> 00:06:16,140
And we will increment the count because we are having a new component now because it does not have any

129
00:06:16,140 --> 00:06:18,720
neighbors, it will not go to any other node.

130
00:06:18,720 --> 00:06:19,050
All right.

131
00:06:19,050 --> 00:06:22,110
But this one over here is visited and this is the second component.

132
00:06:22,140 --> 00:06:24,030
Now we again proceed to three.

133
00:06:24,120 --> 00:06:26,700
And at that point we see that this is already visited.

134
00:06:26,700 --> 00:06:28,110
So we don't call DFS.

135
00:06:28,110 --> 00:06:30,300
On node three we proceed to four right.

136
00:06:30,300 --> 00:06:31,530
So we proceed to four.

137
00:06:31,530 --> 00:06:36,150
Now when we call DFS on four, four and six are going to be visited.

138
00:06:36,150 --> 00:06:36,360
Right.

139
00:06:36,360 --> 00:06:39,870
So four and six are visited and our count is changed to three.

140
00:06:39,870 --> 00:06:41,940
Then we come over here, we come to five.

141
00:06:41,970 --> 00:06:43,200
We see it's already visited.

142
00:06:43,200 --> 00:06:44,160
Then we come to six.

143
00:06:44,160 --> 00:06:45,420
We see it's already visited.

144
00:06:45,420 --> 00:06:46,980
And that brings us to the end.

145
00:06:46,980 --> 00:06:50,730
And we have identified that the number of components is equal to three.

146
00:06:50,730 --> 00:06:52,200
So this is one component.

147
00:06:52,200 --> 00:06:53,730
This is the second component.

148
00:06:53,730 --> 00:06:57,150
And this over here is the third component of this graph.

149
00:06:57,150 --> 00:06:57,660
All right.

150
00:06:57,660 --> 00:06:59,700
So this is how we can solve this question.

151
00:06:59,700 --> 00:07:04,050
Now let's try to look at the complexity analysis of this question.

152
00:07:04,050 --> 00:07:07,590
First let's try to think about the time complexity of this solution.

153
00:07:07,980 --> 00:07:12,780
Now what are the things that take up time over here or number of operations.

154
00:07:12,780 --> 00:07:13,080
Right.

155
00:07:13,080 --> 00:07:16,140
So we will have to build the adjacency list right.

156
00:07:16,140 --> 00:07:18,390
So we will be given just the edges array.

157
00:07:18,390 --> 00:07:23,370
So in this case the edges array will be zero comma one which is this link.

158
00:07:23,370 --> 00:07:24,750
Then one comma three.

159
00:07:26,330 --> 00:07:28,520
And then we have three comma five.

160
00:07:30,590 --> 00:07:33,530
And then we have this two which does not have anything.

161
00:07:33,530 --> 00:07:34,430
So there is no edge.

162
00:07:34,430 --> 00:07:36,050
And then we have four comma six.

163
00:07:36,050 --> 00:07:38,540
So these are the elements in the edges array.

164
00:07:38,570 --> 00:07:41,570
Now using n which is equal to seven in this place.

165
00:07:41,570 --> 00:07:45,350
And this edges array we will have to build the adjacency list.

166
00:07:45,350 --> 00:07:45,620
Right.

167
00:07:45,620 --> 00:07:47,540
So why is this required.

168
00:07:47,540 --> 00:07:50,150
This will be required for doing our DFS right.

169
00:07:50,150 --> 00:07:53,570
So whenever we come over here and we do the depth first search.

170
00:07:53,570 --> 00:07:55,730
And again you could do BFS also.

171
00:07:55,730 --> 00:07:58,400
Now when we in this question we are just using DFS.

172
00:07:58,400 --> 00:08:02,420
Now when we do this we will be using the adjacency list to identify the neighbors.

173
00:08:02,420 --> 00:08:02,720
Right.

174
00:08:02,720 --> 00:08:05,390
So we will have to build the adjacency list.

175
00:08:05,390 --> 00:08:09,080
Now building the adjacency list from the edges array over here.

176
00:08:09,080 --> 00:08:14,960
And the vertices is going to be an O of v plus e where v is the number of vertices and e is the number

177
00:08:14,960 --> 00:08:15,440
of edges.

178
00:08:15,440 --> 00:08:15,950
Operation.

179
00:08:15,950 --> 00:08:16,220
Right.

180
00:08:16,220 --> 00:08:20,000
So initially we are going to build an empty adjacency list.

181
00:08:20,000 --> 00:08:22,430
So it's going to have n number of elements.

182
00:08:22,430 --> 00:08:24,200
So in this case n is equal to seven.

183
00:08:24,200 --> 00:08:26,240
So that would be seven empty arrays right.

184
00:08:26,240 --> 00:08:30,200
So it would be an array where each element is an empty array.

185
00:08:30,200 --> 00:08:32,060
And there will be seven such empty arrays.

186
00:08:32,060 --> 00:08:37,520
So building this is going to be a V operation because this is going to have v empty arrays over here.

187
00:08:37,520 --> 00:08:37,880
All right.

188
00:08:37,880 --> 00:08:39,920
So this is the empty arrays.

189
00:08:39,920 --> 00:08:42,200
And then we have to loop through each element.

190
00:08:42,200 --> 00:08:45,950
So this has the number of elements over here will be equal to the number of edges.

191
00:08:45,950 --> 00:08:50,570
So we will do e number of operations to loop through the edges array over here.

192
00:08:50,570 --> 00:08:50,930
Right.

193
00:08:50,930 --> 00:08:52,340
So that is this e over here.

194
00:08:52,340 --> 00:08:54,860
And then we will just push into zero over here.

195
00:08:54,860 --> 00:08:57,530
We will push one and into one we will push zero.

196
00:08:57,530 --> 00:09:02,570
And in this way we will go ahead and build the edges into these elements in their respective places.

197
00:09:02,570 --> 00:09:07,640
So to build the adjacency list we will have to do O of V plus E operations.

198
00:09:07,640 --> 00:09:10,040
So this is one thing that takes up time.

199
00:09:10,040 --> 00:09:10,940
Now what else.

200
00:09:10,940 --> 00:09:12,290
What else takes up time.

201
00:09:12,290 --> 00:09:20,120
You can see that looping through the vertices that is going from 0 to 6, and then calling DFS recursively

202
00:09:20,120 --> 00:09:22,280
will also take some number of operations.

203
00:09:22,280 --> 00:09:22,610
Right.

204
00:09:22,610 --> 00:09:24,050
Let's try to think about this.

205
00:09:24,050 --> 00:09:27,920
So this part over here will take O of V plus E operations.

206
00:09:27,920 --> 00:09:28,670
Why is that.

207
00:09:28,670 --> 00:09:32,840
So let's try to think about it over here we have this sample graph right.

208
00:09:32,840 --> 00:09:39,170
So initially when we call the DFS when we go from 0 to 6 you can see straightforward over here we are

209
00:09:39,170 --> 00:09:41,120
going to have v number of operations.

210
00:09:41,120 --> 00:09:47,000
And then we are trying we are going to have e number of E one operations for node zero.

211
00:09:47,030 --> 00:09:47,480
Right.

212
00:09:47,480 --> 00:09:54,200
So when we call DFS for zero let me just write that over here 012345 and six.

213
00:09:54,200 --> 00:09:58,040
So when we call DFS for zero we will come inside the DFS function.

214
00:09:58,040 --> 00:09:59,630
We will look at its neighbors right.

215
00:09:59,630 --> 00:10:04,820
So we will try to see each of its neighbors each of its edges if it's visited or not.

216
00:10:04,820 --> 00:10:09,680
So that would be E one operations where E1 is the number of edges of zero.

217
00:10:09,680 --> 00:10:16,310
Similarly, when we call DFS for node one again we are going to do e two operations inside the DFS function.

218
00:10:16,310 --> 00:10:19,940
When we call DFS for two, we are going to do E three operations, etc..

219
00:10:19,940 --> 00:10:20,240
Right.

220
00:10:20,240 --> 00:10:24,020
And we are going to call the depth first search function for each of these nodes.

221
00:10:24,020 --> 00:10:25,460
So that is what we're doing over here right.

222
00:10:25,460 --> 00:10:26,450
We are iterating.

223
00:10:26,450 --> 00:10:29,300
And then we are going to call the DFS function for each node.

224
00:10:29,300 --> 00:10:33,500
Now every node will be called DFS will be called once with every node.

225
00:10:33,500 --> 00:10:34,970
It can happen in two ways.

226
00:10:34,970 --> 00:10:38,630
The first way is like if it's not connected for example two, right?

227
00:10:38,660 --> 00:10:41,540
Two will be called when we get to two over here.

228
00:10:41,540 --> 00:10:45,020
Now DFS on one, three and five will be called recursively.

229
00:10:45,020 --> 00:10:47,990
When we call it for zero it will call it for one as well.

230
00:10:47,990 --> 00:10:50,390
And from there it will call it for three as well.

231
00:10:50,390 --> 00:10:52,490
And from there it will call it for five as well.

232
00:10:52,490 --> 00:10:55,250
So DFS for each of these nodes will happen.

233
00:10:55,250 --> 00:10:56,360
Whenever it happens.

234
00:10:56,360 --> 00:11:00,620
We will have inside that function e I times of operations.

235
00:11:00,620 --> 00:11:00,830
Right.

236
00:11:00,830 --> 00:11:06,740
So in this case there will be e four operations over here E five operations over here E six operations.

237
00:11:06,740 --> 00:11:08,810
And over here E seven operations.

238
00:11:08,810 --> 00:11:14,300
Because we have to iterate through the neighbors of that particular node, which will be an array.

239
00:11:14,300 --> 00:11:14,510
Right.

240
00:11:14,510 --> 00:11:17,600
So that would be received from our adjacency list.

241
00:11:17,600 --> 00:11:20,720
So for example in this case let's take the three right.

242
00:11:20,720 --> 00:11:22,430
So this is this is zero.

243
00:11:22,730 --> 00:11:26,480
This is one this is two this is three etc..

244
00:11:26,480 --> 00:11:28,460
So I'm just taking the example of three.

245
00:11:28,460 --> 00:11:31,160
In the case of three the neighbors are one and five.

246
00:11:31,790 --> 00:11:32,630
This is three right.

247
00:11:32,630 --> 00:11:34,610
So one and five will be there over here.

248
00:11:34,610 --> 00:11:39,890
So whenever we are doing DFS on three we will be taking its neighbors which are one and five.

249
00:11:39,890 --> 00:11:40,940
And then E four.

250
00:11:40,940 --> 00:11:42,710
Over here will be two operations.

251
00:11:42,710 --> 00:11:45,170
We because we have to check whether one is visited.

252
00:11:45,170 --> 00:11:49,070
If not we have to call DFS on one and we have to check whether five is visited.

253
00:11:49,070 --> 00:11:51,470
And if not we have to call DFS on one.

254
00:11:51,470 --> 00:11:53,240
So that would be two operations over there.

255
00:11:53,240 --> 00:11:57,350
So you can see that the total number of operations over here will be in this case.

256
00:11:57,350 --> 00:11:59,240
That's the number of operations.

257
00:11:59,240 --> 00:12:04,700
And if we add all of these up together we will get two times E because this is an undirected graph right.

258
00:12:04,700 --> 00:12:09,020
So an edge between 1 and 3 will be represented over here as well as over here.

259
00:12:09,020 --> 00:12:09,800
This is for one right.

260
00:12:09,800 --> 00:12:12,560
So over here also we will have zero and three.

261
00:12:12,590 --> 00:12:16,490
So this three over here this indicates the connection between 1 and 3.

262
00:12:16,490 --> 00:12:19,070
And this one indicates the connection between 1 and 3.

263
00:12:19,070 --> 00:12:24,200
So because this is an undirected graph, if we add up all of these together we will get two times e.

264
00:12:24,200 --> 00:12:28,820
That's why we can see over here we are getting o of v plus two e number of operations.

265
00:12:28,820 --> 00:12:30,110
And this is just a constant.

266
00:12:30,260 --> 00:12:31,340
So we can avoid this.

267
00:12:31,340 --> 00:12:37,400
And we can see that to iterate through the vertices and recursively call DFS, we are doing a total

268
00:12:37,400 --> 00:12:40,100
number of O of v plus e operations.

269
00:12:40,100 --> 00:12:43,130
So let me just clear this up again.

270
00:12:43,130 --> 00:12:44,450
How did we get this over here.

271
00:12:44,450 --> 00:12:50,240
It's just the total right o of V plus one and uh v two plus E two etc..

272
00:12:50,240 --> 00:12:50,570
Right.

273
00:12:50,570 --> 00:12:52,460
So this has to happen for each node.

274
00:12:52,460 --> 00:12:56,030
So we have seen that and this will converge to O of v plus e.

275
00:12:56,060 --> 00:13:00,320
Again we have to but that can be just removed because that's a constant.

276
00:13:00,320 --> 00:13:06,200
So we can see that the time complexity of this solution is of the order of v plus e, where v is the

277
00:13:06,200 --> 00:13:09,290
number of vertices and e is the total number of edges.

278
00:13:09,320 --> 00:13:12,440
Now what about the space complexity of this solution?

279
00:13:12,440 --> 00:13:18,170
Now for this, let's try to think about the things that take up space which can scale when the input

280
00:13:18,170 --> 00:13:18,830
increases.

281
00:13:18,830 --> 00:13:21,620
So we have the adjacency list which we have to build.

282
00:13:21,620 --> 00:13:24,050
Then we have the visited object.

283
00:13:24,050 --> 00:13:30,560
And then because we are implementing this solution over here in the DFS method, by using DFS and in

284
00:13:30,560 --> 00:13:33,470
the recursive manner, we will have space on the call stack.

285
00:13:33,470 --> 00:13:35,360
Now what about the adjacency list.

286
00:13:35,360 --> 00:13:39,140
So the adjacency list will have v number of arrays right.

287
00:13:39,140 --> 00:13:41,150
So it's going to be an array of arrays.

288
00:13:41,150 --> 00:13:46,100
And the arrays inside this array is going to be equal to number of the vertices.

289
00:13:46,100 --> 00:13:46,370
Right.

290
00:13:46,370 --> 00:13:48,080
One array for each vertex.

291
00:13:48,080 --> 00:13:52,640
And then inside these we will have elements which represents the number of edges.

292
00:13:52,640 --> 00:13:58,910
So that's why we can see that the space that is taken by the adjacency list will be of the order of

293
00:13:58,910 --> 00:14:00,140
v plus e, right.

294
00:14:00,140 --> 00:14:04,580
So v number of arrays and inside the arrays elements to represent the edges.

295
00:14:04,580 --> 00:14:07,370
So over here this takes order of v plus e space.

296
00:14:07,370 --> 00:14:13,730
And the visited object is going to take space of the order of V because we will finally have all the

297
00:14:13,730 --> 00:14:14,600
vertices visited.

298
00:14:14,600 --> 00:14:14,900
Right.

299
00:14:14,900 --> 00:14:17,480
So we will just have one entry for one vertex.

300
00:14:17,480 --> 00:14:21,050
That's why this is going to take space of the order of V and the call stack.

301
00:14:21,050 --> 00:14:26,450
In the worst case, if all the nodes are connected, then because we're doing a recursive solution we

302
00:14:26,450 --> 00:14:31,040
call stack maximum can have v call calls in the call stack at the same time.

303
00:14:31,040 --> 00:14:33,170
So these are the things that take up space.

304
00:14:33,170 --> 00:14:36,260
And we have seen the order of space that these things take up.

305
00:14:36,260 --> 00:14:38,870
So that's why we can say that this is the greatest.

306
00:14:38,870 --> 00:14:43,910
So the space complexity of this solution is going to be of the order of V plus E.