what's up guys welcome back to O'Neil
code today we're going to go over the
difference between a depth-first search
and a breadth first search on the graph
these are both important concepts to
fully understand on graphs work and you
get some practice using stacks and
queues so let's look at this example
graph the objective of these two
searching algorithms hit every vertex
just one time you not want to look at
the vertex multiple times so we can cut
down the overall run time of our
algorithm we can first start by looking
at the depth-first search or DFS this
will take advantage of a stack to track
the order of where we have been in what
we need to look at we in first started
vertex 1 since we're looking at this
vertex we need to somehow alert
ourselves that we've been here we can
push onto the stack and mark it on the
graph that is visited since it's now
marking it visited we can look at the
vertices that are connected we have 2 3
& 6 we're going to take the smallest
value which is 2 and do the same we just
did with vertex 1 we're gonna push onto
the stack then mark it as visited so now
on our stack we have two on top and one
on the bottom we now check which vertex
is smallest that connects to 2 since
only it's 3 and 5 that are not visited
we move on to vertex 3 we push on to the
stack and mark it as visited now looking
at the graph there are no vertices
connected to 3 that have not been
visited since this is the case we can
pop 3 off the top of the stack this
brings us back to vertex 2 we again need
to find the smallest vertex connected to
2 that has not been visited since 5 is
the only non visited vertex connected we
move there we push 5 on to the stack and
mark it as visited we now need to look
at vertices 4 & 6 since 4 is smaller we
move there we push forth to the stack
and we mark it as visited so we look at
vertex 4 since 4 is only connected to
vertex 5 which has already been visited
we can pop that off the top of the stack
this brings us back to vertex 5 since
it's a new top of the stack we look at
the connected vertices and see it 6 is
the only non visited vertex left 4 5 we
can move there push 6 on top of the
stack and mark it as visited since 6 is
known on
vertices we pop that off the top of the
stack this moves us back to vertex 5
vertex 5 does not have any non visited
vertices so we can pop that off the top
of the stack this moves us back to
vertex 2 this is not have any non
visited vertices so we can pop that off
the top of the stack as well now this
brings us back to our starting vertex
which is 1 there are no vertices that we
can hit so we pop that off the top of
the stack this leaves us with an empty
stack and we visited every vertex in the
graph and that is how we complete DFS if
we were looking for any vertex in this
graph we would have found it because we
eventually hit every vertex now we can
move on the breadth-first search or BFS
this algorithm is going to take
advantage of a queue unlike depth-first
search which uses a stack if you know
the difference between a stack and a
queue you can imagine the difference in
these two algorithms
since the stack is last in first out we
always took the vertex off the top of
the stack and move back to the one below
a queue is first-in first-out
which means we will take the first
vertex we add to the queue and pump that
out let's look at the graph again and
walk through what this really means we
again look at vertex 1 to start we are
going to add one to the queue and market
as visited then we're gonna do the same
thing we do a depth first search in
finding the next smallest vertex since 2
is the next smallest we can add that to
the queue and mark it as visited but
this time instead of going to vertex 2
we're going to stay at vertex 1 we're
going to keep looking at the vertices
connected to it
we have 3 & 6 left since 3 is a smallest
we're gonna move that to the queue and
mark it as visited so again we're gonna
stay at 1 and look for the remaining
vertices that have not been visited
since 6 is the only one left we move
that to the queue and market as visited
now all the connected vertices to wander
visited we're gonna remove one from the
queue since it's a first vertex added
this is the first in first out that
queues are based around this means we
move to the new head of the queue which
is 2 we begin the process again we look
at the connected vertices and we have 1
3 & 5 since 5 is the only one that has
been visited
we add that to the queue and market is
visited since there are no more non
visited vertices connected to two we
remove her from the queue and move to
the new head which is three now looking
at the graph we can see this three has
no new vertices to look at so we can
also remove that from the queue this
moves us to vertex six since it's a new
head of the queue this also has no new
vertices so we can remove it from the
queue and move to the new head which is
five now five has a non visited vertex
which is four so we can add that to the
queue and market is visited since there
are no more vertices to hit from five we
can remove it from the queue this will
use us to vertex four since this has no
vertices we can move to we removed from
the queue so now the queue is empty
which means we used up all the
connections possible we visit every
vertex and this completes breadth-first
search now that you have both algorithms
you may be wondering which one you
should use to search the tree well this
completely depends on the graph you are
given if you know that the vertex you
are searching for is relatively close to
the root you're going to choose
breadth-first search because it checks
all the children before going deep into
the graph but if you know that the
vertex is deep into the graph you're
going to choose depth-first search
because it goes further down the levels
of the graph so hopefully now you
understand how to search graphs if you
liked the video please give the thumbs
up and if you want to see more videos
from me hit that subscribe button
peace out