BFS via examples

Expected background

These notes assume that you are familiar with the following:

• Graphs and their representation. In particular,
  • Notion of connectivity of nodes and connected components of graphs
  • Adjacency list representation of graphs
  • Notation:
    • $G=(V,E)$
    • $n=|V|$ and $m=|E|$
    • $CC(s)$ denotes the connected component of $s$
• Trees and their basic properties

The problem

In these notes we will solve the following problem:

Next we go through a sequence of examples to build towards an algorithm that will solve the above problem. We encourage you to work on each question first and then toggle for the answer.

But if you must: Toggle all answers

A warmup

Toggle for answer

                            R[s]=T and R[u]=F for every u != s
                        

For the rest of the notes, assume $E\neq \emptyset$.

Example 1

Let us now consider the following somewhat more non-trivial example of $G$:

In this case, by inspection the solution is simple: we should have R[s]=R[a]=R[b]=R[c]=R[d]=T (and every other entry should be false).

Now, let us make things bit more general. Say the connected component of $s$ is a “star” (or a tree of depth 1) graph, like so:

Toggle for answer

                            R[s]=T and R[u]=F for every u != s
                    
                            For every u in Adj[s]
                                Set R[u]=T
                        

But is the above enough? As you might imagine not quite so.

Example 2

Consider the following example:

In the above example, our current algorithm will output all the green and blue nodes as the connected component, which is clearly missing the orange nodes. So the idea is that not only do we have to output all neighbors of $s$ but we also have to output all neighbors of neighbors of $s$.

Before we proceed, let us re-state our existing algorithm:

				R[s] = T and R[u]=F for every u != s
				L0 = {s}
				L1 = null

				For every u in L0 # So u will trivially be s
					For every w in Adj[u]
						Add w to L1
				For every w in L1
					R[w] = T
			

Now let us try to modify the algorithm above to work for the following more general case (basically a tree of depth 2):

Toggle for answer

				R[s] = T and R[u] = F for every u != s
				L0={s} # L is for “layer”
                                L1 = null
                                L2 = null

				For every u in L0
					For every w in Adj[u]
						Add w to L1

				For every w in L_1
					R[w] = T

				For every u in L1 # Repeat for L1 what we have done for L0
					For every  w in Adj[u]
						Add w to L2

				For every w in L_2
					R[w] = T
			

Spot the inefficiencies

The subtle one first

We start with something that is slightly subtle (but does not affect the correct of even the asymptotic runtime of the algorithm).

Toggle for answer

				R[s] = T and R[u] = F for every u != s
				i=0
				L[i]={s}

				While i<2:
					L[i+1]= null
					For every u in L[i] 
						For every w in Adj[u]
							Add w to L[i+1]
							R[w]=T # There is no need to have a separate loop to do this assignment
					i++
				

Example 3

Now we consider the case of a general tree of depth $d$:

Of course our current algorithm will fail on the above (since it will not add anything beyond the orange level). However, it should now be easy to modify the current algorithm if you know the depth upfront:

Toggle for answer

                                R[s] = T and R[u] = F for every u != s
                                i=0
                                L[i]={s}

                                While i<d:
                                        L[i+1]= null
                                        For every u in L[i]
                                                For every w in Adj[u]
                                                        Add w to L[i+1]
                                                        R[w]=T # There is no need to have a separate loop to do this assignment
                                        i++
                                

Example 4

Now let us consider an example where $G$ is a tree plus one more edge:

So the first thing to note that there is no notion of level since our $G$ is no longer a tree. So before we think about how to modify the existing algorithm to handle the above case, think about how one would change condition in step 6 so that we can terminate properly. In particular, let us start with the following:

Toggle for answer

This naturally brings us to the following question:

The obvious solution

Once you are done handling the pink nodes in the tree graph, you do not expect to get any nodes in the new layer you would aim to construct from L_d. In particular, the following seems a good fix:

                                R[s] = T and R[u] = F for every u != s
                                i=0
                                L[i]={s}

                                While L[i] != null:
                                        L[i+1]= null
                                        For every u in L[i] 
                                                For every w in Adj[u]
                                                        Add w to L[i+1]
                                                        R[w]=T # There is no need to have a separate loop to do this assignment
                                        i++
                                

Toggle for answer

                                R[s] = T and R[u] = F for every u != s
                                i=0
                                L[i]={s}

                                While L[i] != null:
                                        L[i+1]= null
                                        For every u in L[i]
                                                For every w in Adj[u]
                                                    If R[w] == F
                                                        Add w to L[i+1]
                                                        R[w]=T 
                                        i++
                                

Coming back to our example of tree plus an edge

Toggle for answer

Answer 10

It works! Let’s look back at how the algorithm will run on this specific graph. When the algorithm is creating L[2] from L[1] (i.e. the blue nodes), then L[2] in addition to having the orange node will also have the green node in it. So effectively “pull” up the subtree rooted at the green node. The situation would look like this

Question 11

So why is Algorithm 5 correct?

Toggle for answer

Answer 11

Basically we do not care in which order the nodes are put in: i.e. whether we discovered the green node directly from the blue node or the orange node. If we choose the latter then we would have the following situation

The general case

We are now ready to bite the bullet and handle the most general case. E.g. our $G$ might look something like this:

Toggle for answer