Topological sorting program in Java

In this program, we are going to share Topological sorting program in Java. If you are a Java beginner and want to start learning the Java programming, then keep your close attention in this tutorial as I am going to share how to write a java program for topological sorting with the output.

Topological sorting program in Java

Copy the below Java program and execute it with the help of Javac compiler. At the end of this program, We have shared the output of this program.

import java.io.*;

import java.util.*;

class Graph
{
    private int V;
    private LinkedList<Integer> adj[];

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

    void addEdge(int v,int w) { adj[v].add(w); }

    void topologicalSortUtil(int v, boolean visited[],
                             Stack stack)
    {
        visited[v] = true;
        Integer i;

        Iterator<Integer> it = adj[v].iterator();
        while (it.hasNext())
        {
            i = it.next();
            if (!visited[i])
                topologicalSortUtil(i, visited, stack);
        }

        stack.push(new Integer(v));
    }

    void topologicalSort()
    {
        Stack stack = new Stack();

        boolean visited[] = new boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;
        
        // 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() + " ");
    }

    public static void main(String args[])
    {        
        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("The topological sort of the given graph is:");

        g.topologicalSort();
    }
}

import java.io.*;

import java.util.*;

class Graph

{

private int V;

private LinkedList<Integer> adj[];

//Constructor

Graph(int v)

{

V = v;

adj = new LinkedList[v];

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

adj[i] = new LinkedList();

}

void addEdge(int v,int w) { adj[v].add(w); }

void topologicalSortUtil(int v, boolean visited[],

Stack stack)

{

visited[v] = true;

Integer i;

Iterator<Integer> it = adj[v].iterator();

while (it.hasNext())

{

i = it.next();

if (!visited[i])

topologicalSortUtil(i, visited, stack);

}

stack.push(new Integer(v));

}

void topologicalSort()

{

Stack stack = new Stack();

boolean visited[] = new boolean[V];

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

visited[i] = false;

// 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() + " ");

}

public static void main(String args[])

{

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("The topological sort of the given graph is:");

g.topologicalSort();

}

The topological sort of the given graph is:
5 4 2 3 1 0

Liked this program? Do Like & share with your friends 🙂

If you like FreeWebMentor and you would like to contribute, you can write an article and mail your article to [email protected] Your article will appear on the FreeWebMentor main page and help other developers.

Topological sorting program in Java

Topological sorting program in Java

Recommended Posts:

webmentor