Graph/CycleDetection_inUndirectedGraphUsingBFS.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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
packageGraph;

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

/**
 * TC = O(N+E)
 * SC = O(N+E) + O(N) + O(N)
 */

// class for creating a pair of <node, node's parent node> for storing it to the queue data structure
classPair{
intnode, parentNode;

// constructor
publicPair(intnode, intparentNode){
this.node = node;
this.parentNode = parentNode;
 }
}
publicclassCycleDetection_inUndirectedGraphUsingBFS {
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);
 }
 }

// Method call
booleanisCyclePresent = isCycle(numberOfNodes, adjacencyList);
if(isCyclePresent){
System.out.println("\nResult : Graph contains the cycle.");
 }else{
System.out.println("\nResult : Graph doesn't contain the cycle.");
 }
 }
publicstaticbooleanisCycle(intnumberOfNodes, ArrayList<ArrayList<Integer>> adjacencyList){
// boolean array for checking if the node is visited or not
boolean[] visitedNodes = newboolean[numberOfNodes+1];

// running loop for all nodes
for(inti=1 ; i<=numberOfNodes ; i++){
// if not visited then go for recursive call
if(!visitedNodes[i]){
if(checkCycleInGraph(i, adjacencyList, visitedNodes)){
returntrue;
 }
 }
 }
returnfalse;
 }
publicstaticbooleancheckCycleInGraph(intnode, ArrayList<ArrayList<Integer>> adjacencyList, boolean[] visitedNodes){
Queue<Pair> queue = newLinkedList<>();
queue.offer(newPair(node, -1)); // parent node of first node is always -1 because there is no parent node of first node
visitedNodes[node] = true;

while(!queue.isEmpty()){
intcurrentVisitingNode = queue.peek().node; // this is the current visiting node
intcurrentVisitingNodesParentNode = queue.peek().parentNode; // this is parent of the current visiting node
queue.poll();


// checking for all the adjacent nodes of the current visiting node
for(intadjacentNode : adjacencyList.get(currentVisitingNode)){
// if adjacent node is not visited then visit it
if(!visitedNodes[adjacentNode]){
queue.offer(newPair(adjacentNode, currentVisitingNodesParentNode));
visitedNodes[adjacentNode] = true;
 }
// if the adjacent node is visited, but it is not equal to the parent of the current
// visiting node so how this adjacent node is visited before that means there is a cycle
// that's why the adjacent node is already visited. So, return true.
elseif(currentVisitingNodesParentNode != adjacentNode){
returntrue;
 }
 }
 }
returnfalse;
 }
}