1 00:00:00,030 --> 00:00:03,629 what's up guys welcome back to O'Neil 2 00:00:02,009 --> 00:00:04,980 code today we're going to go over the 3 00:00:03,629 --> 00:00:06,798 difference between a depth-first search 4 00:00:04,980 --> 00:00:09,179 and a breadth first search on the graph 5 00:00:06,799 --> 00:00:11,070 these are both important concepts to 6 00:00:09,179 --> 00:00:12,509 fully understand on graphs work and you 7 00:00:11,070 --> 00:00:14,820 get some practice using stacks and 8 00:00:12,509 --> 00:00:17,100 queues so let's look at this example 9 00:00:14,820 --> 00:00:19,050 graph the objective of these two 10 00:00:17,100 --> 00:00:21,510 searching algorithms hit every vertex 11 00:00:19,050 --> 00:00:23,160 just one time you not want to look at 12 00:00:21,510 --> 00:00:24,510 the vertex multiple times so we can cut 13 00:00:23,160 --> 00:00:26,849 down the overall run time of our 14 00:00:24,510 --> 00:00:29,970 algorithm we can first start by looking 15 00:00:26,849 --> 00:00:31,679 at the depth-first search or DFS this 16 00:00:29,969 --> 00:00:33,299 will take advantage of a stack to track 17 00:00:31,678 --> 00:00:35,759 the order of where we have been in what 18 00:00:33,299 --> 00:00:38,099 we need to look at we in first started 19 00:00:35,759 --> 00:00:39,750 vertex 1 since we're looking at this 20 00:00:38,100 --> 00:00:42,000 vertex we need to somehow alert 21 00:00:39,750 --> 00:00:43,769 ourselves that we've been here we can 22 00:00:42,000 --> 00:00:46,019 push onto the stack and mark it on the 23 00:00:43,770 --> 00:00:47,609 graph that is visited since it's now 24 00:00:46,020 --> 00:00:50,160 marking it visited we can look at the 25 00:00:47,609 --> 00:00:52,500 vertices that are connected we have 2 3 26 00:00:50,159 --> 00:00:54,599 & 6 we're going to take the smallest 27 00:00:52,500 --> 00:00:57,210 value which is 2 and do the same we just 28 00:00:54,600 --> 00:01:00,030 did with vertex 1 we're gonna push onto 29 00:00:57,210 --> 00:01:01,890 the stack then mark it as visited so now 30 00:01:00,030 --> 00:01:04,650 on our stack we have two on top and one 31 00:01:01,890 --> 00:01:07,290 on the bottom we now check which vertex 32 00:01:04,650 --> 00:01:09,630 is smallest that connects to 2 since 33 00:01:07,290 --> 00:01:13,110 only it's 3 and 5 that are not visited 34 00:01:09,629 --> 00:01:15,959 we move on to vertex 3 we push on to the 35 00:01:13,109 --> 00:01:17,400 stack and mark it as visited now looking 36 00:01:15,959 --> 00:01:18,750 at the graph there are no vertices 37 00:01:17,400 --> 00:01:21,659 connected to 3 that have not been 38 00:01:18,750 --> 00:01:24,509 visited since this is the case we can 39 00:01:21,659 --> 00:01:27,420 pop 3 off the top of the stack this 40 00:01:24,509 --> 00:01:29,368 brings us back to vertex 2 we again need 41 00:01:27,420 --> 00:01:32,040 to find the smallest vertex connected to 42 00:01:29,368 --> 00:01:34,680 2 that has not been visited since 5 is 43 00:01:32,040 --> 00:01:37,560 the only non visited vertex connected we 44 00:01:34,680 --> 00:01:39,960 move there we push 5 on to the stack and 45 00:01:37,560 --> 00:01:43,320 mark it as visited we now need to look 46 00:01:39,959 --> 00:01:45,899 at vertices 4 & 6 since 4 is smaller we 47 00:01:43,319 --> 00:01:48,419 move there we push forth to the stack 48 00:01:45,899 --> 00:01:51,329 and we mark it as visited so we look at 49 00:01:48,420 --> 00:01:52,978 vertex 4 since 4 is only connected to 50 00:01:51,328 --> 00:01:55,578 vertex 5 which has already been visited 51 00:01:52,978 --> 00:01:58,408 we can pop that off the top of the stack 52 00:01:55,578 --> 00:02:01,139 this brings us back to vertex 5 since 53 00:01:58,409 --> 00:02:03,299 it's a new top of the stack we look at 54 00:02:01,140 --> 00:02:07,228 the connected vertices and see it 6 is 55 00:02:03,299 --> 00:02:09,479 the only non visited vertex left 4 5 we 56 00:02:07,228 --> 00:02:12,689 can move there push 6 on top of the 57 00:02:09,479 --> 00:02:13,530 stack and mark it as visited since 6 is 58 00:02:12,689 --> 00:02:16,199 known on 59 00:02:13,530 --> 00:02:18,919 vertices we pop that off the top of the 60 00:02:16,199 --> 00:02:21,569 stack this moves us back to vertex 5 61 00:02:18,919 --> 00:02:23,609 vertex 5 does not have any non visited 62 00:02:21,569 --> 00:02:26,159 vertices so we can pop that off the top 63 00:02:23,610 --> 00:02:29,220 of the stack this moves us back to 64 00:02:26,159 --> 00:02:31,620 vertex 2 this is not have any non 65 00:02:29,219 --> 00:02:34,229 visited vertices so we can pop that off 66 00:02:31,620 --> 00:02:35,610 the top of the stack as well now this 67 00:02:34,229 --> 00:02:38,909 brings us back to our starting vertex 68 00:02:35,610 --> 00:02:40,920 which is 1 there are no vertices that we 69 00:02:38,909 --> 00:02:43,439 can hit so we pop that off the top of 70 00:02:40,919 --> 00:02:46,079 the stack this leaves us with an empty 71 00:02:43,439 --> 00:02:49,620 stack and we visited every vertex in the 72 00:02:46,080 --> 00:02:51,719 graph and that is how we complete DFS if 73 00:02:49,620 --> 00:02:53,550 we were looking for any vertex in this 74 00:02:51,719 --> 00:02:56,250 graph we would have found it because we 75 00:02:53,550 --> 00:02:58,489 eventually hit every vertex now we can 76 00:02:56,250 --> 00:03:00,419 move on the breadth-first search or BFS 77 00:02:58,489 --> 00:03:02,430 this algorithm is going to take 78 00:03:00,419 --> 00:03:04,949 advantage of a queue unlike depth-first 79 00:03:02,430 --> 00:03:06,209 search which uses a stack if you know 80 00:03:04,949 --> 00:03:07,889 the difference between a stack and a 81 00:03:06,209 --> 00:03:08,810 queue you can imagine the difference in 82 00:03:07,889 --> 00:03:12,089 these two algorithms 83 00:03:08,810 --> 00:03:13,709 since the stack is last in first out we 84 00:03:12,090 --> 00:03:15,569 always took the vertex off the top of 85 00:03:13,709 --> 00:03:17,939 the stack and move back to the one below 86 00:03:15,569 --> 00:03:19,439 a queue is first-in first-out 87 00:03:17,939 --> 00:03:21,479 which means we will take the first 88 00:03:19,439 --> 00:03:23,909 vertex we add to the queue and pump that 89 00:03:21,479 --> 00:03:26,069 out let's look at the graph again and 90 00:03:23,909 --> 00:03:28,650 walk through what this really means we 91 00:03:26,069 --> 00:03:30,269 again look at vertex 1 to start we are 92 00:03:28,650 --> 00:03:32,340 going to add one to the queue and market 93 00:03:30,269 --> 00:03:34,049 as visited then we're gonna do the same 94 00:03:32,340 --> 00:03:37,049 thing we do a depth first search in 95 00:03:34,049 --> 00:03:38,670 finding the next smallest vertex since 2 96 00:03:37,049 --> 00:03:40,950 is the next smallest we can add that to 97 00:03:38,669 --> 00:03:42,839 the queue and mark it as visited but 98 00:03:40,949 --> 00:03:45,479 this time instead of going to vertex 2 99 00:03:42,840 --> 00:03:46,650 we're going to stay at vertex 1 we're 100 00:03:45,479 --> 00:03:47,729 going to keep looking at the vertices 101 00:03:46,650 --> 00:03:51,180 connected to it 102 00:03:47,729 --> 00:03:53,039 we have 3 & 6 left since 3 is a smallest 103 00:03:51,180 --> 00:03:55,530 we're gonna move that to the queue and 104 00:03:53,039 --> 00:03:57,389 mark it as visited so again we're gonna 105 00:03:55,530 --> 00:03:58,919 stay at 1 and look for the remaining 106 00:03:57,389 --> 00:04:01,949 vertices that have not been visited 107 00:03:58,919 --> 00:04:03,899 since 6 is the only one left we move 108 00:04:01,949 --> 00:04:06,539 that to the queue and market as visited 109 00:04:03,900 --> 00:04:08,849 now all the connected vertices to wander 110 00:04:06,539 --> 00:04:10,828 visited we're gonna remove one from the 111 00:04:08,849 --> 00:04:13,199 queue since it's a first vertex added 112 00:04:10,829 --> 00:04:15,480 this is the first in first out that 113 00:04:13,199 --> 00:04:16,829 queues are based around this means we 114 00:04:15,479 --> 00:04:20,370 move to the new head of the queue which 115 00:04:16,829 --> 00:04:22,259 is 2 we begin the process again we look 116 00:04:20,370 --> 00:04:25,319 at the connected vertices and we have 1 117 00:04:22,259 --> 00:04:26,670 3 & 5 since 5 is the only one that has 118 00:04:25,319 --> 00:04:28,290 been visited 119 00:04:26,670 --> 00:04:30,420 we add that to the queue and market is 120 00:04:28,290 --> 00:04:33,000 visited since there are no more non 121 00:04:30,420 --> 00:04:34,800 visited vertices connected to two we 122 00:04:33,000 --> 00:04:37,290 remove her from the queue and move to 123 00:04:34,800 --> 00:04:38,879 the new head which is three now looking 124 00:04:37,290 --> 00:04:41,160 at the graph we can see this three has 125 00:04:38,879 --> 00:04:43,560 no new vertices to look at so we can 126 00:04:41,160 --> 00:04:46,080 also remove that from the queue this 127 00:04:43,560 --> 00:04:48,629 moves us to vertex six since it's a new 128 00:04:46,079 --> 00:04:50,250 head of the queue this also has no new 129 00:04:48,629 --> 00:04:52,199 vertices so we can remove it from the 130 00:04:50,250 --> 00:04:55,529 queue and move to the new head which is 131 00:04:52,199 --> 00:04:58,139 five now five has a non visited vertex 132 00:04:55,529 --> 00:05:00,659 which is four so we can add that to the 133 00:04:58,139 --> 00:05:02,759 queue and market is visited since there 134 00:05:00,660 --> 00:05:04,920 are no more vertices to hit from five we 135 00:05:02,759 --> 00:05:07,829 can remove it from the queue this will 136 00:05:04,920 --> 00:05:09,960 use us to vertex four since this has no 137 00:05:07,829 --> 00:05:12,389 vertices we can move to we removed from 138 00:05:09,959 --> 00:05:14,069 the queue so now the queue is empty 139 00:05:12,389 --> 00:05:16,469 which means we used up all the 140 00:05:14,069 --> 00:05:18,269 connections possible we visit every 141 00:05:16,470 --> 00:05:21,150 vertex and this completes breadth-first 142 00:05:18,269 --> 00:05:22,349 search now that you have both algorithms 143 00:05:21,149 --> 00:05:24,509 you may be wondering which one you 144 00:05:22,350 --> 00:05:25,950 should use to search the tree well this 145 00:05:24,509 --> 00:05:28,110 completely depends on the graph you are 146 00:05:25,949 --> 00:05:29,849 given if you know that the vertex you 147 00:05:28,110 --> 00:05:31,410 are searching for is relatively close to 148 00:05:29,850 --> 00:05:33,330 the root you're going to choose 149 00:05:31,410 --> 00:05:34,950 breadth-first search because it checks 150 00:05:33,329 --> 00:05:37,079 all the children before going deep into 151 00:05:34,949 --> 00:05:39,029 the graph but if you know that the 152 00:05:37,079 --> 00:05:40,229 vertex is deep into the graph you're 153 00:05:39,029 --> 00:05:42,149 going to choose depth-first search 154 00:05:40,230 --> 00:05:44,520 because it goes further down the levels 155 00:05:42,149 --> 00:05:46,919 of the graph so hopefully now you 156 00:05:44,519 --> 00:05:48,419 understand how to search graphs if you 157 00:05:46,920 --> 00:05:49,949 liked the video please give the thumbs 158 00:05:48,420 --> 00:05:51,360 up and if you want to see more videos 159 00:05:49,949 --> 00:05:54,379 from me hit that subscribe button 160 00:05:51,360 --> 00:05:54,379 peace out