[java] 자바를 이용한 BFS 알고리즘

15 Dec 2023

java

이 게시물에서는 자바를 사용하여 너비 우선 탐색(BFS) 알고리즘을 구현하는 방법을 알아볼 것입니다.

BFS 알고리즘

BFS는 그래프나 트리와 같은 자료 구조에서 가까운 노드부터 탐색하여 최단 경로를 찾는 알고리즘입니다. 이는 큐(queue) 자료 구조를 사용하여 구현할 수 있습니다.

아래는 BFS 알고리즘의 자바 예제 코드입니다.

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

public class BFS {
    public void bfs(int[][] graph, int start) {
        boolean[] visited = new boolean[graph.length];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;

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

            for (int i = 0; i < graph.length; i++) {
                if (graph[node][i] == 1 && !visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        int[][] graph = {{0, 1, 1, 0},
                         {1, 0, 0, 1},
                         {1, 0, 0, 1},
                         {0, 1, 1, 0}};
        
        BFS bfs = new BFS();
        bfs.bfs(graph, 0);
    }
}

위 코드는 이차원 배열을 그래프로 나타내고 BFS 알고리즘을 활용하여 그래프를 탐색하는 예제를 보여줍니다.

마치며

이번 포스트에서는 자바를 사용하여 BFS 알고리즘을 구현하는 법을 알아보았습니다. 이를 응용하여 다양한 그래프 탐색 문제를 해결할 수 있습니다.

참고 문헌:

Sedgewick, R., & Wayne, K. (2011). Algorithms. Addison-Wesley.