Java代写|CIT 594 Module 8 Programming Assignment Graphs

本次美国Java代写是一个模块 8 编程作业图的assignment

Learning Objectives

In completing this assignment, you will:

  • Become more familiar with the “adjacency set” representation of a graph
  • Apply what you have learned about how to traverse a graph
  • Demonstrate that you can use graphs to solve common problems in computer science

Getting Started

Begin by downloading the starter code zip file for this assignment.

The zip file includes the following files inside the src folder:

  • Graph.java, UndirectedGraph.java, and DirectedGraph.java: the implementations for
    the adjacency set representation of a graph (undirected and directed) along with breadth-first
    search and depth-first search implementations that we saw in the lessons
  • GraphUtils.java: contains the unimplemented methods for the code that you will write in
    this assignment
  • GraphBuilder.java: includes static methods for generating directed and undirected graphs
    from an input file

Outside the src folder, you will find student_graph_test.txt, which is a sample graph file that
you can use as input for testing the methods that you will implement in this assignment. You are
encouraged to create your own test input files; see the FAQ for how to do this. The sample file is
the same as what is used in the visible test cases on Codio. The hidden test cases contain hidden
graph input files.

Activity

Implement the following specifications in the GraphUtils.java file.

Your implementation must work for both directed and undirected graphs. Do not change the
signature of any of the three methods, and do not create any additional .java files for your solution;
if you need additional classes or methods, you must define them in GraphUtils.java. You may use
portions of the provided code to help write your solution and helper methods. Last, be sure that all
code is in the default package, i.e. there is no “package” declaration at the top of the source code.

You may not mutate any graph or list that is given to you as input. The test suite will throw
an UnsupportedOperationException if you attempt to update, add, or remove elements from any
graph or list.

static int minDistance(Graph graph, String src, String dest)

Given a graph, this method returns the smallest number of edges from the src node to the dest
node, or −1 for any invalid input. Invalid inputs are defined as: any of graph, src, or dest is null;
no path exists from src to dest; any of src or dest do not exist in graph.

static Set<String> nodesWithinDistance(Graph graph, String src, int distance)

Given a graph, a src node contained in graph, and a distance of at least 1, this method returns the
set of all nodes, excluding src, for which the smallest number of edges from src to each node is less
than or equal to distance; null is returned if there is any invalid input. Invalid inputs are defined
as: any of graph or src is null; src is not in graph; distance is less than 1.
static boolean isHamiltonianCycle(Graph g, List<String> values)

This method returns true only if:

  • The graph g is non-null
  • g has at least three nodes
  • values is non-null
  • values represents a Hamiltonian cycle through g
  • values is given as a sequence of vertices ending in the starting node of the cycle

Otherwise, return false. See the definitions below, as well as the FAQ for any further clarifications
if needed.