CS590 homework 5 – Graphs exploration (BFS, DFS)

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

 code and the make a report on the output. instructions are available in the file. and the code should be in the c++ programming language

 

 

CS590 homework 5 – Graphs exploration (BFS, DFS)

The due date for this assignment is Wednesday, December 8th, at 11.59pm. This assignment is worth 10% of your final grade. Any sign of collaboration will result in a 0 and being reported to the Graduate Academic Integrity Board. Late submission policy described in the syllabus will be applied.

 

(100 points)

 

 

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

 

(60 points)

 

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.

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of