BFS (Breadth-First Search)

BFS

BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.

BFS는 최단거리, 또는 최소횟수를 구하라는 문제에서 사용된다.

BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

 

BFS 동작 과정

0) 아래의 그래프를 번호가 낮은 인접 노드부터 순서대로 방문한다.

1) 노드 '1'을 큐에 삽입하고 방문한다.

2) 노드 '1'을 꺼낸 뒤, 노드 '1'가 방문하지 않은 인접 노드인 노드 '2', '3', '8'을 큐에 삽입하고 방문

3) 노드 '2'를 꺼낸 뒤, 노드 '2'가 방문하지 않은 인접 노드인 노드 '7'을 큐에 삽입하고 방문

4) 노드 '3'을 꺼낸 뒤, 노드 '3'이 방문하지 않은 인접 노드인 노드 '4', '5'를 큐에 삽입하고 방문

5) 노드 '8'를 꺼낸 뒤, 방문하지 않은 인접 노드가 없으므로 무시

6) 위 과정을 모든 노드를 방문할 때까지 반복한다.

 

 

BFS 구현 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
 
    // 방문 여부
    public static boolean[] visited = new boolean[9];
 
    // 그래프
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
 
    // DFS 함수 정의
    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.println(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);
    }
}