forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbfs.java
More file actions
62 lines (56 loc) · 1.79 KB
/
bfs.java
File metadata and controls
62 lines (56 loc) · 1.79 KB
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
import java.util.*;
/**
* Implementation of a Breadth First Search
*
* @author Unknown
*
*/
public class bfs{
/**
* The BFS implemented in code to use.
*
* @param a Structure to perform the search on
* @param vertices The vertices to use
* @param source The Source
*/
public static void bfsImplement(byte [][] a,int vertices,int source){ //passing adjacency matrix and no of vertices
byte []b=new byte[vertices]; //flag container containing status of each vertices
Arrays.fill(b,(byte)-1); //status initialization
/* code status
-1 = ready
0 =
542C
waiting
1 = processed */
Stack st = new Stack(vertices); //operational stack
st.push(source); //assigning source
while(!st.isEmpty()){
b[st.peek()]=(byte)0; //assigning waiting status
System.out.println(st.peek());
int pop=st.peek();
b[pop]=(byte)1; //assigning processed status
st.pop(); //removing head of the queue
for(int i=0;i<vertices;i++){
if(a[pop][i]!=0 && b[i]!=(byte)0 && b[i]!=(byte)1 ){
st.push(i);
b[i]=(byte)0; //assigning waiting status
}}}
}
/**
* The main method
*
* @param args Command line arguments
*/
public static void main(String args[]){
Scanner in=new Scanner(System.in);
int vertices=in.nextInt(),source=in.nextInt();
byte [][]a=new byte [vertices][vertices];
//initially all elements of a are initialized with value zero
for(int i=0;i<vertices;i++){
int size =in.nextInt();
for(int j=0;j<size;j++){
a[i][in.nextInt()]=1; //taking adjacency entries by assigning 1
}
}
bfsImplement(a,vertices,source); //function call
in.close();
}
}