Efficient Graph Search

submited by
Style Pass
2021-06-16 22:30:10

Welcome to Drill Bits, a new column about programming that aims to augment your toolbox and help you write better software. Most installments will include both bits and drills: example code and exercises to hone your skills.

As I write these words, much of humanity is under COVID-19 pandemic lockdown; nonessential activity is banned across the globe. Appropriately enough, this pilot episode of Drill Bits borrows from the zeitgeist the principle of eliminating needless work.

Graphs provide a versatile, unified abstraction for an exceptionally wide range of practical systems, from electronic circuits to social networks. Graph search is fundamental to analyzing graphs and the real-world systems they represent. Do standard graph-search algorithms leave room for improvement?

This column drills down on BFS (breadth-first search), which is useful in its own right and as a building block for more sophisticated analyses.9 After a quick refresher on the classic BFS algorithm, shown in figure 1, I'll show how to improve its efficiency with a technique that can similarly improve other graph analyses. BFS can handle directed graphs, but for brevity we will consider only undirected graphs. Until further notice, we'll restrict attention to connected graphs, in which every pair of vertices is joined by some sequence of edges.

Leave a Comment