[JAVA] BFS - 너비 우선 탐색

//

//

너비 우선 탐색(BFS)

• BFS : Breath First Search

• 시작 정점으로부터 인접한 정점들을 모두 차례로 방문한 후 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례로 방문한다.

• 가까운 정점들을 먼저 방문하고 멀리 있는 정점들은 나중에 방문하는 순회 방법

• 인접한 정점들에 대해 차례로 다시 탐색을 반복해야하므로 큐를 사용한다.

1. 시작 정점 v를 결정하여 방문한다.

2. 정점 v에 인접한 정점들 중에서 방문하지 않은 인접 정점이 있으면 차례로 방문하면서 큐에 enQueue한다.

   방문하지 않은 인접 정점이 없으면 큐를 deQueue하여 구한 정점을 v로 다시 설정하고 2번을 반복한다.

3. 큐가 공백이 될 때까지 반복한다.

  package BFS;
  ​
  public class ArrayQueue {
      private int front;
      private int rear;
      private int queueSize;
      private int queue[];
      
      public ArrayQueue(int queueSize) {
          this.front = -1;
          this.rear = -1;
          this.queueSize = queueSize;
          this.queue = new int[queueSize];
      }
  ​
      public boolean isEmpty(){
          return front == rear;
      }
      
      public boolean isFull(){
          return rear == queueSize-1;
      }
      
      public void enQueue(int item){
          if(isFull()){
              System.out.println("Full");
          }
          else{
              queue[++rear] = item;
          }
      }
      
      public int deQueue(){
          if(isEmpty()){
              System.out.println("Empty");
              return -1;
          }
          else{
              return queue[++front];
          }
      }
      
      public int peek(){
          if(isEmpty()){
              System.out.println("Empty");
              return -1;
          }
          else{
              return queue[front+1];
          }
      }
  ​
  }

  package BFS;
  ​
  public class BFS {
      private int totalV;
      private int matrix[][];
      private boolean visited[];
      
      public BFS(int totalV) {
          this.totalV = totalV;
          matrix = new int[totalV][totalV];
          visited = new boolean[totalV];
      }
      
      public void insertEdge(int v1, int v2){
          if(v1 > totalV || v2 > totalV){
              System.out.print("error");
          }
          else{
              matrix[v1][v2] = 1;
              matrix[v2][v1] = 1;
          }
      }
      
      public void startBFS(int v){
          ArrayQueue queue = new ArrayQueue(totalV*totalV);
          int next = -1;
          
          visited[v] = true;
          System.out.printf("%c", v+65);
          queue.enQueue(v);
          
          while(!queue.isEmpty()){
              int v1 = queue.deQueue();
              while((next=getUnvisitedVertex(v1))!= -1 ){
                  visited[next] = true;
                  System.out.printf("%c", next+65);
                  queue.enQueue(next);
              }
          }
      }
      
      public int getUnvisitedVertex(int v){
          for(int i = 0; i < totalV; i++){
              if(matrix[v][i] == 1 && visited[i]==false){
                  return i;
              }
          }
          return -1;
      }
      
  }

  package BFS;
  import java.util.*;
  import java.io.*;
  ​
  public class BFSMain {
  ​
      public static void main(String[] args) {
          // TODO Auto-generated method stub
          Scanner input = new Scanner(System.in);
          
          System.out.print("정점의 개수 : ");
          int totalV = input.nextInt();
          
          System.out.print("간선의 개수 : ");
          int totalE = input.nextInt();
          
          System.out.print("시작 정점 : ");
          int startV = input.nextInt();
          
          BFS bfs = new BFS(totalV);
          
          System.out.println("간선 입력");
          int v1, v2;
          for(int i = 0; i < totalE; i++){
              v1 = input.nextInt();
              v2 = input.nextInt();
              bfs.insertEdge(v1, v2);
          }
  ​
          bfs.startBFS(startV);
      }
  ​
  }