1 00:00:00,520 --> 00:00:01,510 Welcome back. 2 00:00:01,510 --> 00:00:06,520 Let's now go ahead and write the function that will traverse this graph depth first. 3 00:00:06,520 --> 00:00:09,400 And we are going to write a recursive function over here. 4 00:00:09,400 --> 00:00:12,400 So let's call this function Trav DFS. 5 00:00:14,060 --> 00:00:16,880 Now this function is going to be recursively called. 6 00:00:16,880 --> 00:00:21,170 So we have to decide what parameters should be passed to it at every point. 7 00:00:21,170 --> 00:00:25,460 So we definitely need the graph which is this adjacency list over here. 8 00:00:25,460 --> 00:00:30,980 And we need the current vertex where we are at when we call this function. 9 00:00:30,980 --> 00:00:33,950 And we also need the output array which is to be returned. 10 00:00:33,950 --> 00:00:34,550 Finally. 11 00:00:34,550 --> 00:00:41,030 And we need a object let's call it visited, so that we can keep track of which nodes or vertices have 12 00:00:41,030 --> 00:00:42,140 been visited so far. 13 00:00:42,140 --> 00:00:42,680 All right. 14 00:00:42,680 --> 00:00:48,170 So at this point, once we are inside this function we will have called it with a particular vertex 15 00:00:48,170 --> 00:00:48,380 right. 16 00:00:48,380 --> 00:00:50,990 So initially itself we will push that to the output array. 17 00:00:50,990 --> 00:00:53,540 So we can say output dot push vertex. 18 00:00:53,540 --> 00:00:57,260 And we will mark that particular vertex as visited. 19 00:00:57,260 --> 00:01:01,460 So we can say visited at vertex is true. 20 00:01:03,850 --> 00:01:04,360 All right. 21 00:01:04,360 --> 00:01:08,650 Now we are going to find the neighbors of this particular vertex. 22 00:01:08,650 --> 00:01:15,520 And if they have not been visited, then we will call DFS function recursively for those particular 23 00:01:15,520 --> 00:01:16,180 vertices. 24 00:01:16,180 --> 00:01:17,800 So let's go ahead and do that. 25 00:01:17,800 --> 00:01:20,350 So we can say const neighbors. 26 00:01:21,940 --> 00:01:24,400 Is equal to this. 27 00:01:24,400 --> 00:01:29,770 This we have this adjacency list is the graph that is passed to over here right to this function. 28 00:01:29,770 --> 00:01:32,050 So we can say the neighbors is graph. 29 00:01:33,030 --> 00:01:34,260 At vertex. 30 00:01:35,590 --> 00:01:35,890 All right. 31 00:01:35,890 --> 00:01:43,120 So for example if we have the vertex a then we will take the values where the key is a in this adjacency 32 00:01:43,120 --> 00:01:44,290 list which is b and f. 33 00:01:44,290 --> 00:01:46,000 So this array will be neighbors. 34 00:01:46,000 --> 00:01:50,380 So this neighbors is going to be the array of the neighbors of that particular vertex. 35 00:01:50,380 --> 00:01:52,360 Now we are going to loop through that array. 36 00:01:52,360 --> 00:01:58,660 So let's have a for loop for let I is equal to zero I less than. 37 00:01:59,330 --> 00:02:00,800 Neighbors dot length. 38 00:02:03,560 --> 00:02:04,550 I plus, plus. 39 00:02:08,200 --> 00:02:08,770 All right. 40 00:02:08,770 --> 00:02:13,570 Now we are going to identify each neighbor so we can say const neighbor. 41 00:02:14,700 --> 00:02:17,250 Is equal to neighbors. 42 00:02:17,850 --> 00:02:18,660 At I. 43 00:02:20,160 --> 00:02:22,290 So this is going to be one particular neighbor. 44 00:02:22,290 --> 00:02:24,270 For example, B is a neighbor. 45 00:02:24,270 --> 00:02:28,800 Right now we have to check whether this neighbor is there in the visited object. 46 00:02:28,800 --> 00:02:29,820 So let's do that. 47 00:02:29,820 --> 00:02:30,570 So if. 48 00:02:33,610 --> 00:02:37,300 Not visited at neighbor. 49 00:02:37,510 --> 00:02:37,780 Right. 50 00:02:37,780 --> 00:02:43,060 So if this is undefined, that means there is no entry where the key is equal to the neighbor. 51 00:02:43,060 --> 00:02:47,050 If this is the case, then we will recursively call the DFS function. 52 00:02:47,050 --> 00:02:48,970 So again trav dfs. 53 00:02:48,970 --> 00:02:50,980 And then we have to just pass the parameters. 54 00:02:50,980 --> 00:02:52,120 So we have the graph. 55 00:02:52,390 --> 00:02:56,950 And at this point the vertex is going to be this particular neighbor. 56 00:02:56,950 --> 00:02:58,780 So over here we say neighbor. 57 00:03:00,060 --> 00:03:05,940 And then we have to parse the output array and the visited object to keep track whether we have visited 58 00:03:05,940 --> 00:03:07,020 a vertex or not. 59 00:03:07,020 --> 00:03:07,800 And that is it. 60 00:03:07,800 --> 00:03:13,320 So once we are done with this, once we are out of this for loop, we have to just return output. 61 00:03:15,830 --> 00:03:17,810 And we are done with our function. 62 00:03:17,810 --> 00:03:19,130 Now let's test it out. 63 00:03:19,130 --> 00:03:21,110 So we have the adjacency list over here. 64 00:03:21,110 --> 00:03:23,030 So let's call this function. 65 00:03:23,880 --> 00:03:24,810 Travis. 66 00:03:26,020 --> 00:03:28,060 And let's take a look at the parameters. 67 00:03:28,060 --> 00:03:32,500 We have to pass the graph, which is the adjacency list which we have over here. 68 00:03:32,500 --> 00:03:35,080 This is given to us as part of the question. 69 00:03:35,080 --> 00:03:42,070 And let's say we want to start traversing the graph from vertex A and the output array. 70 00:03:42,070 --> 00:03:44,530 At this point let it just be an empty array. 71 00:03:44,530 --> 00:03:48,730 And the visited object is also just going to be an empty object. 72 00:03:48,730 --> 00:03:49,570 So that is it. 73 00:03:49,570 --> 00:03:50,470 So this should work. 74 00:03:50,470 --> 00:03:56,020 So let's try run our code and let's take a look at the output that we are getting. 75 00:03:56,020 --> 00:03:56,560 All right. 76 00:03:56,560 --> 00:04:00,460 So we are getting a, b, c, e d and f okay. 77 00:04:00,460 --> 00:04:01,450 So this is working. 78 00:04:01,450 --> 00:04:05,740 So this is the same graph which we discussed when we discussed the concept video. 79 00:04:05,740 --> 00:04:09,460 But let's over here take a moment and relook at the code. 80 00:04:09,460 --> 00:04:12,910 And we will also quickly take a relook at the space and time complexity. 81 00:04:12,910 --> 00:04:16,900 So for this let me just draw this out so that we can visualize it better. 82 00:04:18,810 --> 00:04:19,260 All right. 83 00:04:19,260 --> 00:04:22,830 So I have drawn the graph over here so that we can visualize it. 84 00:04:22,830 --> 00:04:27,090 Now let's try to trace the algorithm and let's see what's happening. 85 00:04:27,090 --> 00:04:33,510 Initially we call DFS and we are passing the vertex a and the output array is empty and the visited 86 00:04:33,510 --> 00:04:34,500 object is empty. 87 00:04:34,500 --> 00:04:38,400 So we come over here and we are going to push a to the output array. 88 00:04:38,400 --> 00:04:40,110 So that is why we have a over here. 89 00:04:40,110 --> 00:04:40,620 All right. 90 00:04:40,620 --> 00:04:43,020 And then we mark A as visited. 91 00:04:43,020 --> 00:04:47,340 So let's just make a tick mark over here to indicate that A is visited. 92 00:04:47,340 --> 00:04:51,300 Now we are going to identify the neighbors of A which is B and F. 93 00:04:51,300 --> 00:04:57,030 And we are going to have this for loop where I is going to take the values zero and one, because the 94 00:04:57,030 --> 00:04:58,290 length of neighbors is two. 95 00:04:58,290 --> 00:04:58,650 Right? 96 00:04:58,650 --> 00:05:04,500 So and then for each of these neighbors, which is b and f, we are going to check whether they have 97 00:05:04,500 --> 00:05:05,820 been visited or not. 98 00:05:05,820 --> 00:05:09,000 And if not we are going to recursively call Trav DFS. 99 00:05:09,000 --> 00:05:11,820 So initially we are going to call it for B. 100 00:05:11,820 --> 00:05:14,550 So let me just keep track of that over here. 101 00:05:15,060 --> 00:05:17,970 So we are going to call Trav DFS for B. 102 00:05:19,870 --> 00:05:20,530 All right. 103 00:05:20,530 --> 00:05:25,630 And later we have the opportunity to call it for F also. 104 00:05:25,630 --> 00:05:29,200 So I'm just keeping it over here so that we can see what's happening. 105 00:05:29,200 --> 00:05:29,380 Right. 106 00:05:29,380 --> 00:05:31,330 So this is the recursive call stack. 107 00:05:31,330 --> 00:05:34,000 So we are calling DFS where we are passing B. 108 00:05:34,000 --> 00:05:35,860 Again we come over here. 109 00:05:36,460 --> 00:05:39,250 And at this point we push b to the output array. 110 00:05:39,250 --> 00:05:40,570 So we have b over here. 111 00:05:40,570 --> 00:05:42,400 And we mark it as visited. 112 00:05:42,400 --> 00:05:43,840 So let's have a tick mark. 113 00:05:44,170 --> 00:05:48,610 And after this we are going to check the neighbors of B which is A and C. 114 00:05:48,700 --> 00:05:51,400 Now again I is initially C zero. 115 00:05:51,400 --> 00:05:54,130 So at that point we get the neighbor as a right. 116 00:05:54,130 --> 00:05:59,200 This this line over here const neighbor is neighbors at I we get the neighbor as a but we see that it 117 00:05:59,200 --> 00:06:00,100 is already visited. 118 00:06:00,100 --> 00:06:03,280 So we don't call the DFS function for A. 119 00:06:03,790 --> 00:06:06,460 And then we go to the next neighbor. 120 00:06:06,460 --> 00:06:06,790 All right. 121 00:06:06,790 --> 00:06:09,100 So let me just make some space over here. 122 00:06:11,020 --> 00:06:11,770 All right. 123 00:06:12,630 --> 00:06:14,730 Let's just make it a little bit smaller. 124 00:06:14,880 --> 00:06:16,410 So let's continue. 125 00:06:16,410 --> 00:06:19,500 So I take the next neighbor which is C right. 126 00:06:19,500 --> 00:06:21,600 So the next neighbor is C at this point. 127 00:06:21,600 --> 00:06:24,000 And we can see that C is not yet visited. 128 00:06:24,000 --> 00:06:26,970 So we call DFS and we pass C. 129 00:06:26,970 --> 00:06:28,650 So let's do that over here. 130 00:06:29,830 --> 00:06:33,790 Let me just have C written over here and then there is nothing else. 131 00:06:33,790 --> 00:06:33,970 Write. 132 00:06:33,970 --> 00:06:37,360 The neighbors are just A and C, and for A it was already visited. 133 00:06:37,360 --> 00:06:39,760 So we did not call the DFS function. 134 00:06:39,760 --> 00:06:40,930 So we call it for C. 135 00:06:40,960 --> 00:06:44,170 And we come over here and we push C to the output array. 136 00:06:44,170 --> 00:06:45,970 So that's what we have over here. 137 00:06:45,970 --> 00:06:48,760 And after that we mark C as visited. 138 00:06:48,760 --> 00:06:51,820 And we find its neighbors which is B, e and d. 139 00:06:51,910 --> 00:06:56,020 So among b, e and d b is already visited, e and D are not visited. 140 00:06:56,020 --> 00:06:57,190 So we take the. 141 00:06:57,190 --> 00:07:02,350 When I is zero, we get B, but we don't call the function for that because it's already visited. 142 00:07:02,350 --> 00:07:04,600 Then when I is equal to one, we get E right? 143 00:07:04,600 --> 00:07:08,350 So we're going to recursively call the DFS function again over here. 144 00:07:08,350 --> 00:07:11,110 And vertex is going to be e at this point. 145 00:07:11,110 --> 00:07:15,430 And later we have the option to call it for D right when I becomes two. 146 00:07:15,460 --> 00:07:17,350 So I'm just writing that over here. 147 00:07:17,350 --> 00:07:19,870 So we are calling DFS with E. 148 00:07:19,870 --> 00:07:22,450 Again we come over here we push E to the output array. 149 00:07:22,450 --> 00:07:23,770 So we have that over here. 150 00:07:23,770 --> 00:07:25,690 And we mark E as visited. 151 00:07:25,690 --> 00:07:27,070 So I have a tick mark. 152 00:07:27,070 --> 00:07:31,780 And then we are going to identify the neighbors of E which is D, C and f. 153 00:07:31,780 --> 00:07:36,700 Now among this d is the the node that we get when I is equal to zero. 154 00:07:36,700 --> 00:07:38,860 And we see that d is not yet visited. 155 00:07:38,860 --> 00:07:39,070 Right. 156 00:07:39,070 --> 00:07:42,460 So we are going to call DFS with D right. 157 00:07:42,460 --> 00:07:45,190 And then we have the option to call it with C. 158 00:07:45,370 --> 00:07:45,880 Do we have. 159 00:07:45,880 --> 00:07:46,090 No. 160 00:07:46,090 --> 00:07:46,870 It's already visited. 161 00:07:46,870 --> 00:07:48,610 So we don't have the option over here. 162 00:07:48,610 --> 00:07:50,110 And F is not yet visited. 163 00:07:50,110 --> 00:07:50,290 Right. 164 00:07:50,290 --> 00:07:51,790 So let me just write that over here. 165 00:07:51,790 --> 00:07:56,680 We have the option to call DFS later with F when I is equal to two. 166 00:07:56,710 --> 00:07:57,820 That will happen later. 167 00:07:57,820 --> 00:07:59,770 So at this point we are calling it with D. 168 00:07:59,770 --> 00:08:02,800 So again we come over here we push d to the output array. 169 00:08:02,800 --> 00:08:04,000 So we have D over here. 170 00:08:04,940 --> 00:08:06,830 And we mark D as visited. 171 00:08:06,830 --> 00:08:11,450 We identify the neighbors of D, which is C and E, and both of them are visited. 172 00:08:11,450 --> 00:08:11,660 Right. 173 00:08:11,660 --> 00:08:15,740 So in this for loop we do not call DFS and we come out right. 174 00:08:15,740 --> 00:08:17,000 So this call is over. 175 00:08:17,000 --> 00:08:21,710 Now once this call is over remember we had the option to call it with F also. 176 00:08:21,710 --> 00:08:21,950 Right. 177 00:08:21,950 --> 00:08:25,280 So for the neighbors E right we had d c and f. 178 00:08:25,280 --> 00:08:26,780 So for D it's done. 179 00:08:26,780 --> 00:08:28,430 See it was already done. 180 00:08:28,430 --> 00:08:29,780 Now we call it for f. 181 00:08:29,780 --> 00:08:33,080 So we call DFS for f which is this one over here. 182 00:08:33,080 --> 00:08:34,700 And we come over here. 183 00:08:34,700 --> 00:08:36,050 We push f to the output array. 184 00:08:36,050 --> 00:08:36,920 So we have f. 185 00:08:36,950 --> 00:08:38,330 You can see that over here. 186 00:08:40,460 --> 00:08:40,730 Right. 187 00:08:40,730 --> 00:08:43,970 We have F over here, so we push it to the output array. 188 00:08:43,970 --> 00:08:46,430 At that point we mark F as visited. 189 00:08:46,430 --> 00:08:48,800 So let's have our tick mark. 190 00:08:49,850 --> 00:08:53,450 And after that, we are going to identify the neighbors of F over here. 191 00:08:54,600 --> 00:08:58,020 Which is A and E, and both of them are already visited. 192 00:08:58,020 --> 00:09:03,810 So in this for loop we will not call the traverse recursively and this function is also done. 193 00:09:03,810 --> 00:09:04,860 So this is done. 194 00:09:04,860 --> 00:09:07,200 So d is done and f is done right. 195 00:09:07,200 --> 00:09:10,680 So this was part of the call where we had e right. 196 00:09:10,680 --> 00:09:15,510 So it was recursively calling it where the function was called with vertex e. 197 00:09:15,510 --> 00:09:16,920 So that part is done. 198 00:09:16,920 --> 00:09:18,840 And we have the option to call it with d. 199 00:09:18,840 --> 00:09:22,650 But we see that it is already visited, so we no longer need to visit it. 200 00:09:22,650 --> 00:09:25,380 And again C and B and F are already visited. 201 00:09:25,380 --> 00:09:25,680 Right. 202 00:09:25,680 --> 00:09:28,980 So we have already visited visited them B, C and F. 203 00:09:28,980 --> 00:09:32,250 So again these things this is not going to again call. 204 00:09:32,250 --> 00:09:33,690 And these are returning. 205 00:09:33,690 --> 00:09:34,980 And they will will be out of this. 206 00:09:34,980 --> 00:09:35,280 Right. 207 00:09:35,280 --> 00:09:39,150 So yes we got our output a b c, e D and f. 208 00:09:39,150 --> 00:09:41,220 So this is how our function works. 209 00:09:41,220 --> 00:09:43,560 Now what about the time complexity. 210 00:09:43,560 --> 00:09:47,220 The time complexity over here is O of v plus e right. 211 00:09:47,220 --> 00:09:47,700 Why is that. 212 00:09:47,700 --> 00:09:49,890 So let's take a look. 213 00:09:49,890 --> 00:09:53,550 So over here we can see that we are going to visit every node. 214 00:09:53,550 --> 00:09:53,730 Right. 215 00:09:53,730 --> 00:09:55,050 So we are visiting every node. 216 00:09:55,050 --> 00:09:59,850 That means traverse will be called for every node that is V operations. 217 00:09:59,850 --> 00:10:07,470 Now for each of these operations we have this for loop which will run for operations equal to its edges. 218 00:10:07,470 --> 00:10:07,710 Right. 219 00:10:07,710 --> 00:10:14,580 For example, when we call traverse with vertex a, this for loop there will operate two times. 220 00:10:14,580 --> 00:10:17,700 For I is equal to zero and one because the length over here is two right. 221 00:10:17,700 --> 00:10:20,340 So I has to take the value zero and one. 222 00:10:20,340 --> 00:10:25,920 Similarly, when we have the vertex b passed to it, this for loop will run two times. 223 00:10:25,920 --> 00:10:32,340 So in this way we can see that the for loop will run for a total of two into the number of edges. 224 00:10:32,340 --> 00:10:37,890 Let's just count that 123456789 ten 1112 1314. 225 00:10:37,890 --> 00:10:38,130 Right. 226 00:10:38,130 --> 00:10:41,430 So the for loop will operate for 14 times. 227 00:10:41,430 --> 00:10:44,880 And you can see we have one, two, three, four, five, six and seven. 228 00:10:44,880 --> 00:10:45,960 We have seven edges. 229 00:10:45,960 --> 00:10:48,660 So this 14 is nothing but two into edges. 230 00:10:48,660 --> 00:10:52,710 So we can say the time complexity is O of v plus two e. 231 00:10:52,770 --> 00:10:55,740 Now because two is a constant we can just remove it. 232 00:10:55,740 --> 00:11:02,430 That's why we get that the time complexity is O of v plus e, and the space complexity is O of V. 233 00:11:02,430 --> 00:11:02,700 Right. 234 00:11:02,700 --> 00:11:04,650 The space complexity over here is O of V. 235 00:11:04,680 --> 00:11:10,140 Why is that so one we have the output array which will be of length v which is the number of vertices. 236 00:11:10,140 --> 00:11:10,530 Right. 237 00:11:10,530 --> 00:11:12,690 And then we have this visited object. 238 00:11:12,690 --> 00:11:15,960 This also will have v number of key value pairs. 239 00:11:15,960 --> 00:11:19,260 So this is also taking space of the order of v. 240 00:11:19,830 --> 00:11:22,890 And then over here we have these recursive calls right. 241 00:11:22,890 --> 00:11:26,820 So in the worst case we can have v calls in the call stack. 242 00:11:26,820 --> 00:11:28,410 So what would be the worst case. 243 00:11:28,410 --> 00:11:34,470 Let's say the graph looked like this a b c, d, e and f. 244 00:11:36,710 --> 00:11:36,950 Right. 245 00:11:36,950 --> 00:11:39,110 So from eight will will go to B. 246 00:11:39,110 --> 00:11:40,550 From B we will go to C. 247 00:11:40,550 --> 00:11:44,000 From C we will go to D and from D to E and from E to F. 248 00:11:44,000 --> 00:11:47,960 So this is the worst case where we will have v calls on the call stack. 249 00:11:47,960 --> 00:11:53,480 So we can say that the space complexity is of the order of a constant into the number of vertices. 250 00:11:53,480 --> 00:11:55,700 And we can just remove the word constant. 251 00:11:55,700 --> 00:11:59,540 And therefore we get that the space complexity is of the order of V.