1 00:00:00,780 --> 00:00:01,800 Welcome back. 2 00:00:01,800 --> 00:00:08,220 Let's now see how we can implement the DFS or depth first search algorithm iteratively. 3 00:00:08,220 --> 00:00:10,380 So we have our graph over here. 4 00:00:10,380 --> 00:00:12,930 And it is stored as an adjacency list. 5 00:00:12,960 --> 00:00:18,210 Now to implement the DFS algorithm iteratively we will use a stack. 6 00:00:18,210 --> 00:00:22,350 Now a stack is a lifer or last in first out data structure. 7 00:00:22,350 --> 00:00:24,510 So initially our stack is empty. 8 00:00:24,510 --> 00:00:29,220 And let's say we want to start to traverse the graph at vertex A. 9 00:00:29,220 --> 00:00:30,840 So we are starting over here. 10 00:00:30,840 --> 00:00:35,100 Now what we will do is we will push this to our stack. 11 00:00:35,100 --> 00:00:36,870 So let's have it in our stack. 12 00:00:37,560 --> 00:00:39,990 And we also need an output array. 13 00:00:39,990 --> 00:00:43,410 So let's say this is our output array which is empty at this point. 14 00:00:43,410 --> 00:00:47,700 And then once we push a to our stack we will mark it as visited. 15 00:00:47,700 --> 00:00:49,260 So A is now visited. 16 00:00:49,260 --> 00:00:52,110 And what we will do is we will have a while loop. 17 00:00:52,110 --> 00:00:57,060 So this is the difference between BFS and DFS when we implement implemented iteratively. 18 00:00:57,090 --> 00:01:03,300 Now again we have a while loop similar to the case of BFS where we check if something is in the stack 19 00:01:03,300 --> 00:01:06,780 and as long as something is in the stack, we will keep looping. 20 00:01:06,780 --> 00:01:08,550 So this is our while loop. 21 00:01:08,550 --> 00:01:11,310 Now at this point we have something in our stack. 22 00:01:11,310 --> 00:01:15,360 So we will pop from the stack and we will push it to the output array. 23 00:01:15,360 --> 00:01:16,950 So this is the difference. 24 00:01:17,810 --> 00:01:18,200 All right. 25 00:01:18,200 --> 00:01:21,110 So in the case of BFS we had a queue. 26 00:01:21,110 --> 00:01:25,640 And a queue is a Fifo or first in first out data structure. 27 00:01:25,640 --> 00:01:28,610 So we used to take from the first or from the beginning. 28 00:01:28,610 --> 00:01:28,910 Right. 29 00:01:28,910 --> 00:01:31,100 But over here we're going to pop right. 30 00:01:31,100 --> 00:01:33,680 So we are going to take from the end of the stack. 31 00:01:33,680 --> 00:01:37,760 So this will ensure that we get children before neighbors. 32 00:01:37,760 --> 00:01:41,540 So let's trace the algorithm and this will become more clear. 33 00:01:41,540 --> 00:01:43,880 So at this point it just has one element. 34 00:01:43,880 --> 00:01:46,970 So we pop A and we push it to the output array. 35 00:01:46,970 --> 00:01:48,140 So we have a over here. 36 00:01:48,140 --> 00:01:50,660 And then we are going to check the neighbors of a. 37 00:01:50,660 --> 00:01:50,840 Right. 38 00:01:50,840 --> 00:01:53,360 So the neighbors of A are B and f. 39 00:01:53,360 --> 00:01:56,210 And to check this we use the adjacency list. 40 00:01:56,240 --> 00:01:59,600 Now we are going to check whether these are already visited. 41 00:01:59,600 --> 00:02:06,770 And if not we will push them to the stack so we can see that b and F as at this moment are not visited. 42 00:02:06,770 --> 00:02:09,440 So let's push b and f to the stack. 43 00:02:09,440 --> 00:02:11,300 So we get B and f over here. 44 00:02:11,300 --> 00:02:11,810 All right. 45 00:02:11,810 --> 00:02:13,400 And we mark them as visited. 46 00:02:13,400 --> 00:02:17,180 Now again we are over here and we check if the stack is empty. 47 00:02:17,180 --> 00:02:18,440 No it's not empty. 48 00:02:18,440 --> 00:02:21,860 So we come inside the while loop and we are going to pop. 49 00:02:21,860 --> 00:02:26,690 So popping means we are going to take the last element right which is F at this point. 50 00:02:26,690 --> 00:02:31,100 And this will help us get children before neighbors. 51 00:02:31,100 --> 00:02:36,200 So we are going to take f, we are taking from the end of the stack because the stack is a leaf, right 52 00:02:36,200 --> 00:02:38,360 last in first out data structure. 53 00:02:38,360 --> 00:02:41,780 So we take out F and we push it to our output array. 54 00:02:42,480 --> 00:02:46,110 And we are going to check the neighbors of F, which is A and E. 55 00:02:46,140 --> 00:02:49,680 Now you can see that A is already visited, but E is not visited. 56 00:02:49,680 --> 00:02:53,790 So we push E to the stack and we mark E as visited. 57 00:02:53,790 --> 00:02:54,120 Again. 58 00:02:54,120 --> 00:02:56,670 We come inside and we are going to pop from the stack. 59 00:02:56,670 --> 00:03:00,180 That is, we are going to take the last element which is E at this point. 60 00:03:00,180 --> 00:03:03,210 So we take E and we push it to the output array. 61 00:03:03,210 --> 00:03:07,410 And then we are going to check the neighbors of E which is D, C and f. 62 00:03:07,410 --> 00:03:11,790 Now among these we can see that, uh, none of them are visited. 63 00:03:11,790 --> 00:03:12,000 Right. 64 00:03:12,000 --> 00:03:14,280 So d c and f okay f is visited. 65 00:03:14,280 --> 00:03:17,460 So we have f as visited, but d and C are not visited. 66 00:03:17,460 --> 00:03:17,760 Right. 67 00:03:17,760 --> 00:03:22,020 So again at this point we are going to push d and C to our stack. 68 00:03:22,020 --> 00:03:23,010 So let's do that. 69 00:03:23,010 --> 00:03:25,470 And we mark D and C as visited. 70 00:03:25,590 --> 00:03:27,930 And again we check whether the stack is empty. 71 00:03:27,960 --> 00:03:29,220 No it is not empty. 72 00:03:29,220 --> 00:03:30,450 And we are going to pop. 73 00:03:30,450 --> 00:03:32,010 So we come inside the while loop. 74 00:03:32,010 --> 00:03:33,450 And we are going to take from the end. 75 00:03:33,450 --> 00:03:33,750 Right. 76 00:03:33,750 --> 00:03:39,330 So it is this that makes this DFS right depth first because we are always taking from the end of the 77 00:03:39,330 --> 00:03:39,780 stack. 78 00:03:39,780 --> 00:03:42,270 So we get children before neighbors. 79 00:03:42,270 --> 00:03:44,760 So at this point we are going to pop. 80 00:03:44,760 --> 00:03:47,580 So we get C and we push it to the output array. 81 00:03:47,580 --> 00:03:49,650 And we are going to check the neighbors of C. 82 00:03:49,680 --> 00:03:55,680 We get b, E and d, we see that B, E and d are already visited, so we don't push anything to the 83 00:03:55,680 --> 00:03:56,190 stack. 84 00:03:56,190 --> 00:03:59,070 So we come again to the while condition. 85 00:03:59,070 --> 00:04:03,300 We see that the stack is not empty, so we pop from the stack, which is D. 86 00:04:03,300 --> 00:04:05,610 At this point we push it to the output array. 87 00:04:05,610 --> 00:04:12,720 We check the neighbors of D, which is C and E and C and E are already there, so we do not push anything 88 00:04:12,720 --> 00:04:13,440 to the stack. 89 00:04:13,440 --> 00:04:16,410 And after that again we check whether the stack is empty. 90 00:04:16,440 --> 00:04:17,670 No, it's not empty. 91 00:04:17,700 --> 00:04:19,110 We still have one element. 92 00:04:19,110 --> 00:04:22,500 So we pop that and we push it to our output array. 93 00:04:22,500 --> 00:04:26,370 We check the neighbors of B, which is A and C and A and C are already visited. 94 00:04:26,370 --> 00:04:31,290 So that brings us to the end, because when we come again and check over here, we will see that the 95 00:04:31,290 --> 00:04:32,940 stack is empty and we are done. 96 00:04:32,940 --> 00:04:36,810 And this is our output array which is a f e c d b. 97 00:04:37,660 --> 00:04:42,040 So you can see that DFS iteratively is implemented using a stack. 98 00:04:42,040 --> 00:04:44,350 So what we do is we start somewhere. 99 00:04:44,350 --> 00:04:48,220 We push it to the stack, we mark it as visited and we check its neighbors. 100 00:04:48,220 --> 00:04:51,820 So if there are neighbors which are not visited we push it to the stack. 101 00:04:51,820 --> 00:04:52,150 Right. 102 00:04:52,150 --> 00:04:58,330 But then when we again come over here, we always pop or we take from the end of the stack, which will 103 00:04:58,330 --> 00:05:01,120 ensure that we get children before neighbors. 104 00:05:01,120 --> 00:05:03,400 And that is the depth first search. 105 00:05:03,400 --> 00:05:04,000 All right. 106 00:05:04,000 --> 00:05:09,670 Now let's quickly take a look at the complexity analysis of this solution where we are doing DFS search 107 00:05:09,670 --> 00:05:10,570 iteratively. 108 00:05:10,570 --> 00:05:16,810 Now the time complexity of this solution is of the order of V plus E, where v is the number of vertices 109 00:05:16,810 --> 00:05:18,460 and e is the number of edges. 110 00:05:18,490 --> 00:05:23,440 Now the time complexity is O of v plus e, because over here we have this while loop right. 111 00:05:23,440 --> 00:05:29,290 So this while loop will operate a total of v number of times one time for each vertex. 112 00:05:29,290 --> 00:05:31,180 So we have v operations over here. 113 00:05:31,180 --> 00:05:34,420 So this is used to traverse every vertex right. 114 00:05:34,420 --> 00:05:37,450 And then inside we pop and we push it to the output array. 115 00:05:37,450 --> 00:05:45,550 Now over here we have E because of this for loop over here where we use it to check whether it's the 116 00:05:45,550 --> 00:05:48,790 neighbors of that particular vertex is visited or not. 117 00:05:48,790 --> 00:05:52,840 So you can see that we will iterate for every edge of the vertex, right. 118 00:05:53,470 --> 00:05:55,930 Because we use the adjacency list. 119 00:05:55,930 --> 00:06:02,320 So for example, if we are at vertex A we will do two checks for b and f to see whether it is visited 120 00:06:02,320 --> 00:06:02,800 or not. 121 00:06:02,800 --> 00:06:05,170 Similarly, over here also we will do two checks. 122 00:06:05,170 --> 00:06:10,690 Now if we add all of these together up all of these operations together, we will get a total of two 123 00:06:10,720 --> 00:06:12,400 into E number of operations. 124 00:06:12,400 --> 00:06:18,160 So we can say that the time complexity is O of V plus two E because two is a constant, we can just 125 00:06:18,160 --> 00:06:18,670 remove it. 126 00:06:18,670 --> 00:06:22,900 And we can say that the time complexity is of the order of V plus e. 127 00:06:23,170 --> 00:06:25,300 Now what about the space complexity? 128 00:06:25,300 --> 00:06:28,780 The space complexity of this solution is of the order of V. 129 00:06:28,780 --> 00:06:31,240 Now what are the things that take extra space? 130 00:06:31,240 --> 00:06:35,920 We have the visited object, we have the stack, and then we have the output array. 131 00:06:35,920 --> 00:06:41,140 Right now, even if we did not want an output array as per the question, let's say we modify the question 132 00:06:41,140 --> 00:06:45,880 and we don't want to output the traversed path as an output array. 133 00:06:45,880 --> 00:06:51,160 Even in that case, the space complexity would be of the order of V, because we have this visited object 134 00:06:51,160 --> 00:06:54,550 which will have v number of key value pairs. 135 00:06:54,550 --> 00:06:58,030 And then we have this stack over here right now in the worst case. 136 00:06:58,030 --> 00:07:01,720 And again when we do a Big-O analysis we always give the worst case. 137 00:07:01,720 --> 00:07:02,080 Right. 138 00:07:02,080 --> 00:07:05,590 So in the worst case what's the stack going to look like. 139 00:07:05,590 --> 00:07:07,750 Let's take a look at that. 140 00:07:07,750 --> 00:07:13,510 Let's say the graph is something like this where A is connected to B and it's connected to c, d, e 141 00:07:13,510 --> 00:07:14,050 and f. 142 00:07:14,050 --> 00:07:21,250 So in this case when the current vertex is a and we visit the neighbors and push the non visited neighbors 143 00:07:21,250 --> 00:07:24,100 to our stack, all of these would be pushed to the stack, right. 144 00:07:24,100 --> 00:07:29,050 So that would be a total of total of V minus one number of elements in our stack. 145 00:07:29,050 --> 00:07:30,490 And one is just a constant. 146 00:07:30,490 --> 00:07:31,660 So we can avoid that. 147 00:07:31,660 --> 00:07:35,830 And in this case we can see that the stack also takes O of v space. 148 00:07:35,830 --> 00:07:42,040 So we can see that the space complexity of this solution will be O of a constant into V, and we can 149 00:07:42,040 --> 00:07:43,210 just remove the constant. 150 00:07:43,210 --> 00:07:46,780 And we get that the space complexity is equal to O of V.