For Java Implement the in-degree based version of the Topological Sort algorithm

Question

For Java

Implement the in-degree based version of the Topological Sort algorithm.

1. Take as input a list of vertices and a list of edges for a directed graph.

2. Create the adjacency list representation, storing the outlist and the indegree for each vertex. (Count the vertices as you do so.) Set the label for the next vertex to 0.

3. Traverse the vertex headers in the adjacency list, placing any vertex with indegree 0 on a worklist (use a queue).

4. While the worklist is not empty: remove the top vertex, give it the current label, and increment the next_label. Traverse its adjacency list, decrementing the indegree of each of its out-neighbors. If an indegree becomes zero, add that vertex to the worklist.

5. If next_label == the number of vertices, report the topological labeling in numerical order. If not, report that there is a cycle.

Explanation / Answer

Here is the code for the implementation of the in-degree based version of the Topological Sort algorithm.

// topological sorting of a graph using indegrees

import java.util.*;

import java.util.Queue;

//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 <Integer> adj[];

    public Graph(int V)// Constructor

    {

        this.V = V;

        adj = new ArrayList[V];

        for(int i = 0; i < V; i++)

            adj[i]=new ArrayList<Integer>();

    }

    // 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<Integer> temp = (ArrayList<Integer>) adj[i];

            for(int node : temp)

            {

                indegree[node]++;

            }

        }

        // Create a queue and enqueue all vertices with

        // indegree 0

        Queue<Integer> q = new LinkedList<Integer>();

        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 <Integer> topOrder=new Vector<Integer>();

        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 neighbouring 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++;

        }   

        // Check if there was a cycle      

        if(cnt != V)

        {

            System.out.println("There exists a cycle in the graph");

            return ;

        }

        // Print topological order         

        for(int i : topOrder)

        {

            System.out.print(i+" ");

        }

    }

}

// Driver program to test above functions

class Main

{

    public static void main(String[] args)

    {

        // Create a graph given in the above diagram

        Graph g=new Graph(6);

        g.addEdge(5, 2);

        g.addEdge(5, 0);

        g.addEdge(4, 0);

        g.addEdge(4, 1);

        g.addEdge(2, 3);

        g.addEdge(3, 1);

        System.out.println("Topological Sort for the graph");

        g.topologicalSort();

    }

}

OUTPUT:

Topological Sort for the graph

4 5 2 0 3 1

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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