Graph BFS Java Example

Algorithms, DSA

We are going to traverse the below graph using BFS Traversal starts from node 0.

0 -> 3 | 0 -> 2 | 2 -> 1 =========> 0, 3, 2, 1

package com.ngdeveloper.algo;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BFS {

    public static void main(String[] args) {
        Graph graph = new Graph(4);
        graph.addEdge(0, 3);
        graph.addEdge(0, 2);
        graph.addEdge(2, 1);
        graph.bfs(0);
    }

    private static class Graph{
        private int vertices;
        private List<List<Integer>> adjacencyList;

        public Graph(int vertices){
            this.vertices = vertices;
            this.adjacencyList = new ArrayList<>(vertices);
            for(int i=0;i<vertices;i++){
                this.adjacencyList.add(new ArrayList<>());
            }
        }

        public void addEdge(int source, int destination) {
            this.adjacencyList.get(source).add(destination);
            this.adjacencyList.get(destination).add(source);
        }

        public void bfs(int start){
            boolean[] visited = new boolean[vertices];
            visited[start] = true;
            System.out.println("Traversed: "+start);
            Queue<Integer> queue = new LinkedList<>();
            queue.add(start);
            while(!queue.isEmpty()) {
                int node = queue.poll();
                List<Integer> neighbors = adjacencyList.get(node);
                for(Integer neighbor: neighbors){
                    if(!visited[neighbor]) {
                        visited[neighbor] = true;
                        queue.add(neighbor);
                        System.out.println("Traversal: "+neighbor);
                    }
                }
            }
        }
    }
}
Traversed: 0
Traversal: 3
Traversal: 2
Traversal: 1
63 comments

63 comments

Leave a Reply