So, what's the problem? Well, so I did say most of
this stuff about graph search it really
doesn't matter undirected or directed.
It's pretty much cosmetic changes, but the
big exception is when you're computing
connectivity. When you're computing the
pieces of the graph. So, right now I'm
only gonna talk about undirected graphs.
In the directed case, we can again get a
very efficient algorithms for it, but it's
quite a bit harder work. So, that's gonna
be covered in detail in a separate video.
So, for now focus just on a undirected
graph, G. And we're certainly not going to
assume that G is connected. Indeed part of
the point here is to figure out whether or
not it's connected, i.e. in one
piece. So, maybe the graph looks like
this. So, for example maybe the graph has
ten vertices and looks like this, on the
right. And intuitively, especially given
that I've drawn it in such a clean way,
it's clear that this graph has three
pieces, and those are the things that we
wanna call the connected components. But
we do want a somewhat more formal
definition. Something which is actually
you know, in math, that we can say is true
of false about a given graph. And roughly
we define the connected components of an
undirected graph as the maximal regions
that are connected. In the sense you can
get from any vertex in the region from any
other vertex in the region using a path.
So maximal connected regions in that
sense. Now the slick way to do this is
using an equivalence relation. And I'm
gonna this here in part because it's
really the right way to think about the
directed graph case, which we'll talk
about in some detail later. So for undirected
graphs. So this isn't super important but
let me go ahead and state the formal
definition just for completeness about
what is a connected component. What do I
mean by a maximal region that's mutually
connected. So a good formal definition is
as the equivalence classes of the relation
on vertices where which we define by U being
related to V if and only if there's a path
between U and V in the graph G. So
I'll leave it for you to do the simple
check that the squiggle is indeed an
equivalence relation. I'm gonna remind you
what equivalence relations are. This is
something you generally learn in your
first class on proofs or your first class
on discrete math. So it's just something
which may or may not be true about pairs
of objects. And to be an equivalence
relation, you have to satisfy three
properties. So, first you have to be
reflexive, meaning A, everything has to be
related to itself, and indeed, in a graph,
there is a path from any node to itself,
namely the empty path. So, also
equivalence relations have to be
symmetric, meaning if U and V are
related then V and U are related. Because
this is an undirected graph, it's clear
that this is symmetric. If there's a path
from U to V in the graph, there's also a
path from V to U, so no problem there.
Finally equivalence class has got to be
transitive. So that means if U and V are
related and so are V and W, then so are U
and W. That is if U and V have a path, V
and W have a path, then so does U and W.
And you can prove transitivity just by
pasting the two paths together. And so the
upshot is when you want to say something
like the maximal subset of something where
everything is the same, the right way to
make that mathematical is using
equivalence relations. So over in this
blue graph, we want to say one, three,
five, seven and nine, are sort of all the
same in the sense that they are mutually
connected and so that's exactly what
this relation is making precise. All five
of those nodes are related to each other.
Two and four are related to each other.
Six, eight, and ten all pairs of them are
related to each other. So the equivalence,
so equivalence relations always have
equivalence classes of the maximal mutually
related stuff, and in this graph context
that's exactly this connected component.
That's exactly what you want. So, what I
wanna show you is that you can use breadth
first search wrapped in an outer for loop
over all of the vertices to compute, to
identify, all the connected components of
the graph in time linear in the graph. In
O of N plus M time. Now you might be
wondering, you know, why do you wanna do
that. Well there's a lot of reasons. So,
an obvious one which is relevant for
physical networks is to check if a network
has broken into two pieces. So, certainly
if you're an internet service provider,
you wanna make sure that from any point in your
network you can reach any other point in
the network. And that boils down to just
understanding whether the graph that
represents your network is a connected
graph, that is, if it's in one piece or if
it's not in one piece. So obviously you
can ask this same question about
recreational examples so if you return to
the movie graph, maybe you're wondering,
can you get from every single actor, in
the IMDB database, to Kevin Bacon, or are
there actors for which you cannot reach
Kevin Bacon, via a sequence of edges, the
sequence of movies in which two actors
have both played a role. So that's
something that boils down to a
connectivity computation. If you have
network data and you want to display it,
you want to visualize it and show it to a
group of people so that they can interpret
it. Obviously one thing you wanna do is
you wanna know if there's multiple pieces
and then you want to display the pieces
separately. So let me mention one
probably a little less obvious application of
undirected connectivity, which is it gives
a nice quick and dirty heuristic for doing
clustering, if you have pairwise
information about objects. So let me be a
little, let me be a little more concrete.
Suppose you have a set of objects that you
really care about. So this could be a set
of documents, maybe web pages that you
crawled, something like that. It could
be a set of images, either your own or
drawn from some database, or it could be
for example a set of genomes. Suppose
further that you have a pairwise function.
Okay? Which for each pair of objects tells
you whether they are very much like each
other or very much different. And so let's
suppose that if two objects are very
similar to each other, like they're two web
pages that are almost the same, or they're two
genomes where you can get from one to the
other with a small number of mutations,
then they have a low score. So low numbers
close to zero indicate that the objects
are very similar to each other. High
numbers, let's say they could go up to
even a thousand or something, indicate
that they are very different objects. Two
web pages that have nothing to do with
each other. Two genomes for totally
unrelated parts or two images that seem to
be of completely different people or even
completely different objects. Now here's a
graph you can construct using these
objects and the similarity data that you
have about them. So you can have a graph
where the nodes are the objects. So for
each pixel, for each image, for each
document, whatever, you have a single
node. And then for a given pair of nodes,
you put in an edge if, and only if, the
two objects are very similar. So, for
example, you could put in an edge between
two objects if, and only if, the score is
at most ten. So remember, the more similar
two objects are, the closer their score is
to zero. So you're gonna get an edge
between very similar documents, very
similar genomes, very similar images. Now
in this graph you've constructed, you can
find the connected components. So, each of
these connected components will be a group of
objects, which more or less are all very
similar to each other. So, this will be a
cluster of closely related objects in your
database. And you can imagine a lot of
reasons why, given a large set of
unstructured data, just a bunch of
pictures, a bunch of documents, or
whatever, you might wanna find clusters of
highly related objects. So we'll probably
see more sophisticated heuristics for
clustering in some sequel course. But
already undirected connectivity gives
you a super fast, linear time, quick and dirty heuristic
for identifying clusters of similar
objects given pairwise data about
similarity. So that's some reasons you
might wanna do it. Now let's actually talk
about how to compute the connected
components in linear time using just a
simple for loop and breadth-first search
as its inner work horse. So here's the
code to compute all the connected
components of an undirected graph. So
first we initialize all nodes as being
unexplored. I'm also going to assume that
the nodes have names. Let's say their
names are from one to N. So, these names
could just be the position in the node
array that these nodes occupy. So there's
gonna be an outer for loop, which walks
through the nodes in an arbitrary order,
let's say from one to N. This outer for
loop is to ensure that every single node
of the graph will be inspected for sure at
some point in the algorithm. And again,
one of our maxims is that we should never
do redundant work, so before we start
exploring from some node, we check if
we've already been there. And if we
haven't seen I before, then we invoke the
breadth-first search subroutine we were
talking about previously in the lecture in
the graph G starting from the node I. So
to make sure this is clear, let's just run
this algorithm on this blue graph to the
right. So we start in the outer for loop
and we set I equal to one, and we say have
we explored node number one yet? And of
course not, we haven't explored anything
yet. So the first thing we're gonna do is
we're gonna, we're gonna invoke BFS on
node number one here. So now we start
running the usual breadth first search
subroutine starting from this node one.
And so we explore, you know, layer one
here is gonna be nodes three and five and
so we explore them in some order. For
example, maybe, node number three is what
we explore second and then node number
five is what we explore, third. And then
the second layer in this component is
going to be the nodes seven and nine. So,
we'll explore them in some order as well.
Let's say seven first, followed by nine.
So, after this BFS initiated from node number one
completes of course it will have found
everything that it could possibly find,
namely the five nodes in the same
connected component as node number one. And
of course all of the five of these nodes
will be marked as explored. So, now we
return once that exits. We return to the
other for loop we increment I, we go to I
equals two, where we'll say, oh, have we already
explored node number two? No we have
not. And so now we invoke BFS again from
node number two. So that'll be the sixth
node we explore. There's not much to do
from two. All we can do is go to node
number four. So, that's the seventh node
we explore. That BFS terminates finding
the nodes in this connected component.
Then we go back to the outer for loop. We
increment i to three. We say ah, have we already
seen node number three? Yes we have. We
saw that in the first breadth first
search. So we certainly don't bother to
BFS from this node three. Then we
increment i to four, have we seen four?
Yes we have, in the second call to BFS.
Have we seen node five? Yes we have, in
the first call to BFS. Have we seen node
six? No, we have not. So the final
invocation of breadth-first search begins
from node number six. That's gonna be the
eighth node overall that we see. And then
we're gonna see the nodes eight and ten in
some order. So for example, maybe we first
explore node number eight. That's a N,
that's one of the first layer in this
component, and then node number ten is the
other node of the first layer in this
component. So, in general what's going on,
well, what we know about, what we know
what will happen when we invoke breadth
first search from a given node I, we're
going to discover exactly the nodes in I's
connected component. Right? Anything where
there's a path from I to that node, we'll
find it. That's the BFS guarantee.
That's also the definition of a connected
component. All the other nodes, which have
a path to, to I. Another thing that I hope
is clear from the example, but you know,
just to reiterate it, is every breadth
first search call when you explore a node,
you remember that through the entire for
loop. Right? So when we invoke breadth
first search from node number one, we
explore nodes one, three, five, seven, and
nine, and we keep those marked as explored
for the rest of this, for the rest of this
algorithm. Right? So and that's so that we
don't do redundant work when we get to
later stages of the for loop. So, as far
as what does this algorithm accomplish?
Well, it certainly finds every connected
component. Alright, there is absolutely no
way it can miss a node because this
for loop literally walks through the
nodes, all of them, one at a time. And so
you're not gonna miss a node. Moreover, we
know that, you know, as soon as you f-,
hit a connected component for the first
time, and you do breadth first search from
that node, you're gonna find the whole
thing. That's the breadth first search
guarantee. As far as what's the running
time? Well it's going to be exactly what
we want. It's going to be linear time
which again means proportional to the
number of edges plus the number of
vertices. And again, depending on the
graph, one of these might be bigger than
the other. So why is it O of M plus N?
Well as far as the nodes we have to do
this initialization there where we marked
them all as unexplored so that takes
constant time per node. We have just the
basic overhead of a for loop so that's
constant time per node and then we have
this check. Constant time per node so
that's O of N. And then recall we proved
that within breadth first search you do
amount of work proportional, you do
constant time for each node in that
connected component. Now each of the nodes
of the graph is in exactly one of the
connected components, so you'll do constant
time for each node in the BFS in which
you discover that node. So, that's again O
of N over all of the connected components. And as far as the edges, no, we
don't even bother to look at edges until
we're inside one of these breadth first
search calls. They play no role in the
outer for loop or in the preprocessing,
and remember what we proved about an
invocation of breadth first search. The
running time, you only do constant amount
of work per edge in the connected
component that you're exploring. In the
worst case you look at the edge once from
either end point and each of that triggers
a constant amount of work. So when you
discover a given connected component the
edge work is proportional to the number of edges in
that connected component. Each edge of the graph is
only, is in exactly one of the connected
components. So over this entire for loop
over all of these BFS calls for each edge
of the graph you'll only be responsible
for a constant amount of work to the
algorithm. So summarizing, because
breadth first search from a given
starting node does, works in time
proportional to the size of that
component. Piggy backing on that sub
routine, and looping over all of the nodes
of the graph we find all of the connected 
components, in time proportional to the
number of edges and nodes in the entire
graph.