Lab: Graphs

Special thanks to Nathan Sprague for creating this lab.

Overview

Your goal in this lab is to implement a graph data structure using an adjacency matrix and then write several algorithms that operate on graphs.

We have provided the Gradescope unit tests for the graph and algorithms.

Starter Code

• Graph.java - CS240 Graph interface.
• ArrayGraph.java - Adjacency-matrix-based implementation of Graph.java. UNFINISHED.
• GraphAlgorithms.java - Utility class providing several graph algorithms. UNFINISHED.
• ArrayGraphTest.java - Unit tests.
• GraphAlgorithmsTest.java - Unit tests.

Instructions

Complete the unfinished methods in ArrayGraph.java and GraphAlgorithms.java. We recommend you complete the methods in the order they are listed below, as some of them depend on others.

Make sure you test your code as you go along. You can run the unit tests in ArrayGraphTest.java and GraphAlgorithmsTest.java to check your progress.

You will need to implement the following methods:

• ArrayGraph.java:
  • addEdge()
  • hasEdge()
  • removeEdge()
• GraphAlgorithms.java:
  • getOutDegreeOfVertex()
  • getInDegreeOfVertex()
  • isConnected()
  • dfs()

Submission

Submit ArrayGraph.java and GraphAlgorithms.java through Gradescope.