**
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.