SQL Topological Sorting

It is for Directed Acyclic Graph, which linearly describes the ordering of graphs. It is not possible for all graphs, it is possible for only Directed acyclic graphs.

Applications of Topological Sorting:

• Find cycles of a graph.
• Deadlock detection of Operating system.
• Resolution of dependency.
• Ordering of sentences.
• Analysis of critical path.
• Problem with the course schedule.

Java Code for Topological sorting:

import java.io.*;
import java.util.*;
class ConstructingGraph
 {
    private int Vect;
    private ArrayList < ArrayList <Integer> > ad;
   ConstructingGraph (int vec)
    {
        Vec = vec;
        ad = new ArrayList < ArrayList <Integer> >(v);
        for (int i = 0; i < vec; ++i)
            ad. ad (new ArrayList <Integer> ());
    }
    void adEd (int vec, int wi) 
  { 
    adj. ge (v). add (w); 
   }
    void topologicalSort (int vec, boolean visit[], Stack <Integer> sta)
    {
        visit [v] = true;
        Integer j;
        Iterator <Integer> iter = adj. get (v). iterator();
        while (iter. hasNext()) {
            j = iter.next();
            if (!visit [j])
                topologicalSort (j, visit, sta);
        }
        sta. push (new Integer (vec) );
    }
    void topologicalSort1()
    {
        Stack <Integer> sta = new Stack <Integer> ();
 
        boolean visit [] = new boolean [Vec];
        for (int i = 0; i < Vec; i++)
            visit [i] = false;
         for (int i = 0; i < Vec; i++)
            if (visit [i] == false)
                topologicalSort(i, visit, sta);
        while (sta. empty() == false)
            System.out.print(sta.pop() + " ");
    }
 
    // Driver code
    public static void main(String args[])
    {
        ConstructingGraph obj1 = new ConstructingGraph (6);
        obj1. addEdge (5, 2);
        obj1. addEdge (5, 0);
        obj1. addEdge (4, 0);
        obj1. addEdge (4, 1);
        obj1. addEdge (2, 3);
        obj1. addEdge (3, 1);
 
        System.out.println ( "Topological Sort of the given graph");
        obj1. topologicalSort1 ();
    }
}

Output:

Topological Sort of the given graph
5 4 2 3 1 0

Python code for Topological Sort:

from collections import defaultdict
 
 
class ConstructingGraph:
    def __init__ (self, vert):
        self. gra = defaultdict(list) 
        self. V = vert  
    def adEdg (self, p, q):
        self. gra [p]. append (q)
    def topologicalSort (self, q, visit, sta):
        visit [q] = True
        for i in self. gra [q]:
            if visit [i] == False:
                self. topologicalSort (i, visit, sta)
        sta. append (v)
    def topologicalSort1 (self):
        visit = [False] * self.V
        sta = []
        for i in range(self.V):
            if visit [i] == False:
                self. topologicalSort (i, visit, sta)
        print( sta [::-1]) 
g1 = ConstructingGraph (6)
g1. addEdge (5, 2)
g1. addEdge (5, 0)
g1. addEdge (4, 0)
g1. addEdge (4, 1)
g1. addEdge (2, 3)
g1. addEdge (3, 1)
 
print ("Topological Sort of the given graph")
g.topologicalSort1 ()

Output:

Topological Sort of the given graph
5 4 2 3 1 0

C++ code for Topological Sort:

#include <iostream>
#include <list>
#include <stack>
using namespace std;
class ConstructingGraph 
{
    int Vec;
    list <int> * ad;
    void topologicalSort (int p, bool visit[], stack <int>& Sta);
 
public:
    ConstructingGraph (int Vec);
    void adEdg (int q, int p);
    void topologicalSort1 ();
};
 
Graph :: ConstructingGraph (int Vec)
{
    this -> Vec = Vec;
    ad = new list <int> [Vec];
}
 
void Graph :: adEd (int q, int p)
{
    ad [q]. push_back (p);
}
void Graph :: topologicalSort (int q, bool visit [], stack<int>& Sta)
{
    Visit [q] = true;
    list<int> :: iterator j;
    for (j = ad [q]. begin (); i != ad[q]. end (); ++i)
        if (!visited [*j])
            topologicalSort (*j, visit, Sta);
    Sta. push (v);
}
 
void Graph :: topologicalSort1 ()
{
    stack<int> Sta;
 
    // Mark all the vertices as not visited
    bool* visit = new bool [Vec];
    for (int i = 0; i < Vec; i++)
        visit [i] = false;
 
    // Call the recursive helper function
    // to store Topological
    // Sort starting from all
    // vertices one by one
    for (int i = 0; i < Vec; i++)
        if (visit[i] == false)
            topologicalSort (i, visited, Sta);
 
    // Print contents of stack
    while (Sta. empty () == false) {
        cout << Sta.top() << " ";
        Sta. pop ();
    }
}
 
// Driver Code
int main()
{
    // Create a graph given in the above diagram
    ConstructingGraph G1 (6);
    G1. addEdge (5, 2);
    G1. addEdge (5, 0);
    G1. addEdge (4, 0);
    G1. addEdge (4, 1);
    G1. addEdge (2, 3);
    G1. addEdge (3, 1);
 
    cout <<”Topological Sort of the given "
            "graph \n";
 
    // Function Call
    G1. topologicalSort ();
 
    return 0;
}

Output:

Topological Sort of the given graph
5 4 2 3 1 0