To perform searches on a graph, as well as to apply many other algorithms, it is necessary to traverse the graph following its edges.
As with trees, there are many possible ways to traverse a graph, depending on the order in which outgoing edges are traversed. In trees, however, it’s always clear where to start the traversal: from the root. By starting from the root, we are always sure that we can traverse a tree and reach all its nodes. In graphs, however, there isn’t a special vertex like a tree’s root, and in general, depending on the vertex chosen the starting point, there might or might not be a sequence of edges that allows us to visit all vertices.
In this section, we will focus on simple directed graphs; no other assumption will be made. We are not restricting ourselves to strongly connected graphs, and in general, we don’t have further domain knowledge to choose the vertex from which we should start the search. Consequently, we can’t guarantee that a single traversal will cover all the vertices in the graph. On the contrary, several “restarts” from different starting points are normally needed to visit all the vertices in a graph: we’ll show this while discussing DFS.
Initially, however, we will focus on a specific use case: considering the starting point as “given” (externally chosen, without the algorithm knowing much about it) and traversing the graph from it. Based on these assumptions, we will discuss the two most common traversal strategies used on graphs.
1. Optimizing delivery routes
It’s time to go back to the problem with which we introduced this chapter: we have a single delivery to perform from a source point, the warehouse or factory where goods are stocked, to a single destination, the customer’s address.
The hypothesis that we handle deliveries one by one is, obviously, already a simplification. In the general case, it would be too expensive, and delivery companies try to gather together orders from the same warehouse to nearby destinations to spread the costs (gas, the employee’s time, and so on) over several orders.
Finding the best route passing through several points, however, is a computationally hard problem; conversely, the best route for the single-source, single-destination case can be found efficiently.
We’ll develop a generic solution for this problem incrementally, across this and the next few sections, starting with a further-simplified scenario and removing those simplifications step by step, while presenting more complex algorithms to solve these cases.
So, to start our discussion, we need to think about our goal: What’s the “best” route? We can assume, for instance, that the best route is the shortest route, but we could also prefer to find the fastest route or the cheapest one, depending on our requirements.
For the moment, let’s assume we want the shortest route. If we simplify the scenario and ignore factors such as traffic, road conditions, and speed limits, then we can hypothesize that the shorter the distance, the faster we can travel it.
But even this simplified scenario can be made simpler. Figure 14.9, for instance, shows a portion of a city where roads form a regular grid. This is a common situation in many cities in the United States, while elsewhere in the world it’s not necessarily as common. In Europe, many city centers have a plan originally designed during the Middle Age or even earlier, and roads are far less regular.
Figure 14.9 An example map: a portion of San Francisco’s downtown, where blocks form a regular grid
For the moment we can imagine restricting to this ideal situation, but why do that? Well, because it makes our job easier. If all blocks are the same, and can be approximated with squares (or rectangles whose sides’ proportions are close to squares’), then we don’t have to worry about real distances; we can just count the number of blocks traveled to compute the length of a route. The problem would be trivial to solve . . . if it wasn’t for one-way streets! Once we have a minimum viable solution working for this simplified scenario, we can think about developing it to cover more life-like situations.
Figure 14.10 shows the graph that can be built over the map shown in figure 14.9, where we added a vertex at each road intersection, and an edge going from vertex v to vertex u means that from the intersection modeled with v to the one modeled with u, there is a road that can be traveled in that direction (and not necessarily in the opposite direction, from u to v).
If all roads could be traveled in both directions, we would just go west on Market from the warehouse until we crossed 10th St., and then south on 10th down to our destination.
Given the road signs in figure 14.9, however, this is not possible, and we need to take detours. In the next sub-section, we’ll see how.
2. Breadth first search
Listing 14.2 shows the pseudo-code for Breadth First Search (BFS), whose goal, as the name suggests, is to widen the search as much as possible, keeping a perimeter of already visited vertices, and expanding this perimeter to the neighboring vertices. This is shown in figure 14.11, where the graph in figure 14.6 (C) is used to demonstrate the first few steps of this algorithm.
At its core, this algorithm keeps a queue of vertices that will be visited next, the so-called frontier. Vertices are kept in a specific order, so that they are processed from the one closest to the source, to the ones furthest away. The container used to keep track of the vertices in the frontier could be a priority queue, but it would be overkill. Because the metric we use to compute the distance of each vertex from the source is just the number of edges traveled, it turns out that the algorithm naturally discovers vertices in the same order in which they need to be processed. Furthermore, each vertex’s distance can be computed at the time of discovery (the first time each vertex is found while visiting another vertex adjacency list).
So, besides the initialization performed in lines #2-9, the core of the BFS algorithm is the loop at line #10: a vertex v is dequeued and visited. After (optionally) checking whether we reached the search’s goal (if so, we can already return v), we start exploring v’s neighborhood (aka its adjacency list, all its outgoing edges). If we find a vertex u that we hadn’t discovered yet, then we know that its distance from the source will be the distance to get to v plus 1; therefore we can set the distance for u and add u to the tail of the queue.
How can we be sure that u is going to be visited in the right order, that is, after all vertices closer to the source than u and before the ones further away than u?
This can be proved by induction on the distance of vertices. The base of the induction is the initial case. We add the source vertex with a distance 0. This vertex is the only one at distance 0, and so any other vertex added later can’t be closer than (or as close as) the source.
For the inductive step, we assume that our hypothesis is true for all vertices at distance d-1, and we want to prove it for vertex v at distance d; therefore, v is extracted from the queue after all vertices at distance d-1 and before all vertices at distance d+1. From this, it follows that none of the vertices in the queue can have distance d+2, because no vertex at distance d+1 has been visited yet, and we only add vertices to the queue when examining each visited vertex’s adjacency list (so, the distance of a vertex added can only grow by 1 unit with respect to its parent). In turn, this guarantees that u will be visited before any vertex at distance d+2 (or further away) from the source.
For the inductive hypothesis, moreover, we are sure that all vertices at distance d-1 are visited before v, so all vertices at distance d are already in the queue, and hence they will be visited before u.
This property allows us to use a simple queue instead of a priority queue. Not bad, considering that the former has a O(1) worst-case running time for enqueuing and dequeuing its elements (while heaps, for example, need O(log(n)) steps for each operation), allowing us to keep the running time of BFS linear. It’s a worst-case O(|v| + |E|), linear in the largest between the number of vertices and edges. For connected graphs, this can be simplified to O( |E|) .
We mentioned that checking whether search has reached the goal (line #12) and the whole concept of goal vertex are optional. We can also use BFS to just compute the paths and distances from a single source to all the other vertices in the graph. It’s worth noting that as of today there is no known algorithm that can find the shortest path to a single destination more efficiently than BFS. In other words, it’s asymptotically equivalently expensive to compute the single-source-single-destination shortest path, and the single-source-all-destinations shortest paths.
If we were interested in all the distances between all the pairs of vertices, we would have better options than running BFS |V| times (but that’s out of scope here).
3. Reconstructing the path to target
Quite often, besides computing the minimum distance of a certain vertex from a source vertex, we are also interested in discovering the shortest path to that vertex, meaning which edges should be followed, and in which sequence, to get from source to destination.
As shown in the bottom part of figure 14.11, we can obtain a tree considering the “parent” relation between visited and discovered vertices: each vertex u has exactly one parent, the vertex v that was being visited when u was discovered (line #15 in listing 14.2).
This tree contains all the shortest paths from the source vertex to the other vertices, but the output of the BFS algorithm is just a dictionary, so how can we reconstruct these paths from the parents container that is returned?
Listing 14.3 describes the algorithm. It starts from the goal vertex (the last vertex in the path) and reconstructs the path backward at each step, looking for the parent of the current vertex. In simple graphs, since there is only one edge between an ordered pair of vertices, if we know that we moved from vertex v to vertex u, the edge traversed becomes implicit. In multigraphs, we would have to keep track of the actual edge chosen at each step.
The code in listing 14.3 assumes that the parents dictionary is well formed, that the graph is connected, and that there is a path from source to destination. If all of that holds true, there are only two cases where the current vertex can have a null parent: either current is the destination vertex (and in that case, it means it wasn’t reachable from the source), or current is the source vertex.
If parents[destination] != null, in fact, this means that the destination was reached by traversing a path from the source (because of the way BFS works), and it can be proven by induction that there must be a chain of vertices between those two vertices.
Let’s see the algorithm in action on the result of the run shown in figure 14.11. bfs, on that graph, using v1 as source, returned the following values for parents:
[v1 → null, v2 → v3, v3 → v1, v4 → v3, v5 → v3, v6 → v5]
If we start at v5, for instance, we see that parents[v5]== v3, and this means that we need to add v3 to path after v5, and then look at its parent, and so on.
Right before line #9, we have path==[v5, v3, v1], and reversing it, we get the sequence of vertices we were looking for.
4. Depth first search
BFS, as we have seen, uses a clear strategy to traverse a graph. It starts from the closest vertices to a source, and then it propagates in all directions like a wave, in concentric rings: first all the vertices at distance 1, then the next ring, with all the vertices at distance 2, and so on.
This strategy is, as we have seen, quite effective when we have to find the shortest paths from a source to the other vertices in a graph; at the same time, of course, this is not the only possible strategy to traverse a graph.
A different approach, for instance, is to traverse paths “in depth.” It’s like when you are in a maze looking for the exit: you keep going as far away from the source as possible, choosing your direction at each intersection, until you hit a dead end (in graph terms, until you get to a vertex without any untraveled outgoing edges). At that point, you retrace your steps up to the previous bifurcation (the previous vertex with at least an untraveled edge), and choose a different path.
This is the idea behind Depth First Search (DFS), basically the opposite strategy from BFS. This algorithm, described in listing 14.4, can’t be used to find shortest paths, but it has numerous important applications in graph theory, and also in practice.
Figure 14.12 shows an example of DFS traversal on the same graph we used to illustrate BFS and using the same vertex, v^ as a starting point. You can see how the sequence of vertices visited is completely different (and not just because of the way we break ties about which edge to traverse first). The most noticeable detail is, perhaps, that we use a stack instead of a queue to keep track of the next vertices to be visited.
Similarly to BFS, there is no guarantee that a single run of a DFS traversal will visit all vertices in the graph. This is shown in figure 14.13, where instead of starting the traversal from v4, we choose to start from v4. Because the graph has two strongly connected components, and the first one can’t be reached from v4, this unavoidably means that vertices v4 to v3 can’t be visited in this traversal.
To complete the traversal of the graph, we need to start another traversal in one of the remaining vertices, the ones that haven’t been visited before: this is shown in figure 14.14 where the new traversal starts from vertex v3, and avoids the three vertices that hadn’t already been visited in the first run.
To complete the discussion, listing 14.5 shows the code to perform a full DFS traversal of a graph, with restarts.
It’s also possible to pass a callback to method dfs, so that during traversal it can be called on each vertex visited. This can be used for a number of things, from updating the graph (changing vertices’ labels or any other attribute associated), to computing certain arbitrary operations on graphs. All you need to do is pass the callback as an extra argument in listings 14.4 and 14.5 and call the callback as the first thing in listing 14.4.
You can also see that in figures 14.13 and 14.14, we also added the “times” at which vertices are visited and exited (after that their whole adjacency list has been traversed). These values are fundamental for several applications, such as computing the topological sorting (for DAGs: just order vertices by reversed out-time), finding cycles (if a neighbor of the currently visited vertex has an in-time, but not an out-time), or computing connected components.
A final note on performance: as for BFS, this algorithm also has a linear running time O(|V| + |E|) and requires O(|V|) recursive calls (or, equivalently, O(|V|) extra space for the stack).
5. It’s queue vs stack again
When we look at these traversal algorithms, the first thing that should be clear is that their purposes, the contexts in which they are applied, are fundamentally different. BFS is used when the source vertex s is known, and we want to find the shortest path to a certain goal (a specific vertex, all vertices that can be reached from S, or a certain condition).
DFS, however, is mostly used when we need to touch all the vertices, and we don’t care where we start. This algorithm provides great insight into a graph’s structure, and it’s used as a basis for several algorithms, including finding a topological sorting for DAGs, or computing the strongly connected components of a directed graph.
The interesting bit about these algorithms is that their basic version, performing only the traversal, can be rewritten as the same templated algorithm where newly discovered vertices are added to a container from which, at each iteration, we get the next element. For BFS, this container will be a queue and we’ll process vertices in the order they are discovered, while for DFS, it will be a stack (implicit in the recursive version of this algorithm), and the traversal will try to go as far as possible before backtracking and visit all vertex’s neighbors.
6. Best route to deliver a parcel
Now that we have seen how BFS works and how to reconstruct the path from a source to a destination, we can go back to our example and apply BFS to the graph in figure 14.10; the result is shown in figure 14.15.
In this case, the shortest path is pretty obvious—it’s the closest possible path to the “straight-line distance” between the source and the destination, and it’s also the path of minimum Manhattan Distance.
And yet, by just removing the edge between vertices v9 and vE, the result would have to change completely. Try it out as an exercise to work out the solution for this modified case (manually or by writing your own version of BFS and running it).
Source: Rocca Marcello La (2021), Advanced Algorithms and Data Structures, Manning Publications (2021)