In this assignment, you are already given an algorithm for topological sorting. 1. Run the topological sorting algorithm on Graph g1 defined in main. Note down the result somewhere. 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. 3. Current implementation of topologicalSort() uses queues. Implement a new topologicalSortStack() method so that the underlying data structure is now a stack. 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.

class Main { public static void main(String args[]) { // A graph Graph g1=new Graph(6); g1.addEdge(0, 2); g1.addEdge(2, 1); g1.addEdge(2, 3); g1.addEdge(3, 4); g1.addEdge(5, 2); g1.addEdge(5, 4); // A graph that contains a cycle Graph g2=new Graph(6); g2.addEdge(1, 2); g2.addEdge(2, 5); g2.addEdge(5, 0); g2.addEdge(5, 1); g2.addEdge(3, 4); g2.addEdge(4, 5); // Question 4: Comment here } }

----------------------------------------------------------

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 < V; i++) adj[i]=new ArrayList(); } // 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 < V; i++) { ArrayList 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 < V; i++) { if(indegree[i]==0) q.add(i); } // Initialize count of visited vertices int cnt = 0; // Create a vector to store result (A topological // ordering of the vertices) Vector 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(); } }