The traveling salesperson problem (TSP) is to find the shortest round-trip route that visits each city exactly once and then returns to the starting city. The problem is similar to finding a shortest Hamiltonian cycle in Programming Exercise 28.17. Add the following method in the WeightedGraph class:

// Return a shortest cycle
// Return null if no such cycle exists
public List getShortestHamiltonianCycle()

Data from Programming Exercise 28.17.

Define a new class named UnweightedGraphFindCycle that extends UnweightedGraph with a new method for finding a cycle starting at vertex u with the following header: public List getACycle(int u);
The method returns a List that contains all the vertices in a cycle starting from u. If the graph doesn’t have any cycles, the method returns null. Describe the algorithm in pseudocode and implement it.