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.