And let's begin with the idea of
shortest paths. So, again I'll give you
the movie graph. I'll give you Kevin Bacon
as a starting point. What's the fewest
number of hops, the fewest number of edges
on a path that leads to, say, Jon Hamm? So
some notation, I'm going to use DIST of V,
to denote this shortest path distance. So
with respect to a starting node S, the
fewest number of hops or the fewest number
of edges on a path that starts at S, and
goes to V. And again you can define this
in the same way for undirected graphs or
directed graphs. In a directed graph, you
always want to traverse arcs in the
forward direction, in the correct
direction. And to do this we just have to
add a very small amount of extra code to
the BFS code that I showed you earlier.
It's just gonna be a very small constant
overhead, and basically it just keeps
track of what layer each node belongs to,
and the layers are exactly tracking
shortest path distances away from the
starting point S. So what's the
extra code. Well first in the initialization
step, you set your preliminary estimate of
the distance, the number of the shortest
path distance from S to vertex V as well
if V equals S, you know you can get from S
to S on a path of length zero, the empty
path. And if it's any other vertex all
bets are off, you have no idea if there's a
path to V at all. So let's just initially
put plus infinity for all vertices other
than the starting point. This is something
we will of course revise once we actually
discover a path to vertex V. And the only
other extra code you have to add
is, when you're considering, so when you
take a vertex off of the front of the
queue and then you iterate through its
edges and you're considering one of those
edges V, W, so your V would be the vertex
that you just removed from the front of
the queue. And as usual if the other end
of the edge W has already been dealt with
then, you know, you just throw it out.
That would be redundant work to look at it
again. But if this is the first time
you've seen the vertex W. Then, in
addition to what we did previously, in
addition to marking it as explored and
putting it in the queue at the back, we
also compute its distance, and its
distance is just going to be one more than
the distance of the vertex V, responsible
for W's addition to the queue, responsible
for first discovering this vertex W. So,
returning to our running example of
breadth first search, let's see what
happens. So, again, remember the way this
worked is we start out with from the
vertex S, and we set the distance, you
know in our initialization equal to zero.
We don't know what the distance is of
anything else. So, then how did breadth
first search work? So, we, in the initial
step we put S in the queue. We go to the
main while loop, and then the queue's not
empty. We extract S from the queue. We
look at its neighbors. Those neighbors are
A and B. We handle them in some order.
Let's again think of that we first handle
the edge between S and A. So, then what do
we do? We say we haven't seen A yet. So we
mark A as explored. We put A in the queue at
the front, and now we have this extra
step. It's the first time we're seeing A,
so we wanna compute its distance. And we
compute its distance as one more than the
vertex responsible for discovering A. And
so in this case S was the vertex whose
exploration unveiled the existence of the
vertex A to us. S's distance is zero so we set
A's distance to one. And that's tantamount
to being a member of the ith layer. So
what happens in the next iteration of the
while loop. So now the queue contains
Sorry, the next iteration of the for
loop, excuse me. So after we've handled
the edge S comma A, we're still dealing
with S's edges, now we handle the edge S
comma B. We put, it is the first time
we've seen B. We put B at the end of the
queue, we mark it as explored, and then we
also execute this new step. We set B's
distance to one more than the vertex
responsible for discovering it. That would
again be the vertex S. S led to B's
discovery. And so we set B's distance to
be one more than S's distance, also known
as one. And that corresponds to being the
other node in layer one. Now having
handled all of S's adjacent arcs we go
back to the while loop. We ask if the queue is
empty. Certainly not. It takes two
vertices, first A then B. We extract the
first vertex cuz it's FIFO, that would be
the vertex A. Now we look at A's incident
edges. There's S comma A, which we ignore.
There's A comma C. This is the first time
we've seen C. So as before we mark C as
explored. We add C to the end of the queue
and now again we have this additional
line. We set C's distance to be one more
than the vertex responsible for its
discovery. In this case it's A. That first
discovered C. So we're gonna set C's distance to
be one more than A's distance also known
as two. So then having handled A
we move on to the next vertex in the
queue, which in this case is B. Again we
can forget about the edge between S and V.
We've already seen S, we can forget about
the edge between B and C. We've already
seen C but D is now discovered for the
first time via B. It gets more as explored,
it goes to the end of the queue and its
distance is set equal to one more than B's
distances which is two. So, then we deal
with C. Again it has four arcs, four
edges, three of them are irrelevant. The
one to E is not irrelevant, cause this is
the first time we've seen E. So, E's
distance is computed as one more than C,
cause C was the one who first found E, and
so E gets a distance of three, and then
the rest of the algorithm proceeds as
before. And you will notice that the
labelings, the shortest path labels, are
exactly the layers as promised. I hope you
find it very easy to believe at this point
that, that claim is true in general. That
the distance computed by breadth-first
search for an arbitrary vertex V, that's
reachable from S is, that's gonna be equal
to i if and only if V is in the ith
layer as we've been defining it
previously. And what does it really mean
to be in the ith layer? It means
that the shortest path distance between V
and S has i hops, i edges. So I don't
wanna spend time giving a super rigorous
proof of this claim but let me just give
you the gist, the basic idea,
and I encourage you to produce some formal
proof at home if that is something that
interests you. So one way to do it is you can do it
by induction on the layer i. And so what you
want to prove is that all of the nodes that belong to a given layer i do Indeed, breadth
first search does indeed compute the
distance of i for them. So what does it
mean to be a node in layer i? Well, first
of all, you can't have been seen in either
of the, any of the previous layers; you
weren't a member of layer zero through i
minus one. And furthermore, you're a, a
neighbor of somebody who's in layer i
minus one. Right? You're seen for the
first time once all of the layer i minus
one nodes are processed. So the inductive
hypothesis tells you that distances were
correctly computed for everybody from the
lower l, from the lower layers. So in
particular, whoever this node V was from
layer i minus one was responsible for
discovering u, in layer i. It has a distance
computed as i minus one. Yours is assigned
to be one more than its, namely i. So that
pushes through the inductive step
everything in layer i indeed gets the
correct label of a shortest path
distance i away from S. So before we wrap
up with this application, I do wanna
emphasize, it is only breadth first search
that gives us this guarantee of shortest
paths. So, we have a wide family of graph
search strategies, all of which find
everything findable. Breadth-first search is
one of those, but this is a special
additional property that breadth-first search
has: you get shortest path distances from
it. So in particular depth-first search does not in
general compute shortest path distances.
This is really a special property of
breadth-first search. By contrast in this next
application, which is going to be
computing the connected components of
an undirected graph, this is not really
fundamental to breadth first search. For example,
you could use depth first search instead and
that would work just as well.