Graph Traversal: Program to traverse a graph using breadth first search (bfs) technique

Breadth First Search

Breadth first search is a traversal algorithm for graph or tree type of data structures. In traversal, we visit each node or vertice of the graph or tree. BFS is one way of traversing the nodes in a graph or tree. 

BFS follows a particular order of visiting nodes in a graph:

• We start with any node from the graph. It can be called root node or start node
• We then visit all the neighbor nodes of that first node one by one
• Once all the neighbor nodes are visited, we then pick the neighbor nodes and start visiting their neighbor nodes
• While doing this we need to make sure we are not visiting an already visited node, and for this while visiting a node, we mark the node visited by capturing it in a map or similar data structure where we can refer in constant time whether a node is visited or not
• Once all the nodes are visited using above approach we have completed the bsf traversal for that graph

Java Code

    import java.io.*;
    import java.util.*;
    
    class GraphBFS{
    
        private HashSet visitedTracking = new HashSet();
        private LinkedList queue = new LinkedList();
    
        static class Node{
    
            private int id;
            LinkedList adjacent = new LinkedList();
    
            private Node(int id){
                this.id = id;
            }
    
        }
     
        //Function to add an edge into the graph
        public void addEdge(Node a, Node b)
        {
            a.adjacent.add(b);
            b.adjacent.add(a); 
        }
    
        public void traverseBFS(Node root){
            
            visitedTracking.add(root.id);
            System.out.println(root.id);
            queue.add(root); // Add to end of queue
            
            while (!queue.isEmpty()){
                
                Node r = queue.remove(); // Remove from front of queue
                
                for(Node child : r.adjacent) {
                    
                    if (!visitedTracking.contains(child.id)) {
                        visitedTracking.add(child.id);
                        System.out.println(child.id);
                        queue.add(child);
                    }
                }
            }
        }
    
        public static void main(String args[]){
    
            GraphBFS gS = new GraphBFS();
        
            Node a1 = new Node(1);
            Node a2 = new Node(2);
            Node a3 = new Node(3);
            Node a4 = new Node(4);
            Node a7 = new Node(7);
            Node a9 = new Node(9);
            Node a12 = new Node(12);
            Node a5 = new Node(5);
            Node a8 = new Node(8);
            Node a6 = new Node(6);
    
            gS.addEdge(a1,a9);
            gS.addEdge(a1,a3);
            gS.addEdge(a1,a4);
            gS.addEdge(a3,a7);
            gS.addEdge(a7,a2);
            //gS.addEdge(a2,a4);
            gS.addEdge(a2,a6);
            gS.addEdge(a4,a5);
            gS.addEdge(a4,a12);
            gS.addEdge(a6,a8);
    
            gS.traverseBFS(a9);
    
    
        }
   }

Output

9
1
3
4
7
5
12
2
6
8