class Main { public static void main(String args[]) { // A graph Graph g1=new Graph(6); g1.addEdge(0, 1); g1.addEdge(0, 5); g1.addEdge(2, 1); g1.addEdge(5, 4); g1.addEdge(4, 2); g1.addEdge(4, 3); // A graph that contains a cycle Graph g2=new Graph(6); g2.addEdge(0, 1); g2.addEdge(1, 5); g2.addEdge(2, 1); g2.addEdge(4, 2); g2.addEdge(4, 3); g2.addEdge(5, 4); // Question 4: Comment here } } // A Java program to print topological sorting of a graph using indegrees // src: https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/ import java.util.*; //Class to represent a graph class Graph { int V;// No. of vertices //An Array of List which contains //references to the Adjacency List of //each vertex List adj[]; public Graph(int V)// Constructor { this.V = V; adj = new ArrayList[V]; for(int i = 0; i (); } // function to add an edge to graph public void addEdge(int u,int v) { adj[u].add(v); } // prints a Topological Sort of the complete graph public void topologicalSort() { // Create a array to store indegrees of all // vertices. Initialize all indegrees as 0. int indegree[] = new int[V]; // Traverse adjacency lists to fill indegrees of // vertices. This step takes O(V+E) time for(int i = 0; i temp = (ArrayList) adj[i]; for(int node : temp) { indegree[node]++; } } // Create a queue and enqueue all vertices with // indegree 0 Queue q = new LinkedList(); for(int i = 0;i topOrder=new Vector(); while(!q.isEmpty()) { // Extract front of queue (or perform dequeue) // and add it to topological order int u=q.poll(); topOrder.add(u); // Iterate through all its neighboring nodes // of dequeued node u and decrease their in-degree // by 1 for(int node : adj[u]) { // If in-degree becomes zero, add it to queue if(--indegree[node] == 0) q.add(node); } cnt++; } // Print topological order for(int i : topOrder) { System.out.print(i+" "); } System.out.println(); } }

Lab 4 - Topological Sort Download Graph.java and Main.java from Blackboard. Create a Java Project; put all downloaded Java files in the same package. In this assignment you are already given an algorithm for topological sorting. 1. Run the topological sorting algorithm on Graph gi defined in main. Note down the result somewhere. [10 pts] 2. For a topological sort to exist, the graph must not contain any cycles. Modify topologicalSort () method any way you like to handle such cases. The method now must print "A cycle detected!" in such a case. Test your code on Graph g2. (30 pts) 3. Current implementation of topologicalSort () uses queues. Implement a new topologicalSortStack() method so that the underlying data structure is now a stack. [30 pts) 4. Test this modified version with Graph g1. Is the result different from before? Does it mean your code is wrong? Explain in detail as a comment in your source code. [30 pts)