Kahn's Topological Sort  Algorithm  Theory And Implementation In Java:- 




In Graph Theory Kahn's Algorithm is used to Solve Topological Sort problem in this algorithm we use BFS and Queue to solve this problem 

1) Kahn's Algorithm is Used to solve Topological Sort Problem

2) Kahn's Algorithm Only Apply On DAG

3) DAG has at least one vertex whose in degree is 0 and at least one vertex whose out degree is zero

the vertex whose in degree is zero means that vertex is not dependent on any other vertex and we can start topological sorting with this vertex.


we will use in degree array to solve this problem


watch this video to know more about Kahn's Algorithm 





After Watching above video i hope you have better understanding about Kahn's algorithm . first try yourself to implement this logic if you are unable to implement then watch this video :





After watching this above video you are able to implement it if no then full java code is below you can see

but please don't copy paste 



class Edge

{

int source, dest;


public Edge(int source, int dest) {

this.source = source;

this.dest = dest;

}

}


import java.util.ArrayList;

import java.util.List;



class Graph

{

// A List of Lists to represent an adjacency list

public List<List<Integer>> adjList = null;


// stores indegree of a vertex

public int  []indegree;


// Constructor

Graph(List<Edge> edges, int N) {

adjList = new ArrayList<>();

for (int i = 0; i < N; i++) {

adjList.add(new ArrayList<>());

}

indegree = new int[N];


// add edges to the undirected graph

for (Edge edge: edges)

{


// add an edge from source to destination

adjList.get(edge.source).add(edge.dest);


// increment in-degree of destination vertex by 1

indegree[edge.dest]++;

}

}

}



import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;


class Main
{
public static void kahnsAlgorithm (Graph graph, int n) {
Queue<Integer> q = new ArrayDeque<>();
for(int i=0;i<graph.indegree.length;i++) {
if(graph.indegree[i] == 0) {
q.add(i);
}
}
//process the queue
while(!q.isEmpty()) {
int v = q.poll();
System.out.print(v +" ");
for(int u:graph.adjList.get(v)) {
graph.indegree[u]--;
if(graph.indegree[u] == 0) {
q.add(u);
}
}
}
}

public static void main(String[] args)
{
// List of graph edges as per above diagram
List<Edge> edges = Arrays.asList(
new Edge(0, 6), new Edge(1, 2), new Edge(1, 4),
new Edge(1, 6), new Edge(3, 0), new Edge(3, 4),
new Edge(5, 1), new Edge(7, 0), new Edge(7, 1)
);

// Set number of vertices in the graph
final int N = 8;

// create a graph from edges
Graph graph = new Graph(edges, N);
kahnsAlgorithm(graph,N);

}
}