# All Topological Sort in Directed Acyclic Graph

Here given code implementation process.

``````//C program
//All Topological Sort in Directed Acyclic Graph
#include <stdio.h>
#include <stdlib.h>

struct AjlistNode
{
int vId;//Vertices id
struct AjlistNode*next;
};

struct Graph
{
int data; //node key value
struct AjlistNode*next;
};

int size=6;

//set node key value
void setData(struct Graph*node)
{
if(node!=NULL && size>0)
{
int index=0;
for(index;index<size;index++)
{
//set vertic node data
node[index].data=index;//set node key
//Initial no AjlistNode
//set NULL Value
node[index].next=NULL;
}
}
else
{
printf("Vertic Node is Empty");
}
}
//Add Edge from Two given Nodes
void addEdge(struct Graph*node, int V ,int E)
{
//add edge form V to E
//V and E is Node location
if(V<size && E <size)
{
//first create Adjacency node
struct AjlistNode *newEdge=(struct AjlistNode*)malloc(sizeof(struct AjlistNode));
if(newEdge!=NULL)
{

newEdge->next=NULL;
newEdge->vId=E;

struct AjlistNode *temp=node[V].next;

if(temp==NULL)
{
node[V].next=newEdge;
}else
{
//Add node at last
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newEdge;
}
}else
{
printf("\n Memory overflow");
}
}else
{
//not valid Vertices
printf("Invalid Node Vertices %d  %d", V,E);
}
}
//Find indegree of each nodes of a given graph
//Find the  incoming edges of each node
void findIndegree(int indegree[],struct Graph*node)
{

if(node==NULL) return;

struct AjlistNode *temp=NULL;

for (int i = 0; i < size; ++i)
{
temp=node[i].next;

while(temp!=NULL)
{
indegree[temp->vId]++;
temp=temp->next;
}
}
}

void path_sequence(struct Graph*node,
int indegree[],
int visit[],
int index,
int result[])
{
if(index>=size) return;

struct AjlistNode *edges=NULL;

for (int i = 0; i < size; ++i)
{
if(indegree[i]==0 && visit[i]==0)
{

visit[i]=1;
result[index]=i;

edges=node[i].next;

while(edges!=NULL)
{
indegree[edges->vId]--;
edges=edges->next;
}
path_sequence(node,indegree,visit,index+1,result);

//Reset changes

visit[i]=0;

edges=node[i].next;

while(edges!=NULL)
{
indegree[edges->vId]++;
edges=edges->next;
}

}
}

if(index+1==size)
{
for (int i = 0; i < size; ++i)
{
printf("%3d",result[i]);
}
printf("\n");
}

}
void topologicalSort(struct Graph*node)
{
int indegree[size],visit[size],result[size];

for(int i=0;i<size;i++)
{
indegree[i]=0;
visit[i]=0;
}
int status=-1;

//Find indegree of each node in graph
findIndegree(indegree,node);

printf("\n");
for (int i = 0; i < size; i++)
{

if(indegree[i]==0)
{
status=i;
break;
}
}
if(status!=-1)
{
path_sequence(node,indegree,visit,0,result);

}else
{
printf("No topological Sort in this graph");
}
}

//Display Adjacency list of vertex
void printGraph(struct Graph*node)
{
if(node!=NULL)
{
struct AjlistNode *temp=NULL;
for(int index=0;index<size;index++)
{
printf("\n Adjacency list of vertex %d  :",index);
temp=node[index].next;
while(temp!=NULL)
{
//temp->vId is graph node vertices
//in this case temp->vId is same as
//node[temp->vId].data

printf("  %d",node[temp->vId].data);
temp=temp->next;
}
}
}else
{
printf("Empty Graph");
}
}
int main()
{
struct Graph*node=NULL;
node=(struct Graph*)malloc(sizeof(struct Graph)*size);

if(node==NULL)
{
printf("\n Memory overflow");

}else
{
//First set node keys
setData(node);
//Connected two node with Edges

printGraph(node);
topologicalSort(node);
}
return 0;
}

```
```

#### Output

`````` Adjacency list of vertex 0  :
Adjacency list of vertex 1  :  0  4  5
Adjacency list of vertex 2  :  0  4  5
Adjacency list of vertex 3  :  4  5
Adjacency list of vertex 4  :
Adjacency list of vertex 5  :  4
1  2  0  3  5  4
1  2  3  0  5  4
1  2  3  5  0  4
1  2  3  5  4  0
1  3  2  0  5  4
1  3  2  5  0  4
1  3  2  5  4  0
2  1  0  3  5  4
2  1  3  0  5  4
2  1  3  5  0  4
2  1  3  5  4  0
2  3  1  0  5  4
2  3  1  5  0  4
2  3  1  5  4  0
3  1  2  0  5  4
3  1  2  5  0  4
3  1  2  5  4  0
3  2  1  0  5  4
3  2  1  5  0  4
3  2  1  5  4  0
``````
``````/*
C++ Program
All Topological Sort in Directed Acyclic Graph
*/

#include<iostream>

using namespace std;
class AjlistNode {
public:
int id;
AjlistNode *next;
AjlistNode(int value) {
this->id = value;
this->next = NULL;
}
};
class Vertices {
public:

int data;
AjlistNode *next;
Vertices()
{
this->data = 0;
this->next = NULL;
}
Vertices(int value) {
this->data = value;
this->next = NULL;
}
};
class MyGraph {
public:

int size;
Vertices *node;
MyGraph(int value) {
this->size = value;
this->node = new Vertices[value];
///this->setData();
}
void setData() {
if (this->node == NULL) {
cout << "\nEmpty Graph";
} else {
int index = 0;
while (index < this->size) {
this->node[index] = index;
index++;
}
}
}
void addEdge(int start, int end) {
AjlistNode *newEdge = new AjlistNode(end);
if (this->node[start].next == NULL) {
this->node[start].next = newEdge;
} else {
AjlistNode *temp = this->node[start].next;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newEdge;
}
}
void findIndegree(int *indegree) {
if (this->node == NULL) {
return;
}
AjlistNode *temp = NULL;
int i = 0;
while (i < this->size) {
temp = this->node[i].next;
while (temp != NULL) {
indegree[temp->id]++;
temp = temp->next;
}
i++;
}
}
void path_sequence(int *indegree, bool *visit, int index, int *result) {
if (index >= this->size) {
return;
}
AjlistNode *edges = NULL;
int i = 0;
while (i < this->size) {
if (indegree[i] == 0 && visit[i] == false) {
visit[i] = true;
result[index] = i;
edges = this->node[i].next;
while (edges != NULL) {
indegree[edges->id]--;
edges = edges->next;
}
this->path_sequence(indegree, visit, index + 1, result);
visit[i] = false;
edges = this->node[i].next;
while (edges != NULL) {
indegree[edges->id]++;
edges = edges->next;
}
}
i++;
}
if (index + 1 == this->size) {
i = 0;
while (i < this->size) {
cout << "  " << result[i];
i++;
}
cout << "\n";
}
}
void topologicalSort() {
int *indegree = new int[this->size];
bool *visit = new bool[this->size];
int *result = new int[this->size];
int i = 0;
while (i < this->size) {
indegree[i] = 0;
visit[i] = false;
i++;
}
int status = -1;
this->findIndegree(indegree);
cout << "\n Topological Sort \n";
i = 0;
while (i < this->size) {
if (indegree[i] == 0) {
status = i;
break;
}
i++;
}
if (status != -1) {
this->path_sequence(indegree, visit, 0, result);
} else {
cout << "No topological Sort in this graph";
}
}
void printGraph() {
if (this->size > 0 && this->node != NULL) {
int index = 0;
while (index < this->size) {
cout << "\nAdjacency list of vertex " << index << " :";
AjlistNode *temp = this->node[index].next;
while (temp != NULL) {
cout << " " << this->node[temp->id].data;
temp = temp->next;
}
index++;
}
}
}
};
int main() {
int totalNode = 6;
MyGraph g(totalNode);
g.printGraph();
g.topologicalSort();
return 0;
}```
```

#### Output

`````` Adjacency list of vertex 0  :
Adjacency list of vertex 1  :  0  4  5
Adjacency list of vertex 2  :  0  4  5
Adjacency list of vertex 3  :  4  5
Adjacency list of vertex 4  :
Adjacency list of vertex 5  :  4
1  2  0  3  5  4
1  2  3  0  5  4
1  2  3  5  0  4
1  2  3  5  4  0
1  3  2  0  5  4
1  3  2  5  0  4
1  3  2  5  4  0
2  1  0  3  5  4
2  1  3  0  5  4
2  1  3  5  0  4
2  1  3  5  4  0
2  3  1  0  5  4
2  3  1  5  0  4
2  3  1  5  4  0
3  1  2  0  5  4
3  1  2  5  0  4
3  1  2  5  4  0
3  2  1  0  5  4
3  2  1  5  0  4
3  2  1  5  4  0
``````
``````// Java program
// All Topological Sort in Directed Acyclic Graph

class AjlistNode {

public int id; //Vertices node key
public AjlistNode next;
public AjlistNode(int value) {
id = value;
next = null;
}
}
class Vertices {

public int data;
public AjlistNode next;

public Vertices(int value) {
data = value;
next = null;
}
}
public class MyGraph {

//number of Vertices
private int size;
private Vertices[] node;

public MyGraph(int value) {
//set value
size = value;

node = new Vertices[size];
//set initial values of graph node
this.setData();
}

//set initial node value
public void setData() {
if (node == null) {
System.out.println("\nEmpty Graph");
} else {

int index = 0;

while (index < size) {
// avoid java.lang.NullPointerException
node[index] = new Vertices(index);

index++;
}
}
}

//connect two node
public void addEdge(int start, int last) {
AjlistNode newEdge = new AjlistNode(last);

if (node[start].next == null) {
node[start].next = newEdge;
} else {
AjlistNode temp = node[start].next;

while (temp.next != null) {
temp = temp.next;
}
temp.next = newEdge;
}
}
void findIndegree(int[] indegree) {

if (node == null) {
return;
}
AjlistNode temp = null;
int i = 0;
while (i < size) {
temp = node[i].next;

while (temp != null) {
indegree[temp.id]++;
temp = temp.next;
}
i++;
}
}
void path_sequence(int[] indegree, boolean[] visit, int index, int[] result) {

if (index >= size) {
return;
}
AjlistNode edges = null;

int i = 0;

while (i < size) {

if (indegree[i] == 0 && visit[i] == false) {
visit[i] = true;
result[index] = i;
edges = node[i].next;

while (edges != null) {
indegree[edges.id]--;
edges = edges.next;
}
path_sequence(indegree, visit, index + 1, result);
visit[i] = false;
edges = node[i].next;

while (edges != null) {
indegree[edges.id]++;
edges = edges.next;
}
}
i++;
}

if (index + 1 == size) {
i = 0;

while (i < size) {

System.out.print("  " + result[i]);

i++;
}

System.out.print("\n");
}
}
void topologicalSort() {
int[] indegree = new int[size];
boolean[] visit = new boolean[size];
int[] result = new int[size];
int i = 0;
while (i < size) {
indegree[i] = 0;
visit[i] = false;
i++;
}
int status = -1;
findIndegree(indegree);

System.out.print("\n Topological Sort \n");
i = 0;
while (i < size) {

if (indegree[i] == 0) {
status = i;
break;
}
i++;
}

if (status != -1) {
path_sequence(indegree, visit, 0, result);
} else {

System.out.print("No topological Sort in this graph");
}
}

public void printGraph() {

if (size > 0 && node != null) {
int index = 0;
while (index < size) {
System.out.print("\nAdjacency list of vertex " + index + " :");
AjlistNode temp = node[index].next;
while (temp != null) {
System.out.print(" " + node[temp.id].data);
temp = temp.next;
}
index++;
}
}
}

public static void main(String[] args) {
int totalNode = 6;

MyGraph g = new MyGraph(totalNode);

//Connected two node with Edges

g.printGraph();
g.topologicalSort();

}
}```
```

#### Output

`````` Adjacency list of vertex 0  :
Adjacency list of vertex 1  :  0  4  5
Adjacency list of vertex 2  :  0  4  5
Adjacency list of vertex 3  :  4  5
Adjacency list of vertex 4  :
Adjacency list of vertex 5  :  4
1  2  0  3  5  4
1  2  3  0  5  4
1  2  3  5  0  4
1  2  3  5  4  0
1  3  2  0  5  4
1  3  2  5  0  4
1  3  2  5  4  0
2  1  0  3  5  4
2  1  3  0  5  4
2  1  3  5  0  4
2  1  3  5  4  0
2  3  1  0  5  4
2  3  1  5  0  4
2  3  1  5  4  0
3  1  2  0  5  4
3  1  2  5  0  4
3  1  2  5  4  0
3  2  1  0  5  4
3  2  1  5  0  4
3  2  1  5  4  0
``````
``````// C# program
// All Topological Sort in Directed Acyclic Graph
using System;
public class AjlistNode {

public int id; //Vertices node key
public AjlistNode next;
public AjlistNode(int value) {
id = value;
next = null;
}
}
public class Vertices {

public int data;
public AjlistNode next;

public Vertices(int value) {
data = value;
next = null;
}
}
public class MyGraph {

//number of Vertices
private int size;
private Vertices[] node;

public MyGraph(int value) {
//set value
size = value;

node = new Vertices[size];
//set initial values of graph node
this.setData();
}

//set initial node value
public void setData() {
if (node == null) {
Console.WriteLine("\nEmpty Graph");
} else {

int index = 0;

while (index < size) {
// avoid C#.lang.NullPointerException
node[index] = new Vertices(index);

index++;
}
}
}

//connect two node
public void addEdge(int start, int last) {
AjlistNode newEdge = new AjlistNode(last);

if (node[start].next == null) {
node[start].next = newEdge;
} else {
AjlistNode temp = node[start].next;

while (temp.next != null) {
temp = temp.next;
}
temp.next = newEdge;
}
}
void findIndegree(int[] indegree) {

if (node == null) {
return;
}
AjlistNode temp = null;
int i = 0;
while (i < size) {
temp = node[i].next;

while (temp != null) {
indegree[temp.id]++;
temp = temp.next;
}
i++;
}
}
void path_sequence(int[] indegree, Boolean[] visit, int index, int[] result) {

if (index >= size) {
return;
}
AjlistNode edges = null;

int i = 0;

while (i < size) {

if (indegree[i] == 0 && visit[i] == false) {
visit[i] = true;
result[index] = i;
edges = node[i].next;

while (edges != null) {
indegree[edges.id]--;
edges = edges.next;
}
path_sequence(indegree, visit, index + 1, result);
visit[i] = false;
edges = node[i].next;

while (edges != null) {
indegree[edges.id]++;
edges = edges.next;
}
}
i++;
}

if (index + 1 == size) {
i = 0;

while (i < size) {

Console.Write("  " + result[i]);

i++;
}

Console.Write("\n");
}
}
void topologicalSort() {
int[] indegree = new int[size];
Boolean[] visit = new Boolean[size];
int[] result = new int[size];
int i = 0;
while (i < size) {
indegree[i] = 0;
visit[i] = false;
i++;
}
int status = -1;
findIndegree(indegree);

Console.Write("\n Topological Sort \n");
i = 0;
while (i < size) {

if (indegree[i] == 0) {
status = i;
break;
}
i++;
}

if (status != -1) {
path_sequence(indegree, visit, 0, result);
} else {

Console.Write("No topological Sort in this graph");
}
}

public void printGraph() {

if (size > 0 && node != null) {
int index = 0;
while (index < size) {
Console.Write("\nAdjacency list of vertex " + index + " :");
AjlistNode temp = node[index].next;
while (temp != null) {
Console.Write(" " + node[temp.id].data);
temp = temp.next;
}
index++;
}
}
}

public static void Main(String[] args) {
int totalNode = 6;

MyGraph g = new MyGraph(totalNode);

//Connected two node with Edges

g.printGraph();
g.topologicalSort();

}
}```
```

#### Output

``````Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
Topological Sort
1  2  0  3  5  4
1  2  3  0  5  4
1  2  3  5  0  4
1  2  3  5  4  0
1  3  2  0  5  4
1  3  2  5  0  4
1  3  2  5  4  0
2  1  0  3  5  4
2  1  3  0  5  4
2  1  3  5  0  4
2  1  3  5  4  0
2  3  1  0  5  4
2  3  1  5  0  4
2  3  1  5  4  0
3  1  2  0  5  4
3  1  2  5  0  4
3  1  2  5  4  0
3  2  1  0  5  4
3  2  1  5  0  4
3  2  1  5  4  0``````
``````# Python 3 Program
# All Topological Sort in Directed Acyclic Graph

class AjlistNode :

def __init__(self, value) :
self.id = value
self.next = None

class Vertices :

def __init__(self, value) :
self.data = value
self.next = None

class MyGraph :

def __init__(self, value) :
self.size = value
self.node = [0]*self.size
self.setData()

def setData(self) :
if (self.node == None) :
print("\nEmpty Graph")
else :
index = 0
while (index < self.size) :
self.node[index] = Vertices(index)
index += 1

def addEdge(self, start, last) :
newEdge = AjlistNode(last)
if (self.node[start].next == None) :
self.node[start].next = newEdge
else :
temp = self.node[start].next
while (temp.next != None) :
temp = temp.next

temp.next = newEdge

def findIndegree(self, indegree) :
if (self.node == None) :
return

temp = None
i = 0
while (i < self.size) :
temp = self.node[i].next
while (temp != None) :
indegree[temp.id] += 1
temp = temp.next

i += 1

def path_sequence(self, indegree, visit, index, result) :
if (index >= self.size) :
return

edges = None
i = 0
while (i < self.size) :
if (indegree[i] == 0 and visit[i] == False) :
visit[i] = True
result[index] = i
edges = self.node[i].next
while (edges != None) :
indegree[edges.id] -= 1
edges = edges.next

self.path_sequence(indegree, visit, index + 1, result)
visit[i] = False
edges = self.node[i].next
while (edges != None) :
indegree[edges.id] += 1
edges = edges.next

i += 1

if (index + 1 == self.size) :
i = 0
while (i < self.size) :
print(" ", result[i],end=" ")
i += 1

print(end="\n")

def topologicalSort(self) :
indegree = [0]*self.size
visit = [False]*self.size
result = [0]*self.size
i = 0
while (i < self.size) :
indegree[i] = 0
visit[i] = False
i += 1

status = -1
self.findIndegree(indegree)
print("\n Topological Sort ")
i = 0
while (i < self.size) :
if (indegree[i] == 0) :
status = i
break

i += 1

if (status != -1) :
self.path_sequence(indegree, visit, 0, result)
else :
print("No topological Sort in this graph")

def printGraph(self) :
if (self.size > 0 and self.node != None) :
index = 0
while (index < self.size) :
print("\nAdjacency list of vertex ", index ," :",end="  ")
temp = self.node[index].next
while (temp != None) :
print(self.node[temp.id].data,end="  ")
temp = temp.next

index += 1

def main() :
totalNode = 6
g = MyGraph(totalNode)
g.printGraph()
g.topologicalSort()

if __name__ == "__main__":
main()```
```

#### Output

``````Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
Topological Sort
1  2  0  3  5  4
1  2  3  0  5  4
1  2  3  5  0  4
1  2  3  5  4  0
1  3  2  0  5  4
1  3  2  5  0  4
1  3  2  5  4  0
2  1  0  3  5  4
2  1  3  0  5  4
2  1  3  5  0  4
2  1  3  5  4  0
2  3  1  0  5  4
2  3  1  5  0  4
2  3  1  5  4  0
3  1  2  0  5  4
3  1  2  5  0  4
3  1  2  5  4  0
3  2  1  0  5  4
3  2  1  5  0  4
3  2  1  5  4  0``````
``````# Ruby Program
# All Topological Sort in Directed Acyclic Graph

class AjlistNode
attr_accessor :id, :next
def initialize(value)
@id = value
@next = nil
end
end

class Vertices
attr_accessor :data, :next
def initialize(value)
@data = value
@next = nil
end
end

class MyGraph
attr_accessor :size, :node
def initialize(value)
@size = value
@node = Array.new(@size,0)
self.setData()
end
def setData()
if (@node == nil)
print("\nEmpty Graph")
else
index = 0
while (index < @size)
@node[index] = Vertices.new(index)
index += 1
end
end
end
newEdge = AjlistNode.new(last)
if (@node[start].next == nil)
@node[start].next = newEdge
else
temp = @node[start].next
while (temp.next != nil)
temp = temp.next
end
temp.next = newEdge
end
end
def findIndegree(indegree)
if (@node == nil)
return
end
temp = nil
i = 0
while (i < @size)
temp = @node[i].next
while (temp != nil)
indegree[temp.id] += 1
temp = temp.next
end
i += 1
end
end
def path_sequence(indegree, visit, index, result)
if (index >= @size)
return
end
edges = nil
i = 0
while (i < @size)
if (indegree[i] == 0 and visit[i] == false)
visit[i] = true
result[index] = i
edges = @node[i].next
while (edges != nil)
indegree[edges.id] -= 1
edges = edges.next
end
self.path_sequence(indegree, visit, index + 1, result)
visit[i] = false
edges = @node[i].next
while (edges != nil)
indegree[edges.id] += 1
edges = edges.next
end
end
i += 1
end
if (index + 1 == @size)
i = 0
while (i < @size)
print("  ", result[i])
i += 1
end
print("\n")
end
end
def topologicalSort()
indegree =  Array.new(@size,0)
visit =  Array.new(@size,false)
result =  Array.new(@size,0)
i = 0
while (i < @size)
indegree[i] = 0
visit[i] = false
i += 1
end
status = -1
self.findIndegree(indegree)
print("\n Topological Sort \n")
i = 0
while (i < @size)
if (indegree[i] == 0)
status = i
break
end
i += 1
end
if (status != -1)
self.path_sequence(indegree, visit, 0, result)
else
print("No topological Sort in this graph")
end
end
def printGraph()
if (@size > 0 and @node != nil)
index = 0
while (index < @size)
print("\nAdjacency list of vertex ", index ,"  :")
temp = @node[index].next
while (temp != nil)
print(" ", @node[temp.id].data)
temp = temp.next
end
index += 1
end
end
end
end
def main()
totalNode = 6
g = MyGraph.new(totalNode)
g.printGraph()
g.topologicalSort()
end

main()```
```

#### Output

``````Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
Topological Sort
1  2  0  3  5  4
1  2  3  0  5  4
1  2  3  5  0  4
1  2  3  5  4  0
1  3  2  0  5  4
1  3  2  5  0  4
1  3  2  5  4  0
2  1  0  3  5  4
2  1  3  0  5  4
2  1  3  5  0  4
2  1  3  5  4  0
2  3  1  0  5  4
2  3  1  5  0  4
2  3  1  5  4  0
3  1  2  0  5  4
3  1  2  5  0  4
3  1  2  5  4  0
3  2  1  0  5  4
3  2  1  5  0  4
3  2  1  5  4  0``````
``````<?php
/*
Php Program
All Topological Sort in Directed Acyclic Graph
*/

class AjlistNode {
public \$id;
public \$next;

function __construct(\$value) {
\$this->id = \$value;
\$this->next = null;
}
}
class Vertices {
public \$data;
public \$next;

function __construct(\$value) {
\$this->data = \$value;
\$this->next = null;
}
}
class MyGraph {
private \$size;
private \$node;

function __construct(\$value) {
\$this->size = \$value;
\$this->node = array_fill(0, \$this->size, 0);
\$this->setData();
}
public  function setData() {
if (\$this->node == null) {
echo("\nEmpty Graph");
} else {
\$index = 0;
while (\$index < \$this->size) {
\$this->node[\$index] = new Vertices(\$index);
\$index++;
}
}
}
public  function addEdge(\$start, \$last) {
\$newEdge = new AjlistNode(\$last);
if (\$this->node[\$start]->next == null) {
\$this->node[\$start]->next = \$newEdge;
} else {
\$temp = \$this->node[\$start]->next;
while (\$temp->next != null) {
\$temp = \$temp->next;
}
\$temp->next = \$newEdge;
}
}

function findIndegree(&\$indegree) {
if (\$this->node == null) {
return;
}
\$temp = null;
\$i = 0;
while (\$i < \$this->size) {
\$temp = \$this->node[\$i]->next;
while (\$temp != null) {
\$indegree[\$temp->id]++;
\$temp = \$temp->next;
}
\$i++;
}
}

function path_sequence(&\$indegree, &\$visit, \$index, &\$result) {
if (\$index >= \$this->size) {
return;
}
\$edges = null;
\$i = 0;
while (\$i < \$this->size) {
if (\$indegree[\$i] == 0 && \$visit[\$i] == false) {
\$visit[\$i] = true;
\$result[\$index] = \$i;
\$edges = \$this->node[\$i]->next;
while (\$edges != null) {
\$indegree[\$edges->id]--;
\$edges = \$edges->next;
}
\$this->path_sequence(\$indegree, \$visit, \$index + 1, \$result);
\$visit[\$i] = false;
\$edges = \$this->node[\$i]->next;
while (\$edges != null) {
\$indegree[\$edges->id]++;
\$edges = \$edges->next;
}
}
\$i++;
}
if (\$index + 1 == \$this->size) {
\$i = 0;
while (\$i < \$this->size) {
echo("  ". \$result[\$i]);
\$i++;
}
echo("\n");
}
}

function topologicalSort() {
\$indegree = array_fill(0, \$this->size, 0);;
\$visit = array_fill(0, \$this->size, false);;
\$result = array_fill(0, \$this->size, 0);;
\$i = 0;
while (\$i < \$this->size) {
\$indegree[\$i] = 0;
\$visit[\$i] = false;
\$i++;
}
\$status = -1;
\$this->findIndegree(\$indegree);
echo("\n Topological Sort \n");
\$i = 0;
while (\$i < \$this->size) {
if (\$indegree[\$i] == 0) {
\$status = \$i;
break;
}
\$i++;
}
if (\$status != -1) {
\$this->path_sequence(\$indegree, \$visit, 0, \$result);
} else {
echo("No topological Sort in this graph");
}
}
public  function printGraph() {
if (\$this->size > 0 && \$this->node != null) {
\$index = 0;
while (\$index < \$this->size) {
echo("\nAdjacency list of vertex ". \$index ." :");
\$temp = \$this->node[\$index]->next;
while (\$temp != null) {
echo(" ". \$this->node[\$temp->id]->data);
\$temp = \$temp->next;
}
\$index++;
}
}
}
}

function main() {
\$totalNode = 6;
\$g = new MyGraph(\$totalNode);
\$g->printGraph();
\$g->topologicalSort();
}
main();```
```

#### Output

``````Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
Topological Sort
1  2  0  3  5  4
1  2  3  0  5  4
1  2  3  5  0  4
1  2  3  5  4  0
1  3  2  0  5  4
1  3  2  5  0  4
1  3  2  5  4  0
2  1  0  3  5  4
2  1  3  0  5  4
2  1  3  5  0  4
2  1  3  5  4  0
2  3  1  0  5  4
2  3  1  5  0  4
2  3  1  5  4  0
3  1  2  0  5  4
3  1  2  5  0  4
3  1  2  5  4  0
3  2  1  0  5  4
3  2  1  5  0  4
3  2  1  5  4  0``````
``````/*
Node Js Program
All Topological Sort in Directed Acyclic Graph
*/

class AjlistNode {

constructor(value) {
this.id = value;
this.next = null;
}
}
class Vertices {

constructor(value) {
this.data = value;
this.next = null;
}
}
class MyGraph {

constructor(value) {
this.size = value;
this.node = Array(value).fill(0);
this.setData();
}
setData() {
if (this.node == null) {
process.stdout.write("\nEmpty Graph");
} else {
var index = 0;
while (index < this.size) {
this.node[index] = new Vertices(index);
index++;
}
}
}
var newEdge = new AjlistNode(last);
if (this.node[start].next == null) {
this.node[start].next = newEdge;
} else {
var temp = this.node[start].next;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newEdge;
}
}
findIndegree(indegree) {
if (this.node == null) {
return;
}
var temp = null;
var i = 0;
while (i < this.size) {
temp = this.node[i].next;
while (temp != null) {
indegree[temp.id]++;
temp = temp.next;
}
i++;
}
}
path_sequence(indegree, visit, index, result) {
if (index >= this.size) {
return;
}
var edges = null;
var i = 0;
while (i < this.size) {
if (indegree[i] == 0 && visit[i] == false) {
visit[i] = true;
result[index] = i;
edges = this.node[i].next;
while (edges != null) {
indegree[edges.id]--;
edges = edges.next;
}
this.path_sequence(indegree, visit, index + 1, result);
visit[i] = false;
edges = this.node[i].next;
while (edges != null) {
indegree[edges.id]++;
edges = edges.next;
}
}
i++;
}
if (index + 1 == this.size) {
i = 0;
while (i < this.size) {
process.stdout.write("  " + result[i]);
i++;
}
process.stdout.write("\n");
}
}
topologicalSort() {
var indegree = Array(this.size).fill(0);;
var visit = Array(this.size).fill(false);;
var result = Array(this.size).fill(0);;
var i = 0;
while (i < this.size) {
indegree[i] = 0;
visit[i] = false;
i++;
}
var status = -1;
this.findIndegree(indegree);
process.stdout.write("\n Topological Sort \n");
i = 0;
while (i < this.size) {
if (indegree[i] == 0) {
status = i;
break;
}
i++;
}
if (status != -1) {
this.path_sequence(indegree, visit, 0, result);
} else {
process.stdout.write("No topological Sort in this graph");
}
}
printGraph() {
if (this.size > 0 && this.node != null) {
var index = 0;
while (index < this.size) {
process.stdout.write("\nAdjacency list of vertex " + index + " :");
var temp = this.node[index].next;
while (temp != null) {
process.stdout.write(" " + this.node[temp.id].data);
temp = temp.next;
}
index++;
}
}
}
}

function main() {
var totalNode = 6;
var g = new MyGraph(totalNode);
g.printGraph();
g.topologicalSort();
}

main();```
```

#### Output

``````Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
Topological Sort
1  2  0  3  5  4
1  2  3  0  5  4
1  2  3  5  0  4
1  2  3  5  4  0
1  3  2  0  5  4
1  3  2  5  0  4
1  3  2  5  4  0
2  1  0  3  5  4
2  1  3  0  5  4
2  1  3  5  0  4
2  1  3  5  4  0
2  3  1  0  5  4
2  3  1  5  0  4
2  3  1  5  4  0
3  1  2  0  5  4
3  1  2  5  0  4
3  1  2  5  4  0
3  2  1  0  5  4
3  2  1  5  0  4
3  2  1  5  4  0``````
``````/*
Swift 4 Program
All Topological Sort in Directed Acyclic Graph
*/

class AjlistNode {
var id: Int;
var next: AjlistNode? ;
init(_ value: Int) {
self.id = value;
self.next = nil;
}
}
class Vertices {
var data: Int;
var next: AjlistNode? ;
init(_ value: Int) {
self.data = value;
self.next = nil;
}
}
class MyGraph {
var size : Int;
var node : [Vertices]? = [Vertices]() ;
init(_ value: Int) {
self.size = value;

var i : Int = 0;
while (i<value) {
self.node!.append(Vertices(i));
i+=1;
}

}

func addEdge(_ start: Int, _ last: Int) {
let newEdge: AjlistNode? = AjlistNode(last);
if (self.node![start].next == nil) {
self.node![start].next = newEdge;
} else {
var temp: AjlistNode? = self.node![start].next;
while (temp!.next != nil) {
temp = temp!.next;
}
temp!.next = newEdge;
}
}
func findIndegree(_ indegree: inout [Int] ) {
if (self.node == nil) {
return;
}
var temp: AjlistNode? = nil;
var i: Int = 0;
while (i < self.size) {
temp = self.node![i].next;
while (temp != nil) {
indegree[temp!.id] += 1;
temp = temp!.next;
}
i += 1;
}
}
func path_sequence(_ indegree: inout [Int] , _ visit : inout [Bool] , _ index : Int, _ result: inout [Int] ) {
if (index >= self.size) {
return;
}
var edges: AjlistNode? = nil;
var i: Int = 0;
while (i < self.size) {
if (indegree[i] == 0 && visit[i] == false) {
visit[i] = true;
result[index] = i;
edges = self.node![i].next;
while (edges != nil) {
indegree[edges!.id] -= 1;
edges = edges!.next;
}
self.path_sequence(&indegree, &visit, index + 1, &result);
visit[i] = false;
edges = self.node![i].next;
while (edges != nil) {
indegree[edges!.id] += 1;
edges = edges!.next;
}
}
i += 1;
}
if (index + 1 == self.size) {
i = 0;
while (i < self.size) {
print(" ", result[i],terminator:" ");
i += 1;
}
print(terminator:"\n");
}
}
func topologicalSort() {
var indegree: [Int] = Array(repeating:0,count:self.size);
var visit: [Bool] = Array(repeating:false,count:self.size);
var result: [Int] = Array(repeating:0,count:self.size);
var i: Int = 0;
while (i < self.size) {
indegree[i] = 0;
visit[i] = false;
i += 1;
}
var status: Int = -1;
self.findIndegree(&indegree);
print("\n Topological Sort ");
i = 0;
while (i < self.size) {
if (indegree[i] == 0) {
status = i;
break;
}
i += 1;
}
if (status != -1) {
self.path_sequence(&indegree, &visit, 0, &result);
} else {
print("No topological Sort in this graph");
}
}
func printGraph() {
if (self.size > 0 && self.node != nil) {
var index: Int = 0;
while (index < self.size) {
print("\nAdjacency list of vertex ", index ," :",terminator:" ");
var temp: AjlistNode? = self.node![index].next;
while (temp != nil) {
print(" ", self.node![temp!.id].data,terminator:" ");
temp = temp!.next;
}
index += 1;
}
}
}
}
func main() {
let totalNode: Int = 6;
let g: MyGraph? = MyGraph(totalNode);
g!.printGraph();
g!.topologicalSort();
}
main();```
```

#### Output

``````Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
Topological Sort
1  2  0  3  5  4
1  2  3  0  5  4
1  2  3  5  0  4
1  2  3  5  4  0
1  3  2  0  5  4
1  3  2  5  0  4
1  3  2  5  4  0
2  1  0  3  5  4
2  1  3  0  5  4
2  1  3  5  0  4
2  1  3  5  4  0
2  3  1  0  5  4
2  3  1  5  0  4
2  3  1  5  4  0
3  1  2  0  5  4
3  1  2  5  0  4
3  1  2  5  4  0
3  2  1  0  5  4
3  2  1  5  0  4
3  2  1  5  4  0``````
``````// Scala program
// All Topological Sort in Directed Acyclic Graph
class AjlistNode(var next: AjlistNode,
var id: Int) {

//Vertices node key
def this(id: Int) {
this(null, id);
}
}
class Vertices(var next: AjlistNode,
var data: Int) {
def this(value: Int) {
this(null, value);
}
}
class MyGraph(var node: Array[Vertices],
var size: Int) {
//number of Vertices
def this(size: Int) {
//set value
this(Array.fill[Vertices](size)(null), size);

//set initial values of graph node
this.setData();
}
//set initial node value
def setData(): Unit = {
if (this.node == null) {
print("\nEmpty Graph");
} else {
var index: Int = 0;
while (index < this.size) {
// avoid Scala.lang.NullPointerException
this.node(index) = new Vertices(index);
index += 1;
}
}
}
//connect two node
def addEdge(start: Int, last: Int): Unit = {
val newEdge: AjlistNode = new AjlistNode(last);

if (this.node(start).next == null) {
this.node(start).next = newEdge;
} else {
var temp: AjlistNode = this.node(start).next;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newEdge;
}
}
def findIndegree(indegree: Array[Int]): Unit = {
if (this.node == null) {
return;
}
var temp: AjlistNode = null;
var i: Int = 0;
while (i < this.size) {
temp = this.node(i).next;
while (temp != null) {
indegree(temp.id) += 1;
temp = temp.next;
}
i += 1;
}
}
def path_sequence(indegree: Array[Int], visit :
Array[Boolean], index: Int, result: Array[Int]): Unit = {
if (index >= this.size) {
return;
}
var edges: AjlistNode = null;
var i: Int = 0;
while (i < this.size) {
if (indegree(i) == 0 && visit(i) == false) {
visit(i) = true;
result(index) = i;
edges = this.node(i).next;
while (edges != null) {
indegree(edges.id) -= 1;
edges = edges.next;
}
this.path_sequence(indegree, visit, index + 1, result);
visit(i) = false;
edges = this.node(i).next;
while (edges != null) {
indegree(edges.id) += 1;
edges = edges.next;
}
}
i += 1;
}
if (index + 1 == this.size) {
i = 0;
while (i < this.size) {
print(" " + result(i));
i += 1;
}
print("\n");
}
}
def topologicalSort(): Unit = {
var indegree: Array[Int] = Array.fill[Int](size)(0);
var visit: Array[Boolean] = Array.fill[Boolean](size)(false);
val result: Array[Int] = Array.fill[Int](size)(0);
var i: Int = 0;
while (i < this.size) {
indegree(i) = 0;
visit(i) = false;
i += 1;
}
var status: Int = -1;
this.findIndegree(indegree);
print("\n Topological Sort \n");
i = 0;
while (i < this.size && status == -1) {
if (indegree(i) == 0) {
status = i;
}
i += 1;
}
if (status != -1) {
this.path_sequence(indegree, visit, 0, result);
} else {
print("No topological Sort in this graph");
}
}
def printGraph(): Unit = {
if (this.size > 0 && this.node != null) {
var index: Int = 0;
while (index < this.size) {
print("\nAdjacency list of vertex " + index + " :");
var temp: AjlistNode = this.node(index).next;
while (temp != null) {
print(" " + this.node(temp.id).data);
temp = temp.next;
}
index += 1;
}
}
}
}
object Main {
def main(args: Array[String]): Unit = {
val totalNode: Int = 6;
val g: MyGraph = new MyGraph(totalNode);

//Connected two node with Edges
g.printGraph();
g.topologicalSort();
}
}```
```

#### Output

``````Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4 5
Adjacency list of vertex 2 : 0 4 5
Adjacency list of vertex 3 : 4 5
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
Topological Sort
1 2 0 3 5 4
1 2 3 0 5 4
1 2 3 5 0 4
1 2 3 5 4 0
1 3 2 0 5 4
1 3 2 5 0 4
1 3 2 5 4 0
2 1 0 3 5 4
2 1 3 0 5 4
2 1 3 5 0 4
2 1 3 5 4 0
2 3 1 0 5 4
2 3 1 5 0 4
2 3 1 5 4 0
3 1 2 0 5 4
3 1 2 5 0 4
3 1 2 5 4 0
3 2 1 0 5 4
3 2 1 5 0 4
3 2 1 5 4 0``````

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.