Implement methods for the cycle detection and the topological sort algorithms for the digraph Java generic Digraph.java. Then, using your modified generic, build a Java application that advises a student in which order to take courses in their major (e.g., Computer Science).

Your program should first build a digraph with each course and its pre-requisites. Your program should then display the courses in topological order, as long as the digraph has no cycles.

Finding Cycles

You can implement the following algorithms as overloaded methods in the Digraph class to determine whether the digraph has a cycle:

let vStack be a global Stack variable let visited be a global Set variable (already declared in Digraph.java) // is there a cycle in the digraph starting at any vertex? Algorithm hasCycle(): for each vertex nextVertex in the digraph: let vStack be a new Stack let visited by a new Set if (hasCycle(nextVertex)): return true end if end for loop return false end hasCycle()

// is there a cycle in the digraph starting from the given vertex? Algorithm hasCycle(vertex v): let result be a boolean variable, initialized to false vStack.push(v) visited.add(v) for each vertex w adjacent to v: if (visited.contains(w) && vStack.contains(w)): result = true; else if (!visited.contains(w)): result = hasCycle(w) end if end for vStack.pop(); // remove v return result end hasCycle(v)