In this lecture, we are going to start looking at the depth first search graphing algorithm.
This algorithm is going to start at a root node, which we are going to pass into it, and then it's
going to explore as far as possible along each branch before backtracking.
So there's a couple of things that we need.
The first thing we need is a starting vertex.
And the second thing that we need is to make sure that we track the vertex, the vertices that we have
visited.
So make sure to track
visited
vertex so we can create a simple graph and we'll say A, C, B, and then we will connect both to DX.
We'll go from D to e, P to F to G, back to E, and we will take e to H.
H will go to i.
J and k.
K will go to l and L will connect back to it.
So a will be our starting vertex.
So we will go a and then we can either go to C or to B, we will pick B since it shows up first and
the alphabet.
So we will go A to B, D, e from E, we can go to h, l, f and g, so we'll go f to G following the
same criteria as before with what character shows up first.
And since we're g we don't go back to E this way we backtrack.
So we go from G to F, back to E, and from E, we now go to H, which we will now be able to visit
IJ and K,
and from K we can get to L and from L, we see that we're back to E.
Well, we go backtrack now.
So we go L to k, to h, to e, to D, to B to A, and the last vertex we need to visit is C, So now
we finally make it to C, So as you saw, what we did there is we started out at our starting node and
we tried to get as deep into the graph as possible to visit all of our nodes before we branched out
the from A to our other C.
So that was the last node that the last vertex we needed to visit.
If we look at one more, we will say 1 to 3 and then from two we will go for five, three will go to
six and three will go to seven.
So if we start out at one, we will say one, two and then we will visit four and five.
And now that we've hit all the vertices over here, we begin backtracking.
So we'll go from five to 2 to 1 and now we'll go to three.
And now we can hit six and seven.
And what we'll do with this graph is this will be our test graph when we begin when we begin testing
our depth for search implementation and the next lecture.