1 00:00:00,570 --> 00:00:01,590 Welcome back. 2 00:00:01,590 --> 00:00:08,100 Let's now go ahead and code the function which will traverse this graph over here with depth. 3 00:00:08,100 --> 00:00:08,970 First search. 4 00:00:08,970 --> 00:00:12,360 And we will implement this function in an iterative manner. 5 00:00:12,360 --> 00:00:16,140 So let's call this function graph DFS iterative. 6 00:00:17,810 --> 00:00:18,320 All right. 7 00:00:18,320 --> 00:00:22,970 And this function is going to take in the graph as a parameter. 8 00:00:22,970 --> 00:00:26,000 And we also need to mention the starting vertex. 9 00:00:26,000 --> 00:00:28,280 So these are the two parameters for this function. 10 00:00:28,280 --> 00:00:32,270 Now inside this function we will have the output array. 11 00:00:32,270 --> 00:00:34,730 So initially this is going to be an empty array. 12 00:00:34,730 --> 00:00:38,420 And then we will just traverse the graph and push values to it. 13 00:00:38,420 --> 00:00:40,520 And finally we will return this output array. 14 00:00:40,520 --> 00:00:42,440 So this is going to be our function. 15 00:00:42,440 --> 00:00:45,950 Now we also need a visited object. 16 00:00:45,950 --> 00:00:48,110 So let's say const visited. 17 00:00:48,110 --> 00:00:50,090 And initially it's going to be empty. 18 00:00:50,990 --> 00:00:54,920 Now when we call this function initially we are going to pass the start vertex. 19 00:00:54,920 --> 00:00:59,570 So we can at this point push this start to our stack. 20 00:00:59,570 --> 00:00:59,780 Right. 21 00:00:59,780 --> 00:01:04,160 We have discussed that to do DFS iteratively we will be using a stack. 22 00:01:04,160 --> 00:01:06,590 So again let's create that stack over here. 23 00:01:06,590 --> 00:01:08,630 Let's initialize it const stack. 24 00:01:08,900 --> 00:01:13,040 And when we initialize it itself we can push start to it. 25 00:01:13,040 --> 00:01:15,230 And we can mark start as visited. 26 00:01:15,230 --> 00:01:19,550 So we can say visited at start is equal to true. 27 00:01:20,390 --> 00:01:20,960 All right. 28 00:01:20,990 --> 00:01:23,510 Now we are going to have our while loop. 29 00:01:23,510 --> 00:01:28,730 And again let's have a variable current so that we don't again and again initialize it inside the while 30 00:01:28,730 --> 00:01:29,120 loop. 31 00:01:29,120 --> 00:01:33,320 Now this while loop will run so long as something is there in the stack. 32 00:01:33,320 --> 00:01:38,960 So while stack dot length greater than zero, the while loop will keep iterating or looping right? 33 00:01:38,960 --> 00:01:46,310 And then inside this we are going to identify the current value as the uh last in right. 34 00:01:46,310 --> 00:01:49,430 So the the last in structure stack is a linear structure. 35 00:01:49,430 --> 00:01:52,580 So what what came in last will be taken out first. 36 00:01:52,580 --> 00:01:55,940 So we are just going to pop the last element from the stack. 37 00:01:55,940 --> 00:01:57,710 So we can say stack.pop. 38 00:01:57,710 --> 00:02:01,730 So we remove the last element right last in first out. 39 00:02:01,730 --> 00:02:05,300 And we take that element and we are going to push it to our output array. 40 00:02:05,300 --> 00:02:08,870 So output dot push and current right. 41 00:02:08,870 --> 00:02:11,270 So we are going to push current to our output array. 42 00:02:11,270 --> 00:02:16,880 So this will ensure that we push to the output array children nodes before neighbor nodes. 43 00:02:16,880 --> 00:02:18,440 So that is why we are popping right. 44 00:02:18,440 --> 00:02:23,690 If you remember the BFS implementation we had a queue and we were taking from the beginning of the queue 45 00:02:23,690 --> 00:02:26,450 so that we have neighbors before children. 46 00:02:26,450 --> 00:02:30,320 But over here we are doing DFS and we want children before neighbors. 47 00:02:30,320 --> 00:02:32,270 That is why we are taking from the end. 48 00:02:32,270 --> 00:02:35,360 So that's why we have used a stack and hence we are popping over here. 49 00:02:35,360 --> 00:02:35,720 All right. 50 00:02:35,720 --> 00:02:40,520 So we pop the last element out, take the last element out and we push it to the output array. 51 00:02:40,520 --> 00:02:43,010 And then we are going to identify its neighbors. 52 00:02:43,010 --> 00:02:44,570 So we can say const. 53 00:02:45,390 --> 00:02:46,440 Neighbors. 54 00:02:47,510 --> 00:02:48,710 Is equal to. 55 00:02:48,710 --> 00:02:49,640 Graph. 56 00:02:50,280 --> 00:02:51,270 At current. 57 00:02:52,690 --> 00:02:53,020 All right. 58 00:02:53,020 --> 00:02:58,720 So for example if current is a then the neighbors would be this array over here which is b and f. 59 00:02:58,750 --> 00:02:59,260 All right. 60 00:02:59,260 --> 00:03:00,640 So we get an array over here. 61 00:03:00,640 --> 00:03:04,150 Now we are going to loop through this array using a for loop. 62 00:03:04,150 --> 00:03:11,980 So let's say for let I is equal to zero I less than neighbors dot length I plus plus. 63 00:03:11,980 --> 00:03:14,710 So we loop through the array neighbors. 64 00:03:14,710 --> 00:03:20,230 And we will take each neighbor and check if it's there in the visited hash table or not. 65 00:03:20,230 --> 00:03:26,800 So let's say if not visited at neighbors at I right. 66 00:03:26,800 --> 00:03:30,520 So neighbors at I will be one particular neighbor. 67 00:03:30,520 --> 00:03:34,990 So we are going to check whether that is there in our visited object or not or hash table. 68 00:03:34,990 --> 00:03:35,350 Right. 69 00:03:35,350 --> 00:03:40,600 So if it is not there, that is if this is undefined, that means there is no entry where the key is 70 00:03:40,600 --> 00:03:41,830 that particular neighbor. 71 00:03:41,830 --> 00:03:44,530 In that case we are going to push it to our stack. 72 00:03:44,530 --> 00:03:48,220 So stack dot push neighbors at I. 73 00:03:49,760 --> 00:03:50,210 All right. 74 00:03:50,210 --> 00:03:52,010 And then we're going to mark it as visited. 75 00:03:52,010 --> 00:03:57,290 So we say visited at neighbors at I is equal to true. 76 00:03:58,180 --> 00:04:00,250 So we mark it as visited and we're done. 77 00:04:00,250 --> 00:04:00,400 Right. 78 00:04:00,400 --> 00:04:01,750 So this is our function. 79 00:04:01,750 --> 00:04:07,120 So once we are out of the while loop we just have to return the output array which we keep building 80 00:04:07,120 --> 00:04:10,510 over here when we push the current value to the output array. 81 00:04:10,600 --> 00:04:11,080 All right. 82 00:04:11,080 --> 00:04:11,800 So that is it. 83 00:04:11,800 --> 00:04:14,080 Now let's go ahead and test our function. 84 00:04:14,080 --> 00:04:15,880 So we will call this function. 85 00:04:15,880 --> 00:04:18,430 And we will pass this adjacency list to it. 86 00:04:21,380 --> 00:04:25,910 And let's say we want to start traversing the graph at vertex A. 87 00:04:25,910 --> 00:04:28,040 So let's go ahead and run this function. 88 00:04:28,490 --> 00:04:30,290 And let's take a look at our output. 89 00:04:30,290 --> 00:04:33,590 We get a f e c d b which is correct. 90 00:04:33,590 --> 00:04:33,770 Right. 91 00:04:33,770 --> 00:04:37,640 So this is the same graph which we used in our explanation video. 92 00:04:37,640 --> 00:04:41,840 And we have seen that if we do a DFS search this is the output right. 93 00:04:41,840 --> 00:04:44,210 So this is the output that we got when we discussed it. 94 00:04:44,210 --> 00:04:47,000 And over here we have implemented it iteratively. 95 00:04:47,000 --> 00:04:49,310 So let's now draw this graph. 96 00:04:49,310 --> 00:04:53,840 And let's try to go ahead and look at the code and just walk through the code. 97 00:04:53,840 --> 00:04:55,790 So let's go ahead and do that now. 98 00:04:56,620 --> 00:04:57,070 All right. 99 00:04:57,070 --> 00:05:01,240 So I have just drawn this graph over here so that we can visualize it. 100 00:05:01,240 --> 00:05:06,160 Now let's try to trace the the code or walk through the code that we have written. 101 00:05:06,160 --> 00:05:09,850 Now we are calling the function and we are passing this graph to it. 102 00:05:09,850 --> 00:05:15,010 And we want to start traversing this graph over here DFS and iteratively. 103 00:05:15,010 --> 00:05:16,840 And we start at vertex A. 104 00:05:16,840 --> 00:05:18,160 So we are over here. 105 00:05:18,160 --> 00:05:19,630 This graph has been passed to it. 106 00:05:19,630 --> 00:05:21,370 And start is now vertex a. 107 00:05:21,370 --> 00:05:23,620 So output at this point is an empty array. 108 00:05:23,620 --> 00:05:25,330 So we have the output array over here. 109 00:05:25,330 --> 00:05:28,120 So let's see how we get each element to it. 110 00:05:28,120 --> 00:05:32,980 And then visited at this point is an empty object or an empty hash table. 111 00:05:32,980 --> 00:05:34,840 And then we have stack right. 112 00:05:34,840 --> 00:05:36,730 So let's just draw the stack over here. 113 00:05:36,730 --> 00:05:38,500 So the stack at this point. 114 00:05:39,910 --> 00:05:41,920 Has one element which is start. 115 00:05:41,920 --> 00:05:42,130 Right. 116 00:05:42,130 --> 00:05:45,910 So let me just write the stack over here we have start and start is a. 117 00:05:45,910 --> 00:05:49,120 So this is how our stack looks at this point. 118 00:05:49,120 --> 00:05:51,430 And we mark this as visited. 119 00:05:51,430 --> 00:05:51,610 Right. 120 00:05:51,610 --> 00:05:52,540 So A is visited. 121 00:05:52,540 --> 00:05:54,790 So I'm just having a tick mark over here. 122 00:05:54,790 --> 00:06:00,910 But this is going to be an entry in the hash table with the key A and the value as true. 123 00:06:00,910 --> 00:06:01,390 All right. 124 00:06:01,390 --> 00:06:04,990 So we come over here and we check whether there is something in the stack. 125 00:06:04,990 --> 00:06:06,190 Yes there is an element. 126 00:06:06,190 --> 00:06:08,830 So we come inside and we pop this element. 127 00:06:08,830 --> 00:06:11,800 So we take out a and we push it to our output array. 128 00:06:11,800 --> 00:06:13,420 So that is how we get a over here. 129 00:06:13,540 --> 00:06:16,270 Now we find the neighbors of a right. 130 00:06:16,270 --> 00:06:19,180 So for this we are going to make use of the adjacency list. 131 00:06:19,180 --> 00:06:24,670 So we come over here and we see that the neighbors of A are B and f which is these two. 132 00:06:24,670 --> 00:06:25,030 Right. 133 00:06:25,030 --> 00:06:28,720 So now we are going to check over here whether they are visited or not. 134 00:06:28,720 --> 00:06:30,370 We can see that they are not visited. 135 00:06:30,370 --> 00:06:30,640 Right. 136 00:06:30,640 --> 00:06:32,770 So only a has been visited so far. 137 00:06:32,770 --> 00:06:35,500 So we push B and F to the stack. 138 00:06:35,500 --> 00:06:35,830 Right. 139 00:06:35,830 --> 00:06:38,020 And again over here A is already popped out. 140 00:06:38,020 --> 00:06:41,890 So this is no longer there in the stack because we popped it out over here. 141 00:06:41,950 --> 00:06:49,240 Now over here at this point we are pushing the neighbors B and F to the stack, and it's going to be 142 00:06:49,240 --> 00:06:51,430 done in the order of storing it. 143 00:06:51,430 --> 00:06:54,940 So we have stored B ahead of F over here in the adjacency list. 144 00:06:54,940 --> 00:06:58,150 So we are going to push into the stack in this order. 145 00:06:58,150 --> 00:06:59,620 So let's just write that over here. 146 00:06:59,620 --> 00:07:05,920 So we are adding b and f these two into the stack because both of them are not visited. 147 00:07:05,920 --> 00:07:08,560 And we will mark both of them as visited. 148 00:07:08,560 --> 00:07:08,980 Right. 149 00:07:08,980 --> 00:07:10,540 So that is happening over here. 150 00:07:11,900 --> 00:07:12,650 In this part. 151 00:07:12,650 --> 00:07:12,830 Right. 152 00:07:12,830 --> 00:07:16,220 So we push them to the stack and we mark them as visited. 153 00:07:16,220 --> 00:07:17,300 So that is done. 154 00:07:17,300 --> 00:07:22,550 Now what we do, we come again over here and we see that the stack is not empty right. 155 00:07:22,550 --> 00:07:24,140 So we pop from the stack. 156 00:07:24,140 --> 00:07:26,960 So that means the stack is a data structure. 157 00:07:26,960 --> 00:07:28,490 So we take out from the end right. 158 00:07:28,490 --> 00:07:29,330 So we are popping. 159 00:07:29,330 --> 00:07:31,640 So we are taking out F at this point. 160 00:07:32,000 --> 00:07:35,810 So f is taken out and it is pushed to the to the output array. 161 00:07:35,810 --> 00:07:37,970 So that is how we have f over here. 162 00:07:37,970 --> 00:07:40,610 And then we find the neighbors of f. 163 00:07:40,610 --> 00:07:44,540 So again for this we use the adjacency list which is passed to the function. 164 00:07:44,540 --> 00:07:47,450 So the neighbors of f are a, b and e. 165 00:07:47,540 --> 00:07:50,060 Now we check whether they are visited. 166 00:07:50,060 --> 00:07:55,100 And we can see that A is already visited, B is already visited but E is not visited. 167 00:07:55,100 --> 00:07:59,360 So we push E to the stack and we mark E as visited. 168 00:07:59,360 --> 00:07:59,720 Right. 169 00:07:59,720 --> 00:08:01,250 So this happens over here. 170 00:08:02,190 --> 00:08:07,890 We pushed to the stack E and then we mark E as visited, which I'm denoting with this tick mark over 171 00:08:07,890 --> 00:08:08,310 here. 172 00:08:08,310 --> 00:08:10,260 And then again we come to the while loop. 173 00:08:10,260 --> 00:08:12,030 We check whether the stack is empty. 174 00:08:12,060 --> 00:08:15,570 We see that it is not empty, so we pop from the stack again. 175 00:08:15,570 --> 00:08:19,260 Remember, we are taking from the end because the stack is a data structure. 176 00:08:19,260 --> 00:08:20,430 Last in, first out. 177 00:08:20,430 --> 00:08:23,640 So we pop, we take out E and we push it to the output array. 178 00:08:23,640 --> 00:08:24,930 So we have E over here. 179 00:08:24,930 --> 00:08:27,630 And again we are finding the neighbors of E. 180 00:08:27,630 --> 00:08:31,680 And we can see that the neighbors of E are d, c and f. 181 00:08:31,680 --> 00:08:33,480 Now D is it visited. 182 00:08:33,480 --> 00:08:34,500 No it's not visited. 183 00:08:34,500 --> 00:08:35,340 So what do we do. 184 00:08:35,340 --> 00:08:37,770 We we push it to the stack. 185 00:08:37,770 --> 00:08:40,350 So we have D over here and we mark it as visited. 186 00:08:40,350 --> 00:08:42,240 The next one C is it visited. 187 00:08:42,240 --> 00:08:43,380 No it's not visited. 188 00:08:43,380 --> 00:08:46,260 So we mark it as visited and we push it to the stack. 189 00:08:46,260 --> 00:08:48,030 The next one is um. 190 00:08:49,490 --> 00:08:50,720 E uh, we are at E, right? 191 00:08:50,720 --> 00:08:52,670 The next, the next one is f. 192 00:08:52,670 --> 00:08:55,580 Now, F is already visited, so we don't push it to the stack. 193 00:08:55,580 --> 00:08:56,510 So that is done. 194 00:08:56,510 --> 00:08:58,580 So that happens over here right. 195 00:08:58,580 --> 00:08:59,360 That happens over here. 196 00:08:59,360 --> 00:09:05,090 We push to the stack and we mark as visited again we come over here we see that the stack is not empty. 197 00:09:05,090 --> 00:09:05,960 So we pop. 198 00:09:05,960 --> 00:09:07,160 We take from the n right. 199 00:09:07,160 --> 00:09:09,770 So we pop C and we push it to the output array. 200 00:09:09,770 --> 00:09:11,420 So that's how we have C over here. 201 00:09:11,420 --> 00:09:15,800 Again we come over here and we take the neighbors of C. 202 00:09:15,800 --> 00:09:18,020 You can see that the neighbors are B, E and d. 203 00:09:18,020 --> 00:09:20,240 Again we use the adjacency list to find that. 204 00:09:20,240 --> 00:09:22,130 And all of these are already visited. 205 00:09:22,130 --> 00:09:24,590 So we don't add anything to this stack. 206 00:09:24,590 --> 00:09:25,670 And that's it. 207 00:09:25,670 --> 00:09:29,720 So we come over here again we pop from the end which is D. 208 00:09:29,720 --> 00:09:31,250 And we push it to the output array. 209 00:09:31,250 --> 00:09:32,270 So we have D over here. 210 00:09:32,270 --> 00:09:37,490 We check the neighbors of D which is c and e and these are there or these are already visited right. 211 00:09:37,490 --> 00:09:39,350 So we don't add anything to the stack. 212 00:09:39,350 --> 00:09:43,730 And finally we pop B from the stack and we put it to the output array. 213 00:09:43,730 --> 00:09:49,040 And the neighbors of B, A, F and c are already visited, so nothing is added to the stack. 214 00:09:49,040 --> 00:09:56,330 Then when we come and check over here, we will see that the stack is empty and therefore we will come 215 00:09:56,330 --> 00:09:56,960 out of this. 216 00:09:56,960 --> 00:09:57,230 Right? 217 00:09:57,230 --> 00:09:58,580 So we come out of this. 218 00:09:59,260 --> 00:10:03,580 And at this point we will just return the output array, which is what we have over here. 219 00:10:03,580 --> 00:10:05,530 So this is how our function works. 220 00:10:05,530 --> 00:10:08,200 Now what about the space and time complexity. 221 00:10:08,200 --> 00:10:10,090 Let's have a quick look at that. 222 00:10:10,090 --> 00:10:15,640 So in this function we can see that we traverse or we visit every node once right. 223 00:10:15,640 --> 00:10:18,220 So or we visit every vertex once. 224 00:10:18,220 --> 00:10:21,490 So what is ensuring that it's this while loop over here. 225 00:10:21,490 --> 00:10:21,790 Right. 226 00:10:21,790 --> 00:10:28,000 So the stack this while loop over here will operate or will execute a number of times which is equal 227 00:10:28,000 --> 00:10:29,200 to the number of vertices. 228 00:10:29,200 --> 00:10:31,480 So we have the operations over there. 229 00:10:31,480 --> 00:10:37,780 And then over here every at every vertex we will have operations equal to its neighbors. 230 00:10:37,780 --> 00:10:38,110 Right. 231 00:10:38,110 --> 00:10:43,990 So if we add up all these operations we will get two times the number of edges operations. 232 00:10:43,990 --> 00:10:48,760 So this is the same thing that we have seen in the previous video where we did it recursively. 233 00:10:48,760 --> 00:10:53,380 So that's why the time complexity over here is O of v plus e. 234 00:10:53,500 --> 00:10:56,740 And the space complexity is going to be O of V. 235 00:10:56,740 --> 00:10:58,990 Because what's the extra space that we're using. 236 00:10:58,990 --> 00:11:03,460 We have this output array which is going to take space equal to the number of vertices. 237 00:11:03,460 --> 00:11:08,770 We have the visited object over here, which will have key value pairs equal to the number of vertices. 238 00:11:08,770 --> 00:11:10,390 And then we have the stack right. 239 00:11:10,390 --> 00:11:12,640 So in the worst case this stack. 240 00:11:12,640 --> 00:11:17,860 Also let's say this is a is also going to take space equal to order of V. 241 00:11:17,890 --> 00:11:18,820 How is that happening. 242 00:11:18,820 --> 00:11:25,300 Let's say you have a over here you have B over here C over here D over here E over here and F over here. 243 00:11:25,300 --> 00:11:31,690 You can see in this case when we come over here and we start with a and we check its neighbors and push 244 00:11:31,690 --> 00:11:33,700 the unvisited neighbors to the stack. 245 00:11:33,700 --> 00:11:36,580 We will be pushing all of these elements to the stack. 246 00:11:36,580 --> 00:11:41,590 So at that point the stack will have v minus one elements, which is of the order of V, right. 247 00:11:41,590 --> 00:11:44,110 Because one is a constant and we can just remove it. 248 00:11:44,110 --> 00:11:50,170 So that's why we can say that the space complexity is is of the order of a constant into V, and we 249 00:11:50,170 --> 00:11:54,760 can just remove the constant and we get that the space complexity is O of V.