Question

Write a function which performs Breadth First Search on the given graph. Also write in which order the nodes are visited.

40 20 50 70 10 30 60

Class Node {

public int value;

public Node[] neighbors;

public boolean visited;

public Node(int num) {

neighbors = new Node[5];

visited = False;

data = num

}

}

Answer 1

-------------------------------------------------------------------------------------------------------------

// Node.java File

public class Node {
   public int value;
   public Node[] neighbors;
   public int neighborSize;
   public boolean visited;
   public Node(int num) {
       neighbors = new Node[5];
       visited = false;
       value = num;
       neighborSize = 0;
   }
  
   // self added function
   // The below function attaches a particular node as a neighbor
  
   public void addNeighbor(Node x) {
       neighbors[neighborSize++] = x;
   }
}

// BFS.java File

import java.util.LinkedList;
import java.util.Queue;
import java.util.HashMap;

public class BFS {

   public static void main(String[] args) {
       // make 7 Nodes corresponding to the figure in the question
       Node nA = new Node(40);
       Node nB = new Node(10);
       Node nC = new Node(20);
       Node nD = new Node(30);
       Node nE = new Node(50);
       Node nF = new Node(60);
       Node nG = new Node(70);
       //add neighbors for nA
       nA.addNeighbor(nB);
       nA.addNeighbor(nC);
       //add neighbors for nB
       nB.addNeighbor(nD);
       //add neighbors for nC
       nC.addNeighbor(nB);
       nC.addNeighbor(nD);
       nC.addNeighbor(nE);
       nC.addNeighbor(nF);
       //add neighbors for nD
       nD.addNeighbor(nF);
       //add neighbors for nE
       nE.addNeighbor(nG);
       //add neighbors for nF
       nF.addNeighbor(nF);
       Queue<Node> q = new LinkedList<>();
       //The below Hashmap is for checking a vertex with a particular Integer value has been visited or not
       HashMap<Integer,Boolean> map = new HashMap<>();
       q.add(nA);
       map.put(nA.value, true);
       while(!q.isEmpty()) {
           Node top = q.poll();
           System.out.println("Currently at node whose value is "+top.value);
           //check the neighbors of top
           for(int i=0;i<top.neighborSize;i++) {
               if(!map.containsKey(top.neighbors[i].value)) {
                   q.add(top.neighbors[i]);
                   map.put(top.neighbors[i].value, true);
               }
           }
       }
   }
  
  
}

-------------------------------------------------------------------------------------------------------------

// ScreenShot of Output

Currently at node whose value is 40 Currently at node whose value is 10 Currently at node whose value is 20 Currently at node whose value is 30 Currently at node whose value is 50 Currently at node whose value is 60 Currently at node whose value is 70

-------------------------------------------------------------------------------------------------------------