So in this lecture we're going to drill down into our first specific, search
strategy for graphs and also explore some applications. Namely, breadth first
search. So let me remind you the intuition and applications of breath first search.
The plan is to systematically explore the nodes of this graph beginning
with the given starting vertex in layers. So let's think about the following example
graph. Where S is the starting point for our breadth first search. So to start
vertex S will constitute the first layer. So we'll call that L zero. And then
the neighbors of S are going to be the first layer. And so those are the vertices
that we explore just after S. So those are L one. Now the second layer is going
to be the vertices that are neighboring vertices of L one but are not
themselves in L one or for that matter L zero. So that's going to be
C and D. That's going to be the second layer. Now you'll notice for example S is
itself a neighbor of these nodes in layer one, but we've already counted that in a
previous layer so we don't count S toward L two. And then finally the
neighbors of L two, which are not already put in some layer is E. That will
be layer three. Again notice C and D are neighbors of each other but, they've
already been classified in layer two. So, that's where they belong, not in layer
three. So that's the high level picture of breadth first search you should have. We'll
talk about how to actually precisely implement it on the next slide.
Again just a couple other things that you can do with breadth first search which we'll
explore in this video is computing shortest paths. So it turns out shortest path
distances correspond precisely to these layers. So, for example if you had that as
S, you had that as the Kevin Bacon node in the movie graph, then Jon Hamm would pop
up in the second layer from the breadth first search from Kevin Bacon. I'm also
going to show you how to compute the connected components of an undirected
graph. That is to compute its pieces. We'll do that in linear time. And for this
entire sequence of videos on graph primitives, we will be satisfied with
nothing less than the holy grail of linear time. And again, remember in a graph you
have two different size parameters, the number of edges M and the number of nodes
N. For these videos I'm not going to assume any relationship between M and N.
Either one could be bigger. So linear time's gonna mean O of M plus N. So let's
talk about how you'd actually implement breadth first search in linear time. So
the sub routine is given as input both the graph G. I'm gonna explain this as if
it's undirected, but this entire procedure will work in exactly the same way for a
directed graph. Again, obviously in an undirected graph you can traverse an edge
in either direction. For a directed graph, you have to be careful only to traverse
arcs in the intended direction from the tail to the head, that is traverse them
forward. So as we discussed when we talked about just generic strategies for graph
search, we don't want to explore anything twice, that would certainly be
inefficient. So we're going to keep a boolean at each node, marking whether
we've already explored it or not. And by default, I'm just, we're just going to
assume that nodes are unexplored. They're only explored if we explicitly mark them
as such. So we're going to initialize the search with the starting vertex S. So we
mark S as explored and then we're gonna put that in what I was previously calling
conquered territory the nodes we have already started to explore. So to get
linear time we are gonna have to manage those in a slightly non naive but, but
pretty straightforward way namely via a queue, which is a first in first out data
structure that I assume you have seen. If you have never seen a queue before, please
look it up in a programming textbook or on the web. Basically a queue is just
something where you can add stuff to the back in constant time and you can take
stuff from the front in constant time. You can implement these, for example, using a
doubly linked list. Now recall that in the general systematic approach to
graph search, the trick was to, in each iteration of some while loop, to add one
new vertex to the conquered territory. To identify one unexplored node that is now
going to be explored. So that while loop's gonna translate into one in which we just check
if the queue is non-empty. So we're assuming that the queue data structure
supports that query in constant time which is easy to implement. And if the queue is
not empty we remove a node from it. And because it's a queue, removing nodes from
the front is what you can do in constant time. So call the node that you get out of
the queue V. So, now we're going to look at V's neighbors, vertices with which it
shares edges, and we're gonna see if any of them have not already been explored.
So, if W's something we haven't seen before, that's unexplored, that means it's
in the unconquered territory, which is great. So, we have a new victim. We can
mark W as explored. We can put it in our queue and we've advanced the frontier and
now we have one more explored node than we did previously. And again, a queue by
construction, it supports adding constant time additions at the end of the queue, so
it's where we put W. So, let's see how this code actually executes in this same graph
that we were looking at in the previous slide. And what I'm gonna do is I'm gonna
number the nodes in the order in which they are explored. So, obviously
the first node to get explored is S. That's where the queue starts. So now, when we
follow the code, what happens? Well in the first iteration of the while loop we ask
is the queue empty? No it's not, because S is in it. So we remove in this case the only
node of the queue. It's S. And then we iterate over the edges incident to S. Now there are two
of them. There's the edge between S and A and there's the edge between S and B. And
again this is still a little under specified. In the sense that the algorithm
doesn't tell us which of those two edges we should look at. Turns out it doesn't
matter. Each of those is a valid execution of breadth first search. But
for concreteness, let's suppose that of the two possible edges, we look at the
edge S comma A. So, then we ask, has A already been explored? No, it hasn't. This
is the first time we've seen it, so we say, oh goody. This is sort of new grist
for the mill. So, we can add A to the queue at the end and we mark W as, sorry
mark A as explored. So, A is gonna be the second vertex that we mark. So, after
marking A as explored and adding it to the queue, so now we go back to the for loop,
and so now we move on to the second edge. It's into S, that's the edge between S and
B. So, we ask, have we already explored B? Nope, this is the first time we've seen
it. So, now we have the same thing with B. So, B gets marked as explored and gets
added to the queue at the end. So the queue at this juncture has first a record
for A, cause that was the first one we put in it after we took S out. And then B
follows A in the queue. Again, depending on the execution this could go either way. But
for concreteness, I've done it so that A got added before B. So at this point, this
is what the queue looks like. So now we go back up to the while loop, we say is
the queue empty? Certainly not. There's actually two elements. Now we remove the
first node from queue, in this case, that's the node A that was the one we put in
before the node B. And so now we say, well, let's look at all the edges incident
to A. And in this case A has two two incident edges. It has one that it
shares with S and it has one that it shares with C. And so, if we look at the
edge between A and S, then we'd be asking an if statement. Has S already been
explored? Yes it has, that's where we started. So, there's no reason to do
anything with S. That's already been taken out of the queue. So, in this for
loop for A, there's two iterations. One involves the edge with S, and that one we
completely ignore. But then there's the other edge that A shares with C, and C we
haven't seen yet. So, at that part of the for loop, we say ahah. C is a new thing,
new node we can mark as explored and put in the queue. So, that's gonna be our
number four. So now how has the queue changed. Well, we got rid of A. And
so now B is in the front and we added C at the end. And so now the same thing
happens. We go back to the while loop, the queue is not empty, we take off the first
vertex, in this case that's gonna be B. B has three incident edges, it has one
incident S but that's irrelevant, we've already seen S. It has one incident to C,
that's also irrelevant, that's also irrelevant, because we've already seen C.
True, we just saw it very recently, but we've already seen it. But the edge
between B and D is new, and so that means we can take the node D, mark it as explored
and add it to the queue. So D is going to be the fifth one that we see. And now the
queue has the element C followed by D. So now we go back to the while loop and we take C off
of the queue. It again has four now edges. The one with A is irrelevant, we've already
seen A. The one with B is irrelevant, we've already seen B. The one with D is
irrelevant, we've already seen D. But we haven't seen E yet. So, when we get to the
part of the for loop, or the edge between C and E, we say, aha, E is new. So E will
be the sixth and final vertex to be marked as explored. And that will get added at
the end of the queue. So then in the final two iterations of the while loop
the D is going to be removed, we'll iterate through its three edges, none of
those will be relevant because we've seen the three endpoints. And then we'll go
back to the while loop and we'll get rid of the E. E is irrelevant cause it has two
edges we've already seen the other endpoints. Now we go back to the while loop.
The queue is empty. And we stop. That is breadth-first search. And to see how this
simulates the notion of the layers that we were discussing in the previous slide
notice that the nodes are numbered according to the layer that they're in, so
S was layer zero. And then the two nodes that S caused to get added to the queue, the A
and the B, are number two and three, and the edges of layer three are precisely the
ones, sorry the edges of layer two are precisely the ones that got added to the
queue, while we were processing the nodes from layer one. That is, C and D are
precisely the nodes that got added to the queue while we were processing A and B.
So, this is level zero, level one, and level two. E is the only node that got
added to the queue while we were processing level, layer two. The vertices
C and D. So E will be the third layer. So, in that sense, by using a first in first
out data structure, this queue, we do wind up kinda processing the nodes according to
the layers that we discussed earlier. So, the claim that breadth first search is a
good way to explore a graph, in the sense that it meets the two high level goals
that we delineated in the previous video. First of all it finds everything findable,
and obviously nothing else, and second of all, it does it without redundancy. It
does it without exploring anything twice, which is the key to its linear time
implementation. So a little bit more formally, claim number one. At the end of
the algorithm, the vertices that we've explored are precisely the ones such that
there was a path from S to that vertex. Again this claim is equally valid, whether
you're running BFS in an undirected graph or a directed graph. Of course in an
undirected graph, meaning an undirected path from S to V, whereas a directed graph
in a directed path from S to V. That means a path where every arc in the path gets
traversed in the forward direction. So, why is this true? Well, this is true, we
basically proved this more generally for any graph search strategy of a certain
form of which breadth first search is one. If it's hard for you to see the right way
to interpret breadth-first search as a special case of our generic search
algorithm, you can also just look at our proof for the generic search algorithm and
copy it down for breadth-first search. So it's clear that you're only gonna,
again, the forward direction of this claim is clear. If you actually
find something, if something's marked as explored, it's only because you found a
sequence of edges that led you there. So the only way you mark something as
explored is if there's a path from S to V. Conversely, to prove that anything with an
S to V, for with a path from V will be found, you can proceed by contradiction:
you can look at the part of the path from S to V that, that BFS does successfully
explore, and then you gotta ask, why didn't it go one more hop? It never
would've terminated before reaching all the way to V. So, you can also just copy
that same proof that we had for the generic search strategy in the previous
video. Okay? So, again, the upshot. Breadth first search finds everything
you'd wanna find. Okay? So, it only traverses paths, so you're not gonna find
anything where there isn't a path to it. But it never misses out. Okay? Anything
where there's a path, BFS, guaranteed to find it. No problem. Claim number two is
that the running time is exactly what we want and I am gonna state it in a form
that will be useful later when we talk about connected components. So the running
time of the main while loop, ignoring any kind of pre processing or initialization is
proportional to what I am gonna call NS and MS which is the number of nodes that
can be reached from S and number of edges that can be reached from S. And the reason
for this claim it just becomes clear if you inspect the code which we'll do in a
second. So let's return to the code and just tally up all the work that gets done.
So I'm gonna ignore this initialization. I'm just gonna focus on the main while
loop. So we can summarize the total work done in this while loop as follows. First
we just think about the vertices so in this search we're only gonna deal, ever
deal with the vertices that are findable from S, so that's NS. And what do we do
for the given node, well we insert it into the queue and we delete it from the
queue. Alright? So we're never gonna deal with a single node more than once. So
that's constant time overhead per vertex that we ever see, so that's the proportion
of the NS part. Now, a given edge, we might look at it twice. So, for an edge V
W, we might consider it once when we first look at the vertex V, and we might
consider it again when we look at the vertex W. Each time we look at an edge we
do constant work. So that means we're only gonna do constant work per edge. Okay. So
we look at each vertex at most once. We look at each edge findable from S at most
twice. We do constant time, constant work when we look at something. So the overall
running time is going to be proportional to the number of vertices findable from S
plus the number of edges findable from S. So, that's really cool. We have a linear
time of implementation of a really nice graph search strategy. Moreover we just need
very basic data structures, a queue, to make it run fast with small constants. But
it gets even better. We can use breadth first search as a work horse for some
interesting applications. So, that's what we'll talk about in the rest of this video.