너비 우선 탐색(BFS) - JAVA

너비 우선 탐색

너비 우선 탐색은 영어로 BFS (Breadth First Search) 라 표현하며, 그래프를 탐색하는데 너비를 우선으로 하여 탐색한다는 뜻이다. BFS 탐색을 위해선 스택을 사용한 DFS와 달리 큐 라는 자료구조가 필요하다. 큐를 사용한 BFS 탐색 방법은 아래와 같다.

BFS 순서

1. 시작노드를 큐에 담는다.
2. 큐에 넣은 값을 빼며 방문하지 않은 인접한 노드 전부를 큐에 저장한다.
3. 큐가 empty 가 될때까지 2번 과정을 반복한다.
4. 큐가 비게되면 탐색이 종료된다.

예시

예시로 그래프가 아래와 같을 경우 (무방향 그래프, 숫자가 낮은 노드부터 탐색)

BFS로 탐색을 진행한다면 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 9 -> 8 순 으로 탐색을 진행하게 된다.

코드

DFS 탐색을 코드로 구현할 땐 재귀를 사용하여 구현하거나 스택을 사용하여 구현한다.

package pjh5365.graph;

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

public class BFS {

    static boolean[] visited = new boolean[10];  // 9번 노드까지 있으므로 0빼고 사용하기 위해 10개 필요
    static int[][] graph = {    // 배열별로 자신이 가르키는 노드를 가짐 (양방향 그래프임)
            {}, // 0번 사용하지 않음
            {2, 3, 4},  // 1번 노드가 가르키는 노드는 2, 3, 4
            {1},  // 2번 노드가 가르키는 노드는 1
            {1, 5}, // 3번 노드가 가르키는 노드는 1, 5
            {1}, // 4번 노드가 가르키는 노드는 1
            {3, 6, 7},  // 5번 노드가 가르키는 노드는 3, 6, 7
            {5, 9},    // 6번 노드가 가르키는 노드는 5, 9
            {5}, // 7번 노드가 가르키는 노드는 5
            {9},  // 8번 노드가 가르키는 노드는 9
            {6, 8}  // 9번 노드가 가르키는 노드는 6, 8
    };

    public static void main(String[] args) {
        System.out.println("\nBFS 탐색");
        bfs(1);
        System.out.println();
    }

    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();  // 사용할 큐 선언

        queue.add(start);   // 큐에 시작점 입력
        visited[start] = true;  // 방문표시
        System.out.print(start + " -> "); // 방문확인을 위한 출력
        while(!queue.isEmpty()) {  // 큐가 빌때까지 반복
            int now = queue.poll(); // 큐의 값 빼서 가져오기
            for(int i = 0; i < graph[now].length; i++) {   // 가져온 노드의 인접노드 전부를 탐색
                if(!visited[graph[now][i]]) { // 방문되지 않았다면
                    queue.add(graph[now][i]); // 큐에 삽입
                    visited[graph[now][i]] = true;    // 방문 표시
                    System.out.print(graph[now][i] + " -> ");   // 방문확인을 위한 출력
                }
            }
        }
    }
}

결과는 아래와 같이 나온다.