Description
- Provide an implementation in C++ of the DFS, and BFS algorithms. You are given a class declaration in the header file graph.h, which you should implement in graph.cpp. You should strictly implement the method signatures provided in the header file. As you will see in the skeleton code provided, an Adjacency Matrix representation is used for the graphs. We assume that nodes are represented with unique IDs that are integer values starting from 0 to match the indexes in the Adjacency Matrix. You are also given a test case for each algorithm in main.cpp. You can implement additional test cases for testing purposes, but you don’t have to submit a modified main.cpp. Your submission should run successfully using the main method provided.
Regarding the output of your code, you don’t need to store the distance attribute for BFS, or the discovery and finishing times for DFS. For both algorithms the only required output is the following: whenever you visit a node of the graph, print the node ID using a cout instruction to show the sequence that the nodes are visited.
In order to modify your implementation compared to the pseudocode provided in the lecture notes, you are asked to use a C++ set to keep track of the visited nodes instead of coloring the nodes. This is a good opportunity to familiarize yourselves with C++ sets if you haven’t used it before.
Remarks:
- You are not allowed to use code from online resources. Your submission will be tested against that, and will receive a 0, and a report to the Graduate Academic Integrity Board if it is detected.
- You can use containers from the C++ Std library.
- A Makefile is provided to build the code in the Virtual Box.
- Your code has to compile, and will be graded on the Virtual Box.
- The programming, and testing will take some time. Start early.
- Your report has to be typed, and submitted in a pdf file.
- Feel free to use the provided source code for your implementation. You have to document your code.
