// 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

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

{

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

{

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();

}

}

this assignment, you are already given an algorithm for topological sorting. 1. Run the topological sorting algorithm on Graph " g1 defined in main. Print and 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 method called topological SortStack() so that the underlying data structure is now a stack. This new method must use stack methods such as push () and pop () and it must also handle cases with cycles. [30 pts] (Note: You can use the default Stack implementation of Java for this method.) 4. Test this modified version with Graph " g1 ". Is the result different from before? Does it mean your code is wrong if there is a difference? Explain the results and discuss in detail in your own words as a comment in your source code. [30 pts] 5. Submit your Graph.java and Main.java files through Blackboard