## Path Determination for Unidirectional Graph Searching

June 29th, 2010 at 15:42Graph search algorithms are classic coding and thinking exercises for computer science students. Two particular algorithms most students will experience are Breadth First Search (BFS) and Depth First Search (DFS). The pervasiveness of these algorithms in education will often lead to them being used as a gauge of a programmers knowledge and analytical abilities.

Once a programmer finishes their schooling, it’s important for them to constantly be updating their skill base to stay relevant in an ever changing industry. In addition to staying up to date as new technologies emerge, it’s also important to stay sharp on their existing skills. When a pancake told me that a graph should be implement as bidirectional to determine the path once a target is found using a graph search algorithm, I couldn’t confidently argue that it could be done using a unidirectional graph. I thought this would be a great opportunity for me to brush on on my BFS and DFS by actually implementing them.

Before continuing, Wikipedia has great articles for those unfamiliar with BFS, DFS, or general graph theory.

I won’t go into detail on my particular implementation of the actual search algorithms, which were done in Java. The main focus of this exercise was to show that you could retrieve the complete path using BFS or DFS on a unidirectional graph.

Both search algorithms have to protect against traversing cycles. Doing so prevents the algorithm from literally running in circles. To protect against cycles the algorithms keep a list of nodes they’ve already visited. This list can also be used to compute the path for unidirectional graphs once the target is found.

Here is my implementation. The list of nodes passed into the function has the start node at the beginning, followed by every node checked before the target was found, and lastly the target. I’ll let the code and comments speak for the functionality.

Hopefully this can be as educational for readers as it has for me. Due to the pervasive nature of this problem as a test, I won’t be publishing any source beyond what is shown, and even then I’m keeping it as an image so it can’t be easily copy/pasted. My apologies for anyone looking to copy my code for honest purposes.

**Jeff**, in Coding

June 30th, 2010 at 11:06 am

Bonus points for figuring out the computational complexity of your algorithm…

October 2nd, 2013 at 7:41 pm

Now that I’m brushing up on my big O notation, I’m gonna take a shot at this.

If n is the number of elements in the tree, starting from the inner loop that checks all the children of a specific node, assuming worse case scenario that the entire tree is under that one parent, the inner loop is n-1 which is O(n).

Assuming worse case scenario that the entire tree is in the pathQueue, the outer loop, which starts one before the last element, is again n-1, or O(n).

Putting it all together, O(n) * O(n) = O(n^2)