Graph/CycleDetection_inDirectedGraph_usingBFS_KahnAlgorithm.java at main · adv11/Graph · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
packageGraph;

importjava.util.ArrayList;
importjava.util.LinkedList;
importjava.util.Queue;
importjava.util.Scanner;

publicclassCycleDetection_inDirectedGraph_usingBFS_KahnAlgorithm {
publicstaticvoidmain(String[] args) {
Scannersc = newScanner(System.in);
ArrayList<ArrayList<Integer>> adjacencyList = newArrayList<>();

// Taking input for number of nodes
System.out.println("Enter the number of nodes:");
intnumberOfNodes = sc.nextInt();

// initializing adjacencyList with new ArrayList<>()
for(inti=1 ; i<=numberOfNodes+1 ; i++){
adjacencyList.add(newArrayList<>());
 }

// taking input of adjacent nodes of particular node
for(inti=1 ; i<=numberOfNodes ; i++){
System.out.println("Enter number of adjacent nodes to the node : " + i);
intcountOfAdjacentNodes = sc.nextInt();

// taking input of the particular adjacent nodes to the node i
System.out.println("Enter adjacent nodes:");
for(intj=0 ; j<countOfAdjacentNodes ; j++){

// taking input of adjacent node
intadjacentNode = sc.nextInt();
// adding the adjacent node to the particular node i
adjacencyList.get(i).add(adjacentNode);
 }
 }

if(isCyclic(adjacencyList, numberOfNodes)){
System.out.println("Graph has cycle.");
 }else{
System.out.println("Graph has not cycle.");
 }
 }
publicstaticbooleanisCyclic(ArrayList<ArrayList<Integer>> adjacencyList, intnumberOfNodes){
int[] inDegree = newint[numberOfNodes+1]; // for storing indegree of the nodes
for(ArrayList<Integer> adjacentNodesList : adjacencyList){
for(intadjacentNode : adjacentNodesList){
inDegree[adjacentNode]++;
 }
 }

Queue<Integer> queue = newLinkedList<>();
for(intnode=1 ; node<=numberOfNodes ; node++){ // adding the nodes into the queue with indegree 0
if(inDegree[node] == 0){
queue.offer(node);
 }
 }

intvisitedNodes = 0; // for counting the nodes visited while BFS call
while (!queue.isEmpty()){
intcurrentNode = queue.poll(); // current node
visitedNodes++;

// adjacent nodes of the current node
for(intadjacentNode : adjacencyList.get(currentNode)){
inDegree[adjacentNode]--; // decreasing the indegree of the adjacent nodes

// if the indegree becomes 0 then add that node into the queue data structure
if(inDegree[adjacentNode] == 0){
queue.offer(adjacentNode);
 }
 }
 }

// if the number of visited nodes is equal to the total number of nodes then it
// means there is no cycle so return false else return true
if(visitedNodes == numberOfNodes){
returnfalse;
 }
returntrue;
 }
}