-
Notifications
You must be signed in to change notification settings - Fork 116
/
Graphs:BFS Traversal
44 lines (42 loc) · 1.26 KB
/
Graphs:BFS Traversal
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
import java.util.Scanner;
import java.util.Queue;
import java.util.*;
public class Solution {
public static void printHelper(int edges[][], int sv,boolean visited[]){
Queue<Integer> q = new LinkedList<>();
q.add(sv);
visited[sv]=true;
while(q.size()!=0){
int firstelem = q.remove();
System.out.print(firstelem+" ");
for(int i=0; i<edges.length; i++){
if(edges[firstelem][i]==1 && !visited[i]){
q.add(i);
visited[i]=true;
}
}
}
}
// we have to deal with both connected and non connected
public static void print(int edges[][]){
boolean visited[] = new boolean[edges.length];
for(int i=0; i< edges.length; i++){
if(!visited[i]){
printHelper(edges, i, visited);
}
}
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int V = s.nextInt();
int E = s.nextInt();
int edges[][] = new int[V][V];
for(int i =0; i< E; i++){
int fv = s.nextInt();
int sv = s.nextInt();
edges[fv][sv] = 1;
edges[sv][fv] =1;
}
print(edges);
}
}