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
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
- 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.
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
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: email@example.com 微信:itcsdx