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, it would mean that we’re trying to find our way from Alice to Irena.

Interestingly, you can see that there are two different paths we can take to get from Alice to Irena.

The shorter path is obvious:

We can get from Alice to Irena in this sequence:

Alice -> Derek -> Gina -> Irena

However, we can take a slightly longer path to get to Irena as well:

This is the longer path:

Alice -> Elaine -> Derek -> Gina -> Irena

The term path is an official graph term, and it means the specific sequence of edges to get from one vertex to another.

Now, searching a graph (which you now know means getting from one vertex to another) can be useful for a variety of use cases.

Perhaps the most obvious application for graph search is searching for a particular vertex within a connected graph. When this is the case, search can be used to find any vertex within the entire graph even if we have access to just one random vertex.

Another use for graph search is to discover whether two vertices are connected. For example, we may want to know whether Alice and Irena are somehow connected to each other in this network. A search would give us the answer.

Search can also be used even if we aren’t looking for one particular vertex; that is, we can use graph search to merely traverse a graph, which can be useful if we want to perform an operation on every vertex in the graph. You’ll see shortly how this works.