# Java - Implementation of Kahn's Algorithm- Easy to Understand.

• ``````public boolean canFinish(int numCourses, int[][] prerequisites) {
//represent the graph using incoming and outgoing nodes map
Map<Integer, Set<Integer>> outgoingNodes = new HashMap<>();
Map<Integer, Set<Integer>> incomingNodes = new HashMap<>();

//Initialize
for (int i = 0; i < numCourses; i++) {
outgoingNodes.put(i, new HashSet<Integer>());
incomingNodes.put(i, new HashSet<Integer>());
}

//Loop through the 2D arrays [0, 1] means to take course 0 you have to take course 1 first. i.e. 0 <- 1
for (int i = 0; i < prerequisites.length; i++) {
//[A, B] B is the prerequisites for A. A <- B
// to A, B is the incoming node
// to B, A is the outgoing node
}

//Apply Kahn's algorithm
/**
*
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge
while S is non-empty do
remove a node n from S
add n to tail of L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
*/

List<Integer> L = new ArrayList<>();
//Initialize S
for(Map.Entry<Integer, Set<Integer>> entry : incomingNodes.entrySet()){
if(entry.getValue().isEmpty()){
}
}

while(!S.isEmpty()){
Integer n = S.remove();
HashSet<Integer> copysOfOutgoingNodesN = new HashSet<>(outgoingNodes.get(n)); //to avoid concurrentModificationException
for(Integer m : copysOfOutgoingNodesN){
outgoingNodes.get(n).remove(m);
incomingNodes.get(m).remove(n);

if(incomingNodes.get(m).isEmpty()){
}
}
}

for (int i = 0; i < numCourses; i++) {
if(!incomingNodes.get(i).isEmpty() || !outgoingNodes.get(i).isEmpty()){
return false;
}
}

return true;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.