The content of this article was learned on June 3rd and 4th, due to negligence, it was not uploaded in time, sorry.
The functions of the campus navigation part are roughly as follows:
(1) Able to print all event points, including a brief introduction to each event point;
(2) It is possible to query the corresponding Hamilton cycle route at the specified event point, that is, start from the current source point, pass through all the event points only once, and print out the route, which can be realized by the horse-treading chessboard algorithm;
(3) Any two race points can be specified, the shortest distance can be found through the Floyd algorithm, and the corresponding route can be printed out.
Before starting, you need to prepare to abstract the View class of a race point. The corresponding code is as follows:
@Data
@AllArgsConstructor
@NoArgsConstructor
public class View {
// destination number
private int id;
// destination name
private String name;
// Destination introduction
private String introduction;
}
We need to use a data structure such as a graph to reflect the relationship between various attractions. In Java, we can use an adjacency matrix (two-dimensional array) to store the distance between attractions. The rows and columns of the array represent two event points respectively. . At the same time, use a one-dimensional array to store all the event point Views. This class should also include the following three functions:
(1) Initialize the event point array and adjacency matrix by passing in the number of event points. By default, the distance between two scenic spots in the matrix is initialized to Integer.MAX_VALUE, which means there is no edge (undirected edge) between them.
(2) Define a method for adding event point elements to the specified index position of the event point array;
(3) Define a method that can add an undirected edge between two specified event points;
The corresponding MGrapt.java race point map class is as follows:
@Data
@AllArgsConstructor
@NoArgsConstructor
public class MGraph {
// The maximum weight, indicating that the two attractions are not reachable
private static final int INF = Integer.MAX_VALUE;
// vertex array
private View[] views;
// adjacency matrix
private int[][] matrix;
/**
* Construction method (initialize the vertices and adjacency matrix of the graph)
* @param size The number of vertices of the graph
*/
public MGraph(int size) {
// Initialize vertex array and adjacency matrix
views = new View[size];
matrix = new int[size][size];
// traverse the adjacency matrix and initialize all elements to the maximum weight
for (int[] row : matrix)
Arrays. fill(row, INF);
}
/**
* Add attractions
* @param i vertex number
* @param view vertex object
*/
public void addView(int i, View view) {
views[i] = view;
}
/**
* add edge
* @param i vertex number
* @param j vertex number
* @param weight weight value
*/
public void addEdge(int i, int j, int weight){
// undirected graph, the distance between two vertices is the same
matrix[i][j] = weight;
matrix[j][i] = weight;
}
}
Then write a ViewAndMGraphInitial class to automatically load game points and drawings when the program starts:
public class ViewAndMGraphInitial {
// attractions information
public static View[] views;
// picture
public static MGraph mGraph;
// Use static code blocks to initialize attractions information and maps
static {
// Create 10 spots
views = new View[10];
views[0] = new View(0, "administrative building", "administrative office");
views[1] = new View(1, "Haiyunhu", "A place where I have nothing to wander");
views[2] = new View(2, "Library", "Where to go to sleep");
views[3] = new View(3, "East Canteen", "East District Cooking Spot");
views[4] = new View(4, "East Playground", "East District Training Ground");
views[5] = new View(5, "South Gate", "It is easy to climb over the wall here");
views[6] = new View(6, "Style Center", "It is full of Xiuer");
views[7] = new View(7, "West Playground", "West District Training Ground");
views[8] = new View(8, "Jingshi Building", "The place where the class is held");
views[9] = new View(9, "Wenli Building", "The tallest building on campus");
// Create graph
mGraph = new MGraph(views. length);
// add vertices
for (int i = 0; i < views. length; i ++ ) {
mGraph.addView(i, views[i]);
}
// add edges and weights (undirected graph)
// 0 Administration Building 1 Haiyunhu (also 1 Haiyunhu 0 Administration Building)
mGraph. addEdge(0, 1, 300);
// 0 Administration Building 9 Texture Building
mGraph. addEdge(0, 9, 700);
// 1 Ocean Hu 2 Library
mGraph. addEdge(1, 2, 600);
// 2 Library 3 East Cafeteria
mGraph. addEdge(2, 3, 100);
// 2 library 9 texture building
mGraph. addEdge(2, 9, 400);
// 2 Library 7 West Playground
mGraph. addEdge(2, 7, 550);
// 3 East Canteen 4 East Playground
mGraph. addEdge(3, 4, 100);
// 3 East Dining Hall 6 Culture and Sports Center
mGraph. addEdge(3, 6, 550);
// 4 East Playground 5 South Gate
mGraph. addEdge(4, 5, 250);
// 5 South Gate 6 Culture and Sports Center
mGraph. addEdge(5, 6, 250);
// 6 Culture and Sports Center 7 West Playground
mGraph. addEdge(6, 7, 100);
// 7 West Playground 8 Jingshi Building
mGraph. addEdge(7, 8, 100);
// 8 Jingshi Building 9 Texture Building
mGraph. addEdge(8, 9, 100);
}
}
After completing the above preparatory work, start to implement various functions. First, browse all the event points on campus, just traverse the event point array directly:
@Data
@AllArgsConstructor
@NoArgsConstructor
public class ViewsServiceImpl implements ViewsService {
// Attraction map
private MGraph graph;
/**
* Display all attractions information
*/
@Override
public void displayAllViews() {
System.out.println("------------------ Attraction information ------------------");
for (View view : graph. getViews()) {
System.out.println("ID: " + view.getId());
System.out.println("Name: " + view.getName());
System.out.println("Introduction: " + view.getIntroduction());
System.out.println("----------------------");
}
}
}
For the realization of the Hamiltonian path, we can implement it in the TourPathServiceImpl business interface implementation class, which should contain an MGraph graph attribute as the event point graph, and an int[] path attribute to store the corresponding vertex number on the Hamiltonian path, which is actually The subscript of the corresponding event point element, the size of the array is the number of event points.
The implementation class should include an isSafe to determine whether the current vertex can be added to the specified index position, the logic is relatively simple:
(1) First judge that there is no edge between the vertex v and the vertex with the index pos-1, and return false if there is no edge. The reason why it is pos-1 is because pos starts from 1, and the path array starts from 0, in order to avoid the array subscript out of bounds.
(2) Then traverse the first pos arrays to determine whether the vertex v is already in the Hamilton cycle, and return false if it already exists.
The corresponding code is as follows:
/**
* Check if vertex v can be added to the Hamiltonian cycle at index pos
* @param v vertex number
* @param pos index
* @return true: can be added; false: cannot be added
*/
private boolean isSafe(int v, int pos) {
// returns false if there is no edge between vertex v and the vertex with index pos-1
if (graph. getMatrix()[path[pos - 1]][v] == Integer. MAX_VALUE)
return false;
// Return false if vertex v is already in a Hamiltonian cycle
for (int i = 0; i < pos; i ++ )
if (path[i] == v)
return false;
// otherwise return true
return true;
}
Next, write a hamiltonianCycleUtil method to solve the Hamiltonian cycle, the implementation logic is as follows:
(1) If all vertices have been visited (that is, the index of the current vertex is equal to the number of vertices), directly check whether there is an edge between the last vertex and the starting vertex, and if there is no edge, the solution fails.
(2) Traverse all vertices and solve the problem, see the following code comments for details.
The corresponding code is as follows:
/**
* Recursive function of Hamiltonian cycle, used to solve Hamiltonian cycle
*
* @param pos The index of the current vertex
* @param lastVisited last visited vertex
* @param visited Record whether the vertex has been visited
* @return true: found a Hamiltonian cycle; false: did not find a Hamiltonian cycle
*/
private boolean hamiltonianCycleUtil(int pos, int lastVisited, boolean[] visited) {
// If all vertices have been visited (that is, the index of the current vertex is equal to the number of vertices)
if (pos == graph. getViews(). length) {
// Check if there is an edge between the last vertex and the start vertex
return graph.getMatrix()[path[pos - 1]][path[0]] != Integer.MAX_VALUE;
}
// traverse all vertices
for (int v = 0; v < graph. getViews(). length; v ++ ) {
// If vertex v can be added to the position of index pos of the Hamiltonian cycle (that is, there is an edge between vertex v and the vertex with index pos-1, and vertex v has not been visited)
if ((graph.getMatrix()[path[pos - 1]][v] != Integer.MAX_VALUE) & amp; & amp; (!visited[v]) & amp; & amp; (v != lastVisited) ) {
// Add vertex v to the Hamiltonian cycle at index pos
path[pos] = v;
// mark vertex v as visited
visited[v] = true;
// Call itself recursively to check if vertex v can be added to the Hamiltonian cycle at index pos + 1
if (hamiltonianCycleUtil(pos + 1, v, visited))
return true;
// If vertex v cannot be added to the Hamiltonian cycle at index pos + 1, remove vertex v from the Hamiltonian cycle
path[pos] = -1;
visited[v] = false;
}
}
return false;
}
Finally, call the above method to solve and print the Hamiltonian path. For details, see the following code:
/**
* Find the Hamiltonian path
* @param source the name of the starting vertex
*/
@Override
public void hamiltonian(String source) {
// get all spots
View[] views = graph. getViews();
// get the number of vertices
int num = views. length;
// Record whether the passed vertex has been visited
boolean[] visited = new boolean[num];
// Use Arrays' fill() method to set all elements in the path array to -1
Arrays. fill(path, -1);
// Set all elements in the visited array to false using the fill() method of Arrays
Arrays.fill(visited, false);
// Find the number of the starting vertex
int sourceIndex = -1;
for (int i = 0; i < num; i ++ ) {
if (views[i].getName().equals(source)) {
sourceIndex = i;
break;
}
}
// If the number of the starting vertex is -1, return
if (sourceIndex == -1) {
System.out.println("No start vertex found!");
return;
}
// build a hamiltonian cycle from the starting vertex
path[0] = sourceIndex;
// mark the starting vertex as visited
visited[sourceIndex] = true;
// If a Hamiltonian cycle is found, print the Hamiltonian path (starting from the position with subscript 1, because the position with subscript 0 already stores the number of the starting vertex)
if (hamiltonianCycleUtil(1, sourceIndex, visited)) {
printSolution(path);
} else {
System.out.println("Hamilton path not found!");
}
}
/**
* Print Hamiltonian path (print vertex names)
* @param path Vertex number on the Hamiltonian path
*/
private void printSolution(int[] path) {
System.out.println("The following is the recommended path:");
for (int j : path) {
System.out.print(graph.getViews()[j].getName() + " -> ");
}
System.out.println(graph.getViews()[path[0]].getName());
}