In Part 4 of this series on algorithms, I wrote about breadth First Search. I said that next time I would cover Breadth First Search, but I wanted to cover a wrinkle in graphs that requires a slightly different approach- cyclical graphs.

Cyclical Graphcs

A cyclical graph has a child node that references a parent node somewhere in the graph, creating a circular reference and potentially resulting, in our original code, in an infinite loop as the search adds the parent nodes and then the child nodes into the search queue. So how do we deal with this problem? Look at the code below, a modified version of the Breadth First Search algorithm. This code adds a hash table called searched and adds each person to this hash table as the person is checked to see if they are a mango seller, and whether they have already been added to the searched hash table. This gives us the ability to seaarch cyclical graphs without ending up in an infinite loop.

Note that in the case of this code, I am using the person’s name as their unique key across the code. In a real world scenario, this key will be some kind of truly unique key like an email address, a UUID, or a database-generated primary key.