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

Graph Search

One of the most common graph operations is searching for a particular vertex.

When dealing with graphs, the term search can have several connotations. In the simplest sense, to search a graph means to find a particular vertex somewhere within the graph. This would be similar to searching for a value within an array or a key-value pair inside a hash table.

However, when applied to graphs, the term search usually has a more specific connotation, and that is: if we have access to one vertex in the graph, we must find another particular vertex that is somehow connected to this vertex.

For example, take a look at this example social network:

Let’s say we currently have access to Alice’s vertex. If we said that we’ll search for Irena, ...