Tip:
Highlight text to annotate it
X
for the next demonstration on the graph data structure we're going to start
taking a look at some graph algorithms
and we're going to start out with it depth-first traversal out at first for
so requires
stack so give ourselves place too draw stack
start from the bottom and work our way up from here
now the depth-first traversal
in this case is quite sort out at vertex A and the first thing we're going
to do
its right to take the vertex a we're going to push it onto the stack
we're going to visit and we're going to market this as visited
ok
now we take a look at the vertex at the top of the stack
A and
all vertices adjacent to it that haven't yet been decided that's B
D and G and we're gonna visit the first of these in alphabetical order
which is B so we take the vertex B
we push it onto the stack b visited
and we market as visited
and now we repeat the procedure we take a look at the vertex
top stack be we take a look at all
the Jason on visited foresees well
is already been visited so that just leaves in F we pick the one that
alphabetically least in this case he push on
stack dissident
aunt market is visited
now once again at the top of the stack we have
E we take a look at a chastened and visited vertices
in this case be is already visited the only one we have is Chi
pushed shiite top stack
we visit she and we park cheese visited
now the vertex on the top of the stack is Chi
we find all adjacent and visited vertices
well both and he is already been visited so that means that there's no place to
go from G
we're going to top it off the top stack we should expect
he to notice where going backwards our past
now he also
has no adjacent and visited for seats are going to pop it off to stack
which takes us back to be
now from be we've already visited ande
so that leaves us with ap so the next verse
vertex required visit is going to be /f shot stack
visit mark dismiss it
now to talk stack we have asked
if we take a look at AHF we've already been to be
but we haven't been to either CRT so
we can visit the lowest the stuff that click n
which is see push not stack visit it
markets visited see is on top
stack so take a look at all the vertices connected to see
sees connect af which we've already seen
but H we haven't visited yet
we push it we visit market is visited
FH there's no place to go
except back to see but we've already been there so we're gonna pop each other
stack
which they expect to see now there's no place new to go from C
so a pocket of the stack which text back to apt
now from after is
a connection to a vertex we haven't visited yet NXT
sleek pushed me onto the stack we can visit
and meet mark D as visited
the *** this in a place you to go
sock puppet of the stack which takes us back to F
but from F we've already been ever we can't sort like pop it off the stack
expect be from be there's no place to go
sock puppet of the stack which returned to stay
and since we've seen everything that's connected to a he gets popped up stacks
well
now our stack is empty which means that are too personal is complete
for next example
we're gonna take a look at another craft soccer them in this case
a breadth-first traversal not major difference between a
breadth first burst Limit depth-first traversal is the use a different
supporting data structure
in this case acute
circuit
vertices we still have to visit using a queue just like last time we're gonna
start out for Tex
K so we're going to visit a
and market has visited except the main difference
is in this case we're going to say that we're currently working
on vertex a all the vertices connected
AL medically the one that comes first
is be so we're going to visit p
market is visited
and at it to the Q
pornoxo move to be we're still at vertex a
sir gonna continue want from vertex a and take a look at the next for Texas
connect to it
alphabetically which is d market has visited
and edit
cue again
we're not moving to TN whistle it protects a case we're going to take a
look at any other vertices connected to a
that we haven't yet seen such as chi
market has visited and
and QG now we've already seen all the vertices connected to a
so there's nothing more to do with a so we can
in a shop with a and see where to go next
we're gonna turn to our queue and we're going to pick
the vertex on the head of the queue which is P
we're gonna de Q Bert XP
and make that
the vertex are currently exploring from there
we're going to again take a look at all the connected vertices
at least the ones we haven't already seen yet we've been to a
but we haven't been to hear so
again going enough political order we're going to visit the vertex
E market has visited
an
2q or still at be
so take a look at the next and visited her text me which is half
visit market
do it no place to go from
be so we're done with be next up on the Q
is d so we're going to
DQ'd and
and explore all the vertices connected to D well
we've been to both a and app so we have no place new to go from D
we're done with T to go back to Q
which Texas 2g after G
there's also no place new to go we've been to both a nd
soared energy and now we can go back to queue
which takes us to eat when we take a look at the
this new place new to cost me either
so we're done with the and we come back to you to decide where to go next
well after an expert exner cue
does have a connected for text we haven't seen yet
see so we visit see
market is visited
and at it
cue nowhere else to go
map so we're done with that now back to the Q decide where to go next
tells us to kill to see so we got to see
and we take a look at all the courtesies connect
see leap into F already
haven't been to %eh so it is H it is visited
at cue and
and we're done with C I go back to the Q
we see H his at the head of the queue dq it
take a look at everything connects
H nothing new there so we're done with %eh
and when we go back to Kiwi see it's empty which tells us that this
commercial is complete