The Efficiency of Graph Search

Let’s analyze the time complexity of graph search using Big O notation.

In both depth-first search and breadth-first search, we traverse all the vertices in a worst-case scenario. The worst-case scenario may be that we’re intending to do a full-graph traversal, or we may be searching for a vertex that doesn’t exist in the graph. Or, the vertex we’re searching for may just happen to be the last vertex in the graph that we check.

In any case, we touch all vertices in the graph. At first glance, this would seem to be O(N), with N being the number of vertices.

However, in both search algorithms, for each vertex we traverse, we also iterate over all of its adjacent vertices. We may ignore an adjacent vertex if it has already been visited, but we still spend a step checking that vertex to see whether we’ve visited it.

So for each vertex we visit, we also spend steps checking each of the vertex’s adjacent neighbors. This would seem tough to peg down using Big O notation, since each vertex may have a different number of adjacent vertices.

Let’s analyze a simple graph to make this clear:

Here, Vertex A has four neighbors. By contrast, B, C, D, and E each have three neighbors. Let’s count the number of steps it takes to search this graph.

At the very least, we have to visit each of the five vertices. This alone takes five steps.

Then, for each vertex, we iterate over each of its neighbors.

This would add the following steps:

A: 4 steps to iterate over 4 neighbors
B: 3 steps to iterate over 3 neighbors
C: 3 steps to iterate over 3 neighbors
D: 3 steps to iterate over 3 neighbors
E: 3 steps to iterate over 3 neighbors

This yields sixteen iterations.

So we have the visiting of the five vertices, plus sixteen iterations over adjacent neighbors. That’s a total of twenty-one steps.

But here’s another graph with five vertices:

This graph has five vertices, but the count of iterations over adjacent neighbors is as follows:

V: 4 steps to iterate over 4 neighbors
W: 1 step to iterate over 1 neighbor
X: 1 step to iterate over 1 neighbor
Y: 1 step to iterate over 1 neighbor
Z: 1 step to iterate over 1 neighbor

This is a total of eight iterations.

We have the five vertices, plus eight iterations over adjacent neighbors. This is a total of thirteen steps.

So, we have two graphs, each containing five vertices. However, searching one takes twenty-one steps, while searching the other takes thirteen steps.

It emerges that we can’t just count how many vertices are in the graph. Instead, we also need to consider how many adjacent neighbors each vertex has.

To effectively describe the efficiency of graph search, then, we’re going to need to use two variables. We need one to represent the number of vertices in the graph and another to be the total number of adjacent neighbors each vertex has.

O(V + E)

Interestingly enough, Big O notation doesn’t use the variable N to describe either of these things. Instead, it uses the variables V and E.

The V is the easier one. V stands for vertex and represents the number of vertices in the graph.

E, interestingly, stands for edge, meaning the number of edges in the graph.

Now, computer scientists describe the efficiency of graph search as O(V + E). This means that the number of steps is the number of vertices in the graph plus the number of edges in the graph. Let’s see why this is the efficiency of graph search, as it’s not immediately intuitive.

Specifically, if you look at our two earlier examples, you’ll notice that V + E doesn’t seem to be accurate.

In the A-B-C-D-E graph, there are five vertices and eight edges. This would be a total of thirteen steps. However, we noted that there’s actually a total of twenty-one steps.

And in the V-W-X-Y-Z graph, there are five vertices and four edges. O(V + E) says that graph search would have nine steps. But we saw that there are actually thirteen.

The reason for this discrepancy is that while O(V + E) only counts the number of edges once, in reality, graph search touches each edge more than once.

In the V-W-X-Y-Z graph, for example, there are only four edges. However, the edge between V and W is used twice; that is, when V is the current vertex, we find its adjacent neighbor W using that edge. But when W is the current vertex, we find its adjacent vertex V using that same edge.

With this in mind, the most accurate way to describe the efficiency of graph search in the V-W-X-Y-Z graph would be to count the five vertices, plus:

2 * edge between V and W
2 * edge between V and X
2 * edge between V and Y
2 * edge between V and Z

So this comes out to be V + 2E, since we visit all the vertices once (that’s the V) and use each edge twice (that’s the 2E).

In this example, V is 5, as we visit 5 vertices. And since we use each of the four edges twice, 2E comes out to be 8. This is how V + 2E gives us a total of thirteen steps.

The answer, though, to why we just call this O(V + E), is because Big O drops the constants. While in reality the number of steps is V + 2E, we reduce this to O(V + E).

So while O(V + E) is ultimately just an approximation, it’s good enough, as are all expressions of Big O.

What is definitely clear, though, is that increasing the number of edges will increase the number of steps. After all, both the A-B-C-D-E and V-W-X-Y-Z graphs have five vertices, but because the A-B-C-D-E graph has more edges, it takes considerably more steps.

At the end of the day, graph search is O(V + E) in a worst-case scenario, where the vertex we’re searching for is the last one we find (or isn’t present in the graph at all). And this is true for both breadth-first search and depth-first search.

However, we saw earlier that depending on the shape of the graph and the data we’re searching for, our choice of breadth-first versus depth-first can optimize our search where we’d hope to find our vertex at some point before having to traverse the entire graph. The right method of search can help us increase the odds that we won’t end up in a worst-case scenario and that we’ll find the vertex early.

In the next section, you’re going to learn about a specific type of graph that comes with its own set of search methods that can be used to solve some complex but useful problems.