Advertisement
iNoobAvicena

Breadth First Search (BFS)

Dec 18th, 2020
752
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.ArrayList;
  2. import java.util.LinkedList;
  3. import java.util.List;
  4. import java.util.Queue;
  5. import java.util.Scanner;
  6.  
  7. class Node {
  8.  
  9.     int data;
  10.     boolean visited;
  11.     List<Node> neighbours;
  12.  
  13.     Node(int data) {
  14.         this.data = data;
  15.         this.neighbours = new ArrayList<>();
  16.  
  17.     }
  18.  
  19.     public void addneighbours(Node neighbourNode) {
  20.         this.neighbours.add(neighbourNode);
  21.     }
  22.  
  23.     public List<Node> getNeighbours() {
  24.         return neighbours;
  25.     }
  26.  
  27.     public void setNeighbours(List<Node> neighbours) {
  28.         this.neighbours = neighbours;
  29.     }
  30. }
  31.  
  32. class BreadthFirstSearch {
  33.  
  34.     private Queue<Node> queue;
  35.     static ArrayList<Node> nodes = new ArrayList<Node>();
  36.  
  37.     public BreadthFirstSearch() {
  38.         queue = new LinkedList<Node>();
  39.     }
  40.  
  41.  
  42.     public void bfs(Node node) {
  43.         //Lengkapi
  44.         queue.add(node);
  45.         node.visited = true;
  46.         while (!queue.isEmpty()){
  47.             Node isi = queue.remove();
  48.             System.out.print(isi.data + " ");
  49.             List<Node> neighbours = isi.getNeighbours();
  50.             int i = 0;
  51.             while (i < neighbours.size()){
  52.                 Node check = neighbours.get(i);
  53.                 if(check != null && !check.visited){
  54.                     queue.add(check);
  55.                     check.visited = true;
  56.                 }
  57.                 i++;
  58.             }
  59.         }
  60.     }
  61.  
  62.     public void bfs(Node[] nodes, int mulai){
  63.         for (int i = 0; i < nodes.length; i++) {
  64.             if (nodes[i].data == mulai) {
  65.                 bfs(nodes[i]);
  66.                 break;
  67.             }
  68.         }
  69.         System.out.println("");
  70.     }
  71.  
  72. }
  73.  
  74. public class BFSMain {
  75.  
  76.     public static void main(String arg[]) {
  77.         Scanner in = new Scanner(System.in);
  78.         BreadthFirstSearch BFS = new BreadthFirstSearch();
  79.         String input[] = in.nextLine().split(" ");
  80.         Node[] nodes = new Node[input.length];
  81.         for (int i = 0; i < input.length; i++) {
  82.             nodes[i] = new Node(Integer.parseInt(input[i]));
  83.         }
  84.         int n = in.nextInt();
  85.         for (int i = 0; i < n; i++) {
  86.             int A = in.nextInt();
  87.             int B = in.nextInt();
  88.             nodes = addneighbour(nodes, A, B);
  89.         }
  90.         int mulai = in.nextInt();
  91.         BFS.bfs(nodes, mulai);
  92.     }
  93.     public static Node[] addneighbour(Node[] nodes, int A, int B){
  94.         for (int i = 0; i < nodes.length; i++) {
  95.             if (nodes[i].data==A) {
  96.                 for (int j = 0; j < nodes.length; j++) {
  97.                     if (nodes[j].data==B) {
  98.                         nodes[i].addneighbours(nodes[j]);
  99.                     }
  100.                 }
  101.             }
  102.         }
  103.         return nodes;
  104.     }
  105. }
Advertisement
RAW Paste Data Copied
Advertisement