22C:30, 22C:115 Homework 3 Extra Credit

Due date: Monday, 12/1

This extra credit is worth 50 points (5% or your total grade).

Problem 1
Implement the depth-first-search algorithm and add it to your graph class from Problem 1 in Homework 3. Use the following signature:

void dfs(const string & source,  vector <int> & distances, vector <int> & parent);
The information returned in the vectors distances and parent is similar to what was returned in the bfs function, except that distaces are no longer guaranteed to be shortest-path distances. They are simply distances along whatever paths the depth-first search algorithm decided to take.

As a test of your implementation of dfs, use the ladder program and the input file words.dat from Homework 2 to construct a graph of 5-letter words whose edges connect pairs of words that differ in exactly one letter. Then, by calling dfs appropriately, find a path from the word smart to the word brain. Similarly, use bfs to find a path from smart to the word brain. Report the paths and the respective lengths.

Problem 2
Reimplement the depth-first-search algorithm so that it is non-recursive. Roughly speaking, this can be done by replacing each recursive call to dfs by pushing a new vertex onto the stack. Such a dfs function would contain a while-loop that repeatedly pops the topmost vertex on the stack and looks for an unvisited neighbor of this vertex. Add a function nonRecursiveDfs to the graph class, with the following signature.

void nonRecursiveDfs(const string & source, vector <int> & distances, vector <int> & parent);
Test nonRecursiveDfs like you tested dfs in Problem 1.