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 (de?ned in De?nition 7.14, pages 342-343).
De?nition 7.14 The edges of a directed graph G are classi?ed 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 ?nd 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 ?le 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 ?rst line, followed by a sequence of lines, with each
Algorithms
Programming Assignmentsline 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 ?le 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 tested. Include some of the examples in the text. Java Program 1 page 385 Write a depth-?rst search algorithm to determine if an undirected graph has a cycle. Java Program 2, page 385 Write a breadth-?rst search algorithm to determine if a directed graph has a cycle.
Attachment:- AppendixCode.tar