Overview

For this project you will implement the Breadth-First Search, Depth-First Search and Dijkstra's algorithms. You don't need to provide student tests. Your project score will be based on submit server results. Keep in mind that you have one release token for this project (instead of the usual three.)

Objectives

• Practice implementation of graphs.
• Implement Breadth-First Search (BFS) Traversal.
• Implement Depth-First Search (DFS) Traversal.
• Implement Dijkstra's algorithm for shortest path.

Grading

• (100%) Tests
  • (65%) Public Tests
  • (35%) Release Tests

Clarifications

Any clarifications or corrections associated with this project will be available at Clarifications.

Code Distribution

The project's code distribution is available by checking out the project named Graphs. The code distribution provides you with the following:

• A package named graphs → Package where classes associated with the graph implementation will be provided. You need to define a class named Graph. Feel free to add any other classes you understand you need.
• A package named tests → Includes the public tests (PublicTests.java) and a shell for a class (StudentTests.java) for student tests. Notice that you are not required to write student tests for this project; however, we recommend you do so.

Specifications

This project has two main tasks: Implementing a graph representation and implementing the BFS/DFS/Dijkstra's algorithms. The class(es) associated with the graph representation will be provided in the graph package. Feel free to add any classes you understand you need, but make sure they are in the graph package. Notice that you will NOT lose any credit if you decide not to add any classes beyond Graph.

Notice that the Graph class is a generic class whose type parameter represents the elements of the graph we are defining (e.g., Graph<Student>, Graph<Double>, etc.)

The actual methods you need to implement are described at javadoc. You will find in the graphs package an interface named CallBack. A class implementing this interface represents a class that will process a vertex. An example of such a class is PrintCallBack (which you will find in the graph package). This class is used to generate the string that represents the path we follow when performing a breadth-first search or a depth-first search. Each time we reach a vertex, the implementation of DFS and BFS are expected to call the processVertex method to apply whatever processing needs to be done to the vertex. We have implemented PrintCallBack for you (don't modify it).

Requirements

• Do not implement DFS using a recursive approach; implement DFS using an explicit stack.
• Verify that your project passes the submit server tests (Submit Server). Those are the results we use to compute your grade.
• You have one token for this project in the submit server.
• See Student Tests for information regarding the implementation of student tests for this project.
• See Style Guidelines for information regarding style.
• Notice you will receive points for release tests even if you don't release test your project (e.g., you ran out of tokens.)
• Process adjacent vertices in alphabetical order. This means that when processing a node, you will add adjacent elements to a stack or queue by selecting adjacent nodes in alphabetical order. It does not mean the DFS or BFS result will show the nodes in alphabetical order. For example, if node B has nodes E and D as adjacents, we will add D to the stack/queue, followed by E.

Additional Requirements for Students in CMSC 132H (Honors)

No additional requirements.

Submission

Submit your implementation using the Eclipse "Submit Project" option (available by right clicking on the project folder).

Academic Integrity

Please make sure you read the academic integrity section of the syllabus so you understand what is permissible in our programming projects. We want to remind you that we check your project against other students' projects and any case of academic dishonesty will be referred to the Office of Student Conduct.