Implement Graph Traversals

Read a bit about graph traversal, depth-first search and breadth-first search.

Tasks

When you’ve got an idea of how these work, create a new branch, graph_2 in your data_structures repository. On that branch, add a pair of new methods to your graph implementation.

• g.depth_first_traversal(start_val): Perform a full depth-first traversal of the graph beginning at start_val. Return the full visited path when traversal is complete.
• g.breadth_first_traversal(start_val): Perform a full breadth-first traversal of the graph, beginning at start_val. Return the full visited path when traversal is complete.

In addition, write some demonstration code in an if __name__ == '__main__': block at the end of your file that shows how the two methods of traversal compare to each other when performed on the same graph. See if you can demonstrate the performance characteristics of the two methods over a variety of graph structures.

If your graph is cyclic, each method should avoid getting trapped in loops.

Write tests that prove that your methods work for both cyclic and non-cyclic graphs, etc.

Update your README with information about your implementations, as well as any references or collaborations you used in completing the work. It is a requirement that for each method of this data structure, you include in the README a description of its time complexity in Big-O notation! Expect to lose credit if you don’t have this.

Submitting Your Work

When you are finished with your work and the tests are passing, create a Pull request from graph_2 back to master. Copy the URL and submit it. You may then merge your branch back to master.

As usual, add any, questions, concerns or reflections on this work using the comment feature in Canvas.