COMP $3305$: Analysis of Algorithms

Homework #$4-$ Graph Traversal

Graph traversal is a very important algorithm to go over all vertices in a graph. In this homework, you need to implement both the depth$-$first search $($DFS$)$ and the breadth$-$first search $($BFS$)$ algorithms, and output the order of these two traversals from any given graph.

A header file is provided for the graph traversal class: graph.h$.$ You need to download it from the ecourses, and implement all functions defined in the class using $C++$ with a file named Graph.cpp$.$ The testing main.cpp file is provided too. You need to test your algorithms with different graphs to check if these functions are working correctly.

The expected output of your program should be the order of visiting the vertices in the graph as below.

DFS: $a,b,f,e,g,d,c,h,$

BFS: $a,b,e,f,g,d,h,c,$

Your output format needs to be the same as the expected one, or you will not receive any credit for the homework.