A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

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 ...