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 ...
Get A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
