[java] 너비 우선 탐색 알고리즘 (BFS)

04 Dec 2023

java

너비 우선 탐색 알고리즘 (BFS)은 그래프를 탐색하는 알고리즘 중 하나입니다. BFS는 그래프의 정점들을 너비 방향으로 탐색하기 때문에 너비 우선 탐색이라고 부릅니다. 이 알고리즘은 최단 경로 문제를 해결하는 데에도 자주 사용됩니다.

알고리즘의 동작 원리

BFS 알고리즘은 다음과 같은 순서로 동작합니다:

시작 정점을 큐에 넣고 방문 표시를 합니다.
큐에서 정점을 하나씩 꺼내고, 이웃한 정점들을 방문하지 않았다면 큐에 넣고 방문 표시를 합니다.
큐가 빌 때까지 반복합니다.

이 과정을 통해 시작 정점에서부터 차례대로 가까운 정점부터 탐색하며, 모든 정점을 방문하게 됩니다.

예제 코드

다음은 BFS 알고리즘의 예제 코드입니다. 다음 코드는 인접 리스트를 사용하여 그래프를 표현하고, 큐를 사용하여 탐색합니다.

import java.util.*;

public class BFS {

    public static void bfs(List<List<Integer>> graph, int start) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[graph.size()];

        queue.offer(start);
        visited[start] = true;

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

            List<Integer> neighbors = graph.get(node);
            for (int neighbor : neighbors) {
                if (!visited[neighbor]) {
                    queue.offer(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> graph = new ArrayList<>();

        graph.add(Arrays.asList(1, 2));
        graph.add(Arrays.asList(0, 3, 4));
        graph.add(Arrays.asList(0, 5, 6));
        graph.add(Arrays.asList(1));
        graph.add(Arrays.asList(1, 7));
        graph.add(Arrays.asList(2));
        graph.add(Arrays.asList(2));
        graph.add(Arrays.asList(4));

        bfs(graph, 0);
    }
}

위의 코드는 다음과 같은 그래프를 탐색합니다:

0---1---3
|   |   
|   4---7
|
2---5---6

결론

너비 우선 탐색 알고리즘(BFS)은 그래프 탐색에 유용하게 사용될 수 있는 알고리즘입니다. 이를 활용하여 최단 경로 문제를 해결하거나, 그래프의 연결 상태를 확인하는 등 다양한 작업에 활용할 수 있습니다.

위에서 제시한 예제 코드를 참고하여 실제로 동작하는 BFS 알고리즘을 구현해보세요. 그래프 탐색에 있어서 너비 우선 탐색은 매우 유용한 도구입니다.