Java Design a program in Java that performs a topological sort on a directed gra

Question

Java

Design a program in Java that performs a topological sort on a directed graph. Read the graph using System.in. Store the graph in an adjacency matrix, and print output to System.out.

Input

The first line of input will contain the count of vertices in the graph, this is used to allocate the adjacency matrix.

For example: boolean graph[][] = new boolean[count][count];

The remainder of the file are lines, one for each edge. Each line contains only two integers: source vertex and destination vertex. When the user enters a blank line it should run the program. When the user enters no information at all, the program should terminate.

For each pair, set graph[source][destination]=true. For example, input like this:

5

0   1

2   4

1   4

0   3

Would correspond to a graph like this:

Data structure

You do not need to implement a Graph class. Simply write a main method that creates this boolean graph array and operates on it.

Topological sort algorithm

This algorithm proceeds by calculating the indegree of each vertex. Store this in an int[]. The indegree of a vertex is the number of incoming edges, calculable by adding up all the true values in that vertices matrix column (assuming the matrix rows indicate source vertices).

As your algorithm proceeds, take care not to modify the adjacency matrix.

Try building a list of vertices in the desired order. This will allow you to determine if a cycle exists before printing anything out.

The algorithm functions as follows:

while there is a vertex with indegree 0:

for each vertex V with indegree zero:

subtract 1 from the indegree of every vertex reachable from V

set indegree of V to -1 this indicates we visited V

if (length of the output list < number of vertices) cycle detected

Your program must either print out a valid topological sort of the graph, or print “This graph is cyclic”.
Sample Output

With the input specified above, several outputs are valid. Two examples:   

0

1

3

2

4

or...

2

0

3

1

4

But, if the input is like this:

4

0 1

1 2

2 3

3 1

The output should be

"This graph is cyclic."

while there is a vertex with indegree 0:

for each vertex V with indegree zero:

subtract 1 from the indegree of every vertex reachable from V

set indegree of V to -1 this indicates we visited V

if (length of the output list < number of vertices) cycle detected

Explanation / Answer

Answer:)

Code:

// A Java program to print topological sorting of a DG
import java.io.*;
import java.util.*;

// This class represents a directed graph using adjacency
// list representation
class Graph
{
private int V; // No. of vertices
private LinkedList<Integer> adj[]; // Adjacency List   

//Constructor
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}

// Function to add an edge into the graph
void addEdge(int v,int w) { adj[v].add(w); }

// A recursive function used by topologicalSort
void topologicalSortUtil(int v, Boolean visited[],Stack stack)
{
// Mark the current node as visited.
visited[v] = true;
Integer i;

// Recur for all the vertices adjacent to this vertex
Iterator<Integer> it = adj[v].iterator();
while (it.hasNext())
{
i = it.next();
if (!visited[i])
topologicalSortUtil(i, visited, stack);
}

// Push current vertex to stack which stores result
stack.push(new Integer(v));
}

// The function to do Topological Sort. It uses recursive
// topologicalSortUtil()
void topologicalSort()
{
Stack stack = new Stack();

// Mark all the vertices as not visited
Boolean visited[] = new Boolean[V];
for (int i = 0; i < V; i++)
visited[i] = false;

// Call the recursive helper function to store Topological
// Sort starting from all vertices one by one
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, stack);

// Print contents of stack
while (stack.empty()==false)
System.out.print(stack.pop() + " ");
}

// Driver method
public static void main(String args[])
{
// Create a graph given in the above diagram
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 3);
g.addEdge(1, 4);
g.addEdge(2, 4);

System.out.println("Following is a Topological " +
"sort of the given graph");
g.topologicalSort();
}
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.