PA 9: Application of Graph Traversal
Algorithm and Minimum Spanning Tree
Checkpoint due (+5 extra credit): Monday, midnight
Submit all the part 1 except A*
Due: June 7th, Friday 11:59 PM (midnight)
200 points
Overview
In the first part of the assignment, you will build your own navigation system just like
Google Maps using four different graph traversal algorithms we learn from class: DFS,
BFS, Dijkstra and A*.
In the second part of the assignment, you will implement a data structure Disjoint Set
(Union Find) to help you implement Kruskal’s algorithm and find a Minimum Spanning
Tree for a given Graph.
This assignment is an individual assignment. You may ask Professors/TAs/Tutors
for some guidance and help, but you can’t copy code. You may discuss the assignment
conceptually with your classmates, including bugs that you ran into and how you fixed
them. However, do not look at or copy code. This constitutes an Academic Integrity
Violation.
START EARLY!
Style Requirements
You will be graded on your code’s style:
https://sites.google.com/ucsd.edu/dsc30/resources/style-guide
IntelliJ has a great plugin to check your style automatically. Use it!
There are style considerations beyond indentation and such.
● Choose names for test methods and for variables that are descriptive and useful
when you see them in test output.
● Consider writing helper methods if you repeatedly use the same set of
statements.
● Use Javadoc comments for descriptions of your methods and classes and inline
comments if the logic of your program is not captured by your variable names
and the natural flow of code.
Part 0 - Starter code and PA quiz
Our starter code will be distributed from
https://github.com/ucsd-ets/dsc30sp19-startercode.
Note that this assignment has two parts, and you should create two separate
projects in IntelliJ to implement each part, and submit each part on gradescope
separately.
Please follow the same procedures as before to get your starter code and set up intelliJ.

代写Algorithm留学生作业、代做Minimum Spanning Tree作业、代写Java编程作业
PA quiz (Due Monday)
Fill out this quiz about the PA to make sure you have understood the assignment
thoroughly. You have 5 attempts to complete it.
https://forms.gle/VSBimvhFPpUVG9SK6
Part 1 - Graph Traversal Algorithms
1.1 Intro and Analysis of Graph Traversal Algorithms
Graph traversal algorithms have many useful applications in real life. The four
algorithms we will discuss in class have various applications: DepthFirstSearch,
BreathFirstSearch, Dijkstra and A*. In this part of the assignment, you will use these
four algorithms to build your own navigation system (just like Google Maps).
First, let’s make a guess about which algorithm could potentially be used in Google
Maps to find the shortest path between two locations. For simplicity, assume that
there exists at least one path that connects two given locations. You will probably
cross out DFS first. From what we have learned, DFS will find a path that connects two
vertices, but most likely, this path will not be the shortest. In a large graph like the Earth,
the path generated by DFS will probably spend its whole life on heading towards a
wrong direction.
What about BFS then? We know that with a finite number of vertices in an unweighted
graph, we are guaranteed to find the shortest path connecting two given vertices using
BFS. However, in an actual map, edges between two vertices are typically weighted
rather than unweighted. Roads (edges) that connect different cities (vertices) vary by
length, so we need to assign different weights to each road (edge). Furthermore, traffic
condition could be another component of weight of edges in Google Maps to help you
avoid traffic. Since we know that BFS will most likely fail to find the shortest path in a
weighted graph, we need to continue to the improved version of BFS: Dijkstra.
As we all know, Dijkstra can be used to find the shortest path connecting two given
vertices in a weighted graph. However, once you understand the way Dijkstra explores
the graph, you will realize that Dijkstra is not an efficient algorithm for navigation
system. In a large graph, Dijkstra takes much longer to run for two vertices that are far
away from each other, because Dijkstra will find the shortest path from starting
node to all the other reachable nodes. Although it’s guaranteed that Dijkstra can find
the shortest path, it will search “blindly” for the shortest path: the algorithm will keep
looking for our destination in every possible direction (searching useless parts of the
graph), even if we already know the direction of our destination.
(Dijkstra will explore every location within nearly two thousand miles of Denver before it
locates NYC.)
To solve this problem more efficiently, we will introduce you to an algorithm that “knows”
that we need to first explore east in the example above: A*. Given that we know the
location of our destination, A* can use a simple heuristic function to guide its search.
And with a heuristic function that satisfies certain conditions, A* can still find the shortest
path between two given nodes just like Dijkstra, but much faster. In fact, although
Google Maps is using more complex and efficient algorithms, the idea of the A*
algorithm is its basis.
1.2 Build the Graph
Before starting to implement algorithms for our navigation system, we first need to
consider a well-defined way to represent our “map” using a graph.
As you might know from class, a graph consists of two components: vertices and edges.
Therefore in order to define our “map” as a graph, it is quite natural for us to define
“locations on map” to be the vertices, and “all the roads that connects two locations” to
be the edges.
Since the goal of our navigation system is essentially finding a path that connects two
given locations on the map, we can define our problem as the following:
Given two vertices, find a sequence of edges that connects these two vertices.
Notice that with a finite number of vertices in our graph, if we apply DFS, BFS, Dijkstra
and A* to our graph to find a path (assume there exists at least one path that connects
two given vertices), we might end up with totally different results. We have provided a
wonderful GUI for you to visualize the result path. After you finish implementing each
one of the algorithms, you can use this GUI to check if the path match your expected
behavior of the algorithm. We will give more details about how to use this GUI later.
1.2.1 Vertex and Edge
One simple dataset you will use to build your graph consists of two input files: cityxy.txt
and citypair.txt.
In our graph, the vertices are defined by cityxy.txt, where each line has the name of a
city followed by its x and y coordinates. For example, a line “LasVegas, 160, 350” in
cityxy.txt means we should have a vertex with name “LasVegas”, x-coordinate “160”
and y-coordinate “350” in our graph.
Meanwhile, the edges in our graph are defined by citypair.txt, where each line has a pair
of cities followed by the distance between them, which implies the “weight” of this
undirected edge. For example, a line “LosAngeles, LasVegas, 100” in citypair.txt means
we should have an undirected edge between vertex “LosAngeles” and vertex
“LasVegas” with weight “100”.
In the starter code, we have provided the full Edge class, but only part of the Vertex
class for you. You need to think about what other instance variables and methods
you will need to add to Vertex class after you understand more details about
Graph class. More specifically, you need to decide how to represent all the adjacent
edges of a given vertex, so that it’s possible to traverse from this vertex to its adjacent
vertices. Furthermore, when implementing DFS, BFS, Dijkstra and A*, you need to think
about how you can keep track of some other important information in Vertex class to
make these algorithms work.
1.2.2 Graph
In this class, you will implement all the methods to help you find the path between two
given locations in our navigation system.
We won’t give you detailed instructions in this part, the comments in starter code should
give you an idea of the purpose of each method.
Here are some clarifications on implementation details:
1. We didn’t define any instance variables in this class. You need to think about
which data structure you can use to store all the vertices with edges so that you
can quickly access them.
2. Once you decide which data structure you want to use, check its documentation
to find a method to help you return a Collection of Vertices in getVertices()
3. Let vx
and vy
be x and y coordinates of a given vertex v . The Euclidean
distance between two vertices u, v is given by this formula
4. computeAllEuclideanDistances()will change the user-defined distance of
each edge in the graph to be the Euclidean distance between two locations on
the map.
5. Before you start exploring your graph using different algorithms, you need to
reset some of the instance variables of all the vertices using a helper method
resetAllVertices()
6. CostVertex is a completed helper class for Dijkstra and A* algorithm that you
might find handy. It wraps around a vertex with its “cost”, so that we can use the
“cost” to determine its priority in a priority queue.
7. Think about when you need to stop exploring in our four graph traversal
algorithms, so that you don’t spend time exploring the useless parts of the graph.
8. In these four graph traversal algorithms, the order for selecting children of a
vertex should be the same as the order of the edges of this vertex (Start from the
first edge to the last edge). Since the order of the edges of any vertex is defined
by the user input in citypair.txt, we avoid ambiguity here when exploring the
graph. (Note that you should be using stack to implement DFS and push the
outgoing edges of a given vertex in the same order as mentioned above)
9. Notice that none of the graph traversal algorithms return a path at the end of the
methods. Instead, getpath() is the method we will use to return a list of edges
that connects two given locations (The order of the returned edges should be the
same as the order of edges you get when traversing from start vertex to end
vertex). Later in Display.java, it’s assumed that one of our four graph
traversal algorithms such as BFS() will be called before we call getpath() to
get the results.
10.Once you are done implementing one of the algorithms like DFS (make sure you
finished getPath() and all the methods on the top first), you can proceed to the
next part to use the provided GUI to visualize the results.
Note: feel free to create other methods here (public is OK) if you think the given
methods are not enough for you, you might potentially need some getters here.
1.3 - Fun with GUI
We have provided Display.java, a GUI for visualizing the output of your graph. You
don't need to know how Display.java is implemented (it'd be good if you want to
learn about Java GUI though). Although you do need to write two small parts in
paintGraph(), check TODO in Display.java for more details there.
To run the GUI, you can simply select Run on the top menu of IntelliJ and then click
Run “Display”.
Conceptually, you can imagine Display.java doing the following:
1. Instantiating a new instance of Graph and create vertices / edges from the files
cityxy.txt and citypairs.txt. You can change the file names to play around with
different graphs using the Load / Reset button to load different input files. Notice
that the input files should be placed in “PA9” folder for the GUI to be able to find
those files. You don’t need to handle any command line arguments here, just
type the name of the files and the GUI will do the work for you.
2. Notice that the weight of the edges are defined in the input file citypairs.txt by
default. Because the weight of the edge is not necessarily the distance between
two vertices, you can define the weight of any edges in your own graph.
3. If you only want the weight of your edges to be the true distance between two
vertices, you can simply click Compute All Euclidean Distances, it will call
graph.computeAllEuclideanDistances(). Then the GUI will show all the
updates on the distance variable of Edge objects in the graph. For example, let’s
say the user defined “LosAngeles,111,395”, “LasVegas,160,350” to be two
vertices, and “LosAngeles,LasVegas,100” to be the weight of the edge that
connects them. The default weight of this edge will be 100, but once you click
Compute All Euclidean Distances, our program will calculate the true distance
between LosAngeles and LasVegas: √(111 ? 160) 395 50) 6.5 . And the 2 + ( ? 3
2 ≈ 6
weight of this edge will be updated to 66.5.
4. Clicking on the blue button Draw Dijkstra's Path, it will call graph.Dijkstra()
with the starting city and targeting city names as the parameters. Then it will
highlight the edges returned by graph.getPath() between the starting city
and the targeting city. Same idea for the other 3 buttons.
Graph graph = new Graph();
String startingCity = // get text from selected value in dropdown
String targetingCity = // get text from selected value in other dropdown
graph.Dijkstra(startingCity, targetingCity);
List<Edge> path = graph.getPath(startingCity, targetingCity);
1.4 More Input files and Testing
Right now we only have 2 set of input files: cityxy.txt and citypairs.txt and smallcityxy.txt
and smallcitypairs.txt. Notice that you can customize your input files (need to be in the
right format) and play with the new resulting GUI. You can potentially use your own
input files to create a maze here for your algorithms to solve!
Check this out if you want to further visualize how each algorithm explore the graph
:https://qiao.github.io/PathFinding.js/visual/
Be aware that matching all the outputs below doesn't necessarily mean that you will
pass the autograder test. The test will compare the outputs of your getPath() against
the outputs of our solution code. You need to make sure you put all the edge in the right
sequence (The sequence of edges starting from the start vertex to end vertex).
Test case 1 (input files cityxy.txt and citypairs.txt)
After clicking Compute All Euclidean Distances:
From Los Angeles to Atlanta, using DFS
From Los Angeles to Atlanta, using BFS
From Los Angeles to Atlanta, using Dijkstra / A* ( hvalue: Euclidean distance )
Test case 2 (input files cityxy.txt and citypairs.txt)
After clicking Compute All Euclidean Distances:
From Vancouver to Miami, using DFS
From Vancouver to Miami, using BFS
From Vancouver to Miami, using Dijkstra / A* ( hvalue: Euclidean distance )
Test case 3 (input files smallcityxy.txt and smallcitypairs.txt)
After clicking Compute All Euclidean Distances:
From SanFrancisco to NewYork, using DFS
From SanFrancisco to NewYork, using BFS
From SanFrancisco to NewYork, using Dijkstra / A* ( hvalue: Euclidean distance )
Test case 4 (input files ucsdxy.txt and ucsdpairs.txt)
After clicking Compute All Euclidean Distances:
From Warren to Revelle, using DFS:
From Warren to Revelle, using BFS:
From Warren to Revelle, using Dijkstra / A* ( hvalue: Euclidean distance )
Test case 5 for A* only (input files cityxy.txt and citypairs.txt)
Change your hvalue method to make hvalue to be 4 times Euclidean distance here.
The large factor here will make A* become too greedy (make it behave more like best
first search, quickly approach the goal but the path is not the shortest).
From Vancouver to Miami, using A* ( hvalue: 4 * Euclidean distance )
You should get the results below:
Part 2 - Disjoint Set and Minimum Spanning Tree
2.1 Graph Class
You will start this part of the assignment by first implementing most of the methods in
Graph class (except for runKruskalsAlg()).
This part should be quite similar to how you implement the Graph class in part 1.
However, there are some slightly different details here.
1. Notice that now when we add a new undirected edge to our graph, we also need
to add this new edge to allUndirectedEdges, which is an ArrayList of Edge
in this class to store all the undirected edges. As allUndirectedEdges will be
used in Kruskal’s Algorithm, you must use the following rules to make your
Kruskal’s Algorithm return the correct set of edges: when adding a new
undirected edge between nameU, nameV, you will additionally add a new
edge with nameU as source vertex, nameV as target vertex and given
weight as weight to allUndirectedEdges.
2. Another main difference here is that our constructor for Graph has a boolean
value edgesGiven, which indicates if the user will provide self-defined edges in
the graph. If edgesGiven is given as true, the method populateAllEdges()
should be disabled. Otherwise if edgesGiven is given as false, addEdge(),
addUndirectedEdge(), computeAllEuclideanDistance() should be
disabled. (To disable any method here, check the boolean and if disabling is
necessary, print any error message then directly return at first)
Note that the purpose of this boolean and disabling appropriate methods is to
accommodate our GUI later. In our GUI, the users are given two options to
compute the minimum spanning tree of the graph defined by input files.
The first option is computing the minimum spanning tree using edges defined
by the input edges file. In this case, edgesGiven will be true.
The second option is computing the minimum spanning tree using all the
possible edges for the given vertices without considering the edges input
file. In this case, edgesGiven will be false. (More on this later)
It is easy to see that if the user wants to use the first option, which is computing
the minimum spanning tree using edges defined by the input edges file, then a
call to populateAllEdges() should be disabled since it will add additional
edges that is not defined by input edges file.
3. In populateAllEdges(), you should add all the possible n(n ? 1) / 2 undirected
edges with weight as Euclidean Distance to allUndirectedEdges in a
graph with n vertices. (You don’t need to add these edges to the adjacent list of
any vertex here.)
You need to think about how to add exactly n(n ? 1) / 2 undirected edges without
adding any duplicate undirected edges. (i.e if undirected edge from u to v was
added, then undirected edge from v to u should not be added)
Hint: Consider using the following code to convert your vertices collection to an
array of vertex, which provides easier access to each vertex in your graph.
Collection<Vertex> vCollection = getVertices();
Vertex[] vertices = vCollection.toArray(new Vertex[vCollection.size()]);
2.2 Disjoint Set Implementation
In this class, you will implement Disjoint Set, which will be useful in Kruskal’s algorithm
to determine if adding a new edge will create a cycle in the graph. Disjoint set has a
simple and beautiful implementation and can check if two vertices are connected in
nearly constant runtime.
You probably need to add some additional instance variables to Vertex class to make
your Disjoint Set work on vertex in your graph. Please read the starter code in Vertex
class for more details.
public Vertex find(Vertex v)
Returns the “sentinel node” representing the set that this vertex belongs to. You must
apply path compression here to optimize the runtime.
public void union(Vertex v1, Vertex v2)
Merges the two sets that two given vertices belongs to. If two given vertices belongs
to the same set, return. Otherwise, apply union by size: make the “sentinel node” of
smaller set as child of “sentinel node” of larger set.
(The union operation here can be done using either union by height or union by size.
The choice here is up to you, but we suggest using union by size here as it is slightly
easier to implement. )
2.3 Testing Disjoint Set
Now you should create a tester named DisjointSetTester.java to verify the
correctness of your disjoint set data structure.
Make sure you have tested the following cases:
1. After you union a set of vertices, calling find on each of them should return the same
sentinel node.
2. For two vertices that are not in the same set, calling find should return different
sentinel node.
2.4 Implement Kruskal’s Algorithm
Now go back to your Graph class and implement the method runKruskalAlg(), now
that Disjoint Set can help you efficiently check if two vertices are in the same connected
component. Here are some notes that you need to know to implement this algorithm:
1. To save us from recomputing the same result, if the result was already
computed before, directly return the result at first.
2. Use the code below to sort allUndirectedEdges in increasing order of weight:
Collections.sort(allUndirectedEdges, Comparator.comparingDouble(e ->
e.getDistance()));
3. Assume that there are v vertices in your graph and all the vertices are in the
same connected component, notice that when your result contains v - 1 edges,
the MST of this graph should already be defined by these edges. The reason is
knowing that the graph is connected and there is no cycle in the MST (since MST
is a tree) implies that there are v - 1 edges in the MST. Using this property, think
about how you can slightly improve the runtime of Kruskal’s Algorithm.
After you finish implementing Kruskal’s, just as in part 1, you should check the
TODO in Display.java to implement two small parts in order to display the
graph correctly.
2.5 Testing Kruskal’s Algorithm
Test case 1 (input files cityxy.txt and citypairs.txt)
Click Load Graph With Edges -> Click Run Kruskal’s Algorithm.
You should see the following result:
Qi
Click Load Graph With Edges -> Click Edge Weight: Euclidean Distance -> Click
Run Kruskal’s Algorithm. You should see the following result:
Click Load Graph Without Edges -> Click Run Kruskal’s Algorithm. You should see
the following result:
Test case 2 (input files ucsdxy.txt and ucsdpairs.txt)
(Imagine you are working for AT&T, and you want know a internet/phone network
design that connects all the locations below on UCSD campus with minimum total cost.
Then you should use MST algorithm such as Kruskal’s to find the MST as your network
design)
Click Load Graph With Edges -> Click Edge Weight: Euclidean Distance -> Click
Run Kruskal’s Algorithm. You should see the following result:
Click Load Graph Without Edges -> Click Run Kruskal’s Algorithm. You should see
the following result:
Submission
There are two parts of submission: PA9 Part 1 and PA9 Part 2
Submission for PA9 Part 1:
Note: You can try using Manhattan distance or manipulate the factor of your hValue
before the final submission, but in the final submission, make sure you are using
Euclidean distance as the heuristic function.
Files to submit:
1. Vertex.java
2. Graph.java
3. Display.java
Submission for PA9 Part 2:
Files to submit:
1. Vertex.java
2. DisjointSet.java
3. DisjointSetTester.java
4. Graph.java
5. Display.java
After you submit your files to GradeScope, wait for the output of submission
script. Make sure you see this after your submission:
THIS IS A SUCCESSFUL SUBMISSION. YOUR SCORE WILL BE UPDATED ONCE
GRADED.
Otherwise, please fix the error and resubmit your files.

因为专业，所以值得信赖。如有需要，请加QQ：99515681 或邮箱：99515681@qq.com 

微信：codinghelp