Notes on elementary graph algorithms. Part 1: Breadth-first search
I write all the code in this post in pseudocode.
My first introduction to graphs was when I took honors combinatorics during my senior year at Ohio State. The professor, Dr. Vitaly Bergelson, was a powerhouse when it came to Ramsey Theory. (The fact that his Erdős number is 1 did nothing to help alleviate the intimidation that I felt.)
What is Ramsey Theory? According to Wikipedia, it is the study of the conditions under which order must appear.
Yup. I don’t blame you. Lucky for us, we are going to define and look at graphs in the context of an introductory algorithms class that you might see at an undergraduate level.
Why are graphs important? I mean it is no secret that companies like Google and Facebook love their graph problems when it comes to the algorithmic portion of the interview process. (I had 5 classmates interview for a Facebook internship two weeks ago. All 5 of them got problems that required some knowledge of graph algorithms.)
By now we all know about Google Maps. If you need help finding the fastest route to a specific location, Google Maps does it for you. How? I’d be willing to bet that they use some sort of graph algorithm (Dijkstra?).
Cool. So what do we need to know to write an algorithm like that? First of all, we need to be able to represent a graph in writing. The default way seems to be the following:
Let G = (V, E) be our graph where V is the set of vertices in our graph and E is the set of edges in our graph.
In our diagram above, the vertices V are {u, v, w, x} and the edges E are {(u,v), (v,u), (v,x), (x,v), (x,w), (w,x), (w,u), (u,w)} where (u, v) represents the line connecting the vertices u and v. We call this an undirected graph since the edges have no predefined direction. That is, the edge (u, v) is the same as the edge (v, u). It is legal to travel across that edge in both directions.
G’ here is a directed graph. In this case, the vertices V remain the same as G but the edges E are now given by the set {(v,u), (u,w), (w,x), (x,v)}. It is only legal in a directed graph to travel an edge in the direction that the arrow points.
There are two ways of representing edges of graphs. Depending on the application, you can choose between an adjacency-list representation and an adjacency-matrix representation.
Using the adjacency-list representation, for each vertex v, we can access it’s neighbor vertices by calling Adj[v]. That is, every vertex u ϵ Adj[v] is connected to v by an edge.
Note that the adjacency-list representations for a directed and undirected graph are different even if they have the same vertices. This should be easy to see since the edges in a directed graph are different.
On the other hand, we could represent the edges with an adjacency-matrix.
Adjacency-matrix representation of G
|u v w x
---------
u|0 1 1 0
v|1 0 0 1
w|1 0 0 1
x|0 1 1 0Adjacency-matrix representation of G'
|u v w x
---------
u|0 0 1 0
v|1 0 0 0
w|0 0 0 1
x|0 1 0 0
As can be seen in the two examples above, 0 tells us that no edge exists between the two vertices that denote the (row, column). 1 tells us that an edge does exist.
When do we want to use one over the other? It all depends on the application. Adjacency-lists take at most the same amount of memory as adjacency matrices while adjacency matrices can often be easier to work with.
Now that the definitions are out of the way, lets look at an algorithm. First we take a look at breadth-first search.
In a nutshell, breadth-first search or BFS for short explores all of the nodes closest to the starting node until it has explored all the nodes in the graph. It also has the side effect of giving us a breadth-first tree. That is, BFS creates a tree for us that allows us to see the predecessors of the vertices based on the traversal path of BFS.
Before we talk about the details, lets take a look at the algorithm. Note that the adjacency-list representation is used here.
BFS(G, s)
---------
For all v ϵ G.V
v.color = white
v.d = ∞
v.π = NIL
s.color = gray
s.d = 0
Let Q be an empty queue
Enqueue(Q, s)
While Q is not empty
u = Dequeue(Q)
For all v ϵ Adj[u]
If v.color = white
v.d = u.d + 1
v.π = u
v.color = gray
Enqueue(Q, v)
u.color = blackThis algorithm takes the graph and a starting node s. It starts by setting the color of all the nodes to white, all of the distances d to the given vertex from the starting node equal to infinity (we will see why shortly), and all of the parent pointers to NIL. Then it sets the color of the starting node to gray.
This is important because gray denotes all of the nodes that are on the frontier. In other words, the gray nodes are the nodes that we have just found but have not yet fully explored.
Now it creates a queue named Q (such creativity) and puts s into the queue. From there we enter a WHILE loop that continues until the queue is empty. We start by popping out the first vertex in Q and then we loop through all of the adjacent vertices of u. We only care about adding the vertices that we have not yet discovered into Q so as to not be stuck in an infinite loop.
For each undiscovered vertex adjacent to u, we set its distance d as u.d + 1. This can be shown to be the shortest distance from each of the vertices to the starting vertex s. We also set the parent of these vertices to be u since they were discovered by going through u. Finally we change the color of these vertices to gray and add them to Q. When that is done, u has been fully explored so we change its color to black to tell us that we have fully explored this vertex.
First of all, why did we set all of the starting distances of the vertices to infinity? This is because there may be vertices that BFS can not reach. Since it is impossible to get to those vertices, we say that their distance is infinity.
Notice how the edges of the BFS tree point upwards instead of downwards like normally since the vertices only have pointers to their parent nodes. Assuming you believe that for any vertex v in the BFS tree that v.d is the shortest distance from v to the root node s (proof here) then an interesting property of the BFS tree is that it gives you a shortest path to each node. (Note: “a shortest path” is used because there may be other shortest paths not recorded in the tree.)
What is the asymptotic running time of BFS? It should be clear that the FOR loop contributes |V| since it runs over all of the vertices. What is less clear is the running time of the WHILE loop. In the WHILE loop, we look at all of the adjacent vertices of each vertex in the queue. Each vertex goes into the queue exactly once since we only let vertices that are colored white into the queue. Thus we are scanning the adjacency list of each vertex exactly once. If it is not immediately clear, take a moment to convince yourself that the sum of the total number of the adjacent vertices of each vertex is |E|. Thus the WHILE loop contributes |E| time for a total running time of O(|V| + |E|). In other words, BFS is linear in time to the sum of the total number of vertices and edges that the graph has.
In part 2, we will look at depth-first search and compare it with BFS.
