Graph/BFS.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
packageGraph;

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

/**
 * TC = O(N+E) : N is time taken to visit N nodes, and E is time taken for visiting through adjacent nodes overall.
 * Sc = O(N+E) + O(N) + O(E) : O(N+E) for final data structure, O(N) for boolean array and O(E) for queue data structure.
 */
publicclassBFS {
publicstaticArrayList<Integer> bfsGraph(intnumberOfNodes, ArrayList<ArrayList<Integer>> adjacencyList){
intconnectedComponents = 0;
ArrayList<Integer> bfs = newArrayList<>(); // for storing resultant bfs traversal
boolean[] visitedNodes = newboolean[numberOfNodes+1]; // for checking if the node is visited or not

// running loop for all nodes
for(inti=1 ; i<=numberOfNodes ; i++){

// checking if node is already visited or not
if(!visitedNodes[i]){

// queue data structure for bfs traversal
Queue<Integer> queue = newLinkedList<>();
queue.add(i);
visitedNodes[i] = true;

// while queue has an element
// run the loop
while(!queue.isEmpty()){

// this is currently visiting node
intcurrentVisitingNode = queue.poll();
// adding it to the final resultant data structure
bfs.add(currentVisitingNode);

// adding adjacent nodes of currentVisitingNode
for(intadjacentNode : adjacencyList.get(currentVisitingNode)){

// checking if the adjacent node is already visited or not
// if not then visit it otherwise not
if(!visitedNodes[adjacentNode]){
visitedNodes[adjacentNode] = true; // marking visited
queue.add(adjacentNode); // adding it to the queue data structure
 }
 }
 }
connectedComponents++;
 }
 }

System.out.println("Number of connected components in the given graph is : " + connectedComponents);
returnbfs;
 }
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);
 }
 }

// calling bfs method
ArrayList<Integer> bfs = bfsGraph(numberOfNodes, adjacencyList);

// printing the resultant bfs traversal
System.out.println("BFS Traversal of the given graph is:");
for(intnode : bfs){
System.out.print(node + " ");
 }
 }
}