Algorithms (Java) Work

1) Write an algorithm to classify the edges of a directed graph G into the four categories: tree edge, back edge, forward edge and cross edge (defined in Definition 7.14, pages 342-343). Definition 7.14 The edges of a directed graph G are classified according to how they are explored (traversed in their forward direction). 1. If w is undiscovered at the time vw is explored, then vw is called a tree edge, and v becomes the parent of w. 2. If w is an ancestor of v, the vw is called a back edge. (this included vw) 3. If w is a descendent of v, but w has been discovered earlier than the time vw is explored, then vw is called a descendant edge (other name is forward edge). 4. If w has no ancestor/descendant relationship to v, then vw is called a cross edge. 2.) Additional Problems, problem 7.46, page 383. An Euler circuit in an undirected graph is a circuit (i.e, a cycle that may go through some vertices more than once) that includes every edge exactly once. Give an algorithm that find an Euler circuit in a graph, or tells that the graph doesn’t have one. Each of the following program assignments required a graph-loading procedure that reads in a description of a graph from a file and sets up adjacency lists. Attached is some sample code that serves as a starter. Assume the input contains the number of vertices on the first line, followed by a sequence of lines, with each Algorithms Programming Assignments line containing a pair of vertices representing one edge. Write this procedure so that, with small changes, it could be used for any problems. For a fancier interface, arrange for the graph to be loaded from a named file so that “queries” that direct the main program (not the graph-loading procedure above) to solve a particular problem or produce a particular output can be entered at the terminal by the user after loading is completed. In this case, don’t forget to have a “query” that exits the program. Test data should be chosen so that all aspects of a program are…