Program Plan: Include the required import statement. Create a package “main”. Add a java class named “Edge” to the package which is used to get the edges from the graph. Add a java class named “Graph” to the package which is used to add and remove vertices, edges. Add a java class named “UnweightedGraph” to the package which is used to store vertices and neighbors. Add a java class named “WeightedGraph” to the package which is used to get the weighted edges and print the edges. Add a java class named “WeightedEdge” to the package which is used to compare edges. Add a java class named “NineTailModel” to the package which is used to compare edges. Define the main method using public static main. Allocate memory to the class “Test”. Define the “Test” class. Declare and set the values for the variables. Create an object1 for the “Graph” class. Display the edge. Allocate memory for the “edge” variable. Create an object2 for the “Graph” class. Display the edge. Display the results. Define the “Graph” class. A graph interface gets created. Method to return the size gets defined. Method to return the vertices gets defined. Method to return the index gets created. Method to get the neighbor node gets created. Method to get the degree gets created. Method to print the edges. Method to clear the node gets created. Method to add the edges, add vertex gets created. Method to remove the vertices gets defined. Method for the depth first search gets defined. Method for the breadth first search gets defined. Create a class “UnweightedGraph”: New list for the vertices gets created. New list for the neighbor node gets created. Create an empty constructor. Method to create new graph gets created and adjacency list gets created. Method to create an adjacency list gets created. Method to return the size of the vertices. Method to return the index of the vertices gets defined. Method to gets the neighbor node gets defined. Method to return the degree of the vertices gets created. Method to print the Edges gets created. New to clear the graph gets created. Method to add vertex gets created. Method to add edge gets created. Method to perform the depth first search gets defined. Method to perform breadth first search gets defined. Search tree gets returned. Create a class “SearchTree” Define the method to return the root. Method to return the parent of the vertices Method to return the search order gets defined. Method to return the number of vertices found gets defined. Method to get the path of the vertices gets defined. Loop to validate the path gets defined. Path gets returned. Method to print the path gets defined. Method to print the tree gets defined. Display the edge. Display the root. Condition to validate the parent node to display the vertices gets created. Define the “getHamiltonianPath” method. If the size of graph is equal to “i” value, return a Hamiltonian path from the specified vertex object. Otherwise, return null if the graph does not have a Hamiltonian path. Define the “getHamiltonianPath” method. Return the value using array list. Define the “getHamiltonianPath” method. Declare the required variables. If the length of the graph, indicate no subpath from “i” is found. The vertices in the Hamiltonian path are stored in result. Reorder the adjacency list for each vertex. Create a list for path Add vertex to the result list. Get the next vertex in the path. Return null if no Hamiltonian path is found. Define the “reorderNeigborsBasedOnDegree” method. Check the condition. Find the maximum in the list. Check the condition and swap the list with another list. Define the “allVisited” method. Declare the variables. Check if all the elements in array is visited and return true. Otherwise return the result. Define the “getHamiltonianPath” method. Declare the variables If all the vertices are found then include all the vertices. Then search for a Hamiltonian path from “v”. Define “getHamiltonianCycle” method. Return a Hamiltonian cycle. Define “getHamiltonianCycle” method. Declare the variable. If the length of the graph, indicate no subpath from “i” is found. The vertices in the Hamiltonian path are stored in result. Reorder the adjacency list for each vertex. Create a list for path Add vertex to the result list. Get the next vertex in the path. Return null if no Hamiltonian path is found. Define “getHamiltonianCycle” method. Declare the variable. If all the vertex is visited the return true. Otherwise backtrack “v” is marked unvisited. Return false. Define “isCycle” method. Return the value.

Question

Want to see the full answer?

Answer 1

Question

Chapter 28, Problem 28.17PE

Program Plan Intro

Program Plan:

Include the required import statement.

Create a package “main”.

Add a java class named “Edge” to the package which is used to get the edges from the graph.

Add a java class named “Graph” to the package which is used to add and remove vertices, edges.

Add a java class named “UnweightedGraph” to the package which is used to store vertices and neighbors.

Add a java class named “WeightedGraph” to the package which is used to get the weighted edges and print the edges.

Add a java class named “WeightedEdge” to the package which is used to compare edges.

Add a java class named “NineTailModel” to the package which is used to compare edges.

Define the main method using public static main.

Allocate memory to the class “Test”.

Define the “Test” class.

Declare and set the values for the variables.

Create an object1 for the “Graph” class.

Display the edge.

Allocate memory for the “edge” variable.

Create an object2 for the “Graph” class.

Display the edge.

Display the results.

Define the “Graph” class.

A graph interface gets created.

Method to return the size gets defined.

Method to return the vertices gets defined.

Method to return the index gets created.

Method to get the neighbor node gets created.

Method to get the degree gets created.

Method to print the edges.

Method to clear the node gets created.

Method to add the edges, add vertex gets created.

Method to remove the vertices gets defined.

Method for the depth first search gets defined.

Method for the breadth first search gets defined.

Create a class “UnweightedGraph”:

New list for the vertices gets created.

New list for the neighbor node gets created.

Create an empty constructor.

Method to create new graph gets created and adjacency list gets created.

Method to create an adjacency list gets created.

Method to return the size of the vertices.

Method to return the index of the vertices gets defined.

Method to gets the neighbor node gets defined.

Method to return the degree of the vertices gets created.

Method to print the Edges gets created.

New to clear the graph gets created.

Method to add vertex gets created.

Method to add edge gets created.

Method to perform the depth first search gets defined.

Method to perform breadth first search gets defined.

Search tree gets returned.

Create a class “SearchTree”

Define the method to return the root.

Method to return the parent of the vertices

Method to return the search order gets defined.

Method to return the number of vertices found gets defined.

Method to get the path of the vertices gets defined.

Loop to validate the path gets defined.

Path gets returned.

Method to print the path gets defined.

Method to print the tree gets defined.

Display the edge.

Display the root.

Condition to validate the parent node to display the vertices gets created.

Define the “getHamiltonianPath” method.

If the size of graph is equal to “i” value, return a Hamiltonian path from the specified vertex object.

Otherwise, return null if the graph does not have a Hamiltonian path.

Define the “getHamiltonianPath” method.

Return the value using array list.

Define the “getHamiltonianPath” method.

Declare the required variables.

If the length of the graph, indicate no subpath from “i” is found.

The vertices in the Hamiltonian path are stored in result.

Reorder the adjacency list for each vertex.

Create a list for path

Add vertex to the result list.

Get the next vertex in the path.

Return null if no Hamiltonian path is found.

Define the “reorderNeigborsBasedOnDegree” method.

Check the condition.

Find the maximum in the list.

Check the condition and swap the list with another list.

Define the “allVisited” method.

Declare the variables.

Check if all the elements in array is visited and return true.

Otherwise return the result.

Define the “getHamiltonianPath” method.

Declare the variables

If all the vertices are found then include all the vertices.

Then search for a Hamiltonian path from “v”.

Define “getHamiltonianCycle” method.

Return a Hamiltonian cycle.

Define “getHamiltonianCycle” method.

Declare the variable.

If the length of the graph, indicate no subpath from “i” is found.

The vertices in the Hamiltonian path are stored in result.

Reorder the adjacency list for each vertex.

Create a list for path

Add vertex to the result list.

Get the next vertex in the path.

Return null if no Hamiltonian path is found.

Define “getHamiltonianCycle” method.

Declare the variable.

If all the vertex is visited the return true.

Otherwise backtrack “v” is marked unvisited.

Return false.

Define “isCycle” method.

Return the value.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Students have asked these similar questions

(0)URGENT!!!! Please use this graph class and SOLVE FOR ISOLATEDTRIPLETS QUESTION AND AVERAGE BALANCE RATIO Here is the graph class: public class Graph {private final int V;private int E;private final Bag<Integer>[] adj; /*** Create an empty graph with V vertices.*/@SuppressWarnings("unchecked")public Graph(int V) {if (V < 0) throw new Error("Number of vertices must be nonnegative");this.V = V;this.E = 0;this.adj = new Bag[V];for (int v = 0; v < V; v++) {adj[v] = new Bag<>();}} /*** Return the number of vertices in the graph.*/public int V() { return V; } /*** Return the number of edges in the graph.*/public int E() { return E; } /*** Add the undirected edge v-w to graph.* @throws java.lang.IndexOutOfBoundsException unless both 0 <= v < V and 0 <= w < V*/public void addEdge(int v, int w) {if (v < 0 || v >= V) throw new IndexOutOfBoundsException();if (w < 0 || w >= V) throw new IndexOutOfBoundsException();E++;adj[v].add(w);adj[w].add(v);} /***…

1. Using the above class map, write function void map::mapToGraph(graph &g){...} to create a graph g that represents the legal moves in the map m. Each vertex should represent a cell, and each edge should represent a legal move between adjacent cells. 2. Write a recursive function findPathRecursive(graph &g, stack &moves) that looks for a path from the start island to the destination island. If a path from the start to the destination exists, your function should call the map::printPath() function that should print a sequence of correct moves (Go left, Go right, Go down, Go up, etc.). If no path from the start to the destination exists, the program should print, "No path exists". If a solution exists the solver should also simulate the solution to each map by calling the map::print() function. The map::print() function prints out a map visualization, with the goal and current position of the car in the map at each move, marked to show the progress. Hint: consider recursive-DFS. 3.…

In this project, you will develop algorithms that find road routes through the bridges to travel between islands. The input is a text file containing data about the given map. Each file begins with the number of rows and columns in the map considered as maximum latitudes and maximum longitudes respectively on the map. The character "X" in the file represents the water that means if a cell contains "X" then the traveler is not allowed to occupy that cell as this car is not drivable on water. The character "0" in the file represents the road connected island. That means if a cell contains "0" then the traveler is allowed to occupy that cell as this car can drive on roads. The traveler starts at the island located at latitude = 0 and longitude = 0 (i.e., (0,0)) in the upper left comer, and the goal is to drive to the island located at (MaxLattitude-1, MaxLongitudes-1) in the lower right corner. A legal move from an island is to move left, right, up, or down to an immediately adjacent cell…