BFS | 자바

(이코테 2021 강의 몰아보기) 3. DFS & BFS)를 보면서 작성한 글입니다.

BFS란

BFS는 이전에 포스팅 했던 DFS와 함께대표적인 그래프 탐색 알고리즘 중 하나입니다. BFS라는 말에서도 알 수 있듯이 너비(Breadth)를 우선적으로 탐색합니다.

너비를 우선적으로 탐색한다는 말은 그래프에서 가까운 노드부터 우선적으로 탐색하는 것이며, 아래 그림과 같습니다.

번호가 낮은 인접 노드부터 DFS로 위 그래프를 탐색하면 1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6 순으로 탐색하게 됩니다.

BFS 구현

BFS는 Queue 자료구조를 이용해서 구현합니다.

import java.util.*;

class Main {
  public static boolean[] visited = new boolean[9];
  public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

  public static void bfs(int start) {
    Queue<Integer> q = new LinkedList<>();
    q.offer(start);
    visited[start] = true;

    while(!q.isEmpty()) {
      int x = q.poll();
      System.out.print(x + " ");

      for(int i = 0; i < graph.get(x).size(); i++) {
        int y = graph.get(x).get(i);
        if(!visited[y]) {
          q.offer(y);
          visited[y] = true;
        }
      }
    }
  }

  public static void main(String[] args) {
    // 그래프 초기화
    for (int i = 0; i < 9; i++) {
      graph.add(new ArrayList<Integer>());
  }

  // 노드 1에 연결된 노드 정보 저장 
  graph.get(1).add(2);
  graph.get(1).add(3);
  graph.get(1).add(8);

  // 노드 2에 연결된 노드 정보 저장 
  graph.get(2).add(1);
  graph.get(2).add(7);

  // 노드 3에 연결된 노드 정보 저장 
  graph.get(3).add(1);
  graph.get(3).add(4);
  graph.get(3).add(5);

  // 노드 4에 연결된 노드 정보 저장 
  graph.get(4).add(3);
  graph.get(4).add(5);

  // 노드 5에 연결된 노드 정보 저장 
  graph.get(5).add(3);
  graph.get(5).add(4);

  // 노드 6에 연결된 노드 정보 저장 
  graph.get(6).add(7);

  // 노드 7에 연결된 노드 정보 저장
  graph.get(7).add(2);
  graph.get(7).add(6);
  graph.get(7).add(8);

  // 노드 8에 연결된 노드 정보 저장 
  graph.get(8).add(1);
  graph.get(8).add(7);

  bfs(1);
  }
}

아래와 같은 로직으로 BFS를 코드를 작성했습니다.

1. 시작 노드를 큐에 삽입하고 방문 처리합니다.
2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에서 방문하지 않은 모든 노드를 큐에 넣고 방문 처리합니다.

BFS 관련 문제

• 내가 푼 문제