|
| 1 | +import java.util.ArrayList; |
| 2 | +import java.util.LinkedList; |
| 3 | +import java.util.Queue; |
| 4 | + |
| 5 | +public class BFSTraversalOfGraph { |
| 6 | + public static void addEdge(ArrayList<ArrayList<Integer>> adjList, int s, int d){ |
| 7 | + adjList.get(s).add(d); |
| 8 | + adjList.get(d).add(s); |
| 9 | + } |
| 10 | + |
| 11 | + public static ArrayList<Integer> bfsTravel(ArrayList<ArrayList<Integer>> adjList, int V){ |
| 12 | + ArrayList<Integer> bfs = new ArrayList<>(); |
| 13 | + boolean[] visited = new boolean[V]; |
| 14 | + Queue<Integer> queue = new LinkedList<>(); |
| 15 | + queue.add(0); |
| 16 | + visited[0] = true; |
| 17 | + |
| 18 | + while (!queue.isEmpty()){ |
| 19 | + Integer node = queue.poll(); |
| 20 | + bfs.add(node); |
| 21 | + |
| 22 | + for (Integer it : adjList.get(node)){ |
| 23 | + if(!visited[it]){ |
| 24 | + visited[it] = true; |
| 25 | + queue.add(it); |
| 26 | + } |
| 27 | + } |
| 28 | + } |
| 29 | + return bfs; |
| 30 | + } |
| 31 | + |
| 32 | + public static void main(String[] args) { |
| 33 | + ArrayList<ArrayList<Integer>> list = new ArrayList<>(); |
| 34 | + int V = 10; |
| 35 | + for (int i = 0; i < V; i++) { |
| 36 | + list.add(new ArrayList<>()); |
| 37 | + } |
| 38 | + |
| 39 | + addEdge(list, 0, 1); |
| 40 | + addEdge(list, 1, 2); |
| 41 | + addEdge(list, 1, 3); |
| 42 | + addEdge(list, 0, 4); |
| 43 | + |
| 44 | + System.out.println(bfsTravel(list,V)); |
| 45 | + } |
| 46 | +} |
0 commit comments