[Algorithm] 효율적인 그래프 탐색: 자바로 구현한 BFS 알아보기 (2/2)

개요

본 글에서는 그래프 탐색 알고리즘의 종류인 너비 우선 탐색:BFS(Breadth-First Search) 알고리즘에 대해서 정리해보고자 합니다.

 

BFS의 대한 내용은 아래의 포스팅에서 확인 가능합니다.

 

[Algorithm] 효율적인 그래프 탐색: 자바로 구현한 DFS 알아보기 (1/2)

 

BFS (너비 우선 탐색) 이란❓

BFS(Breadth-First Search)는 그래프 탐색 알고리즘의 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가장 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘입니다.

 

BFS는 다음과 같은 방식으로 동작합니다.

BFS 특징

1. Queue(큐) 활용

• FIFO(First In First Out) 구조인 큐를 사용하여 탐색을 진행합니다.

2. 최단 경로 보장

• 가중치가 없는 그래프에서 시작 노드에서 목표 노드까지의 최단 경로를 찾을 수 있습니다.

3. 레벨 단위 탐색

• 시작 노드에서 가까운 노드부터 탐색하며, 같은 레벨의 노드를 먼저 방문합니다.

 

BFS (너비 우선 탐색) 동작 과정 살펴보기

위 그림에서 알 수 있듯이 시작 노드인 1부터 탐색을 시작하여, BFS 알고리즘은 가까운 노드부터 차례대로 방문합니다.

 

Step 1

 

시작 노드인 1을 큐에 삽입하고 방문 처리를 합니다.

---

Step 2

큐에 있는 값(1)을 꺼내고, 방문하지 않았다면 인접 노드를 큐에 삽입합니다.

• 인접 노드 : 2, 3, 4
• 현재 큐: [2, 3, 4]

---

Step 3

 

큐에 있는 값(2)을 꺼내고, 방문하지 않았다면 인접 노드를 큐에 삽입합니다.

• 인접 노드 : 5
• 현재 큐: [3, 4, 5]

---

Step 4

 

큐에 있는 값(3)을 꺼내고, 방문하지 않았다면 인접 노드를 큐에 삽입합니다.

• 인접 노드 : 6, 7
• 현재 큐: [4, 5, 6, 7]

---

Step 5

 

큐에 있는 값(4)을 꺼내고, 방문하지 않았다면 인접 노드를 큐에 삽입합니다.

• 인접 노드 : 8
• 현재 큐: [5, 6, 7, 8]

---

Step 6

 

큐에 있는 값(5)을 꺼내고, 방문하지 않았다면 인접 노드를 큐에 삽입합니다.

• 인접 노드 : 9
• 현재 큐: [6, 7, 8, 9]

---

Step 7

 

큐에 있는 값(6)을 꺼내고, 방문하지 않았다면 인접 노드를 큐에 삽입합니다.

• 인접 노드 : 10
• 현재 큐: [7, 8, 9, 10]

---

Step 8

 

이제 모든 노드를 방문했기 때문에, 큐에서 값을 차례대로 꺼내면서 BFS를 마무리합니다.

• 7을 꺼냅니다 → 현재 큐: [8, 9, 10]

그러면 위와 같이 최종적으로 다음과 같은 순서로 노드를 방문하게 됩니다:

• 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10

 

BFS (너비 우선 탐색) Java 코드

public class Main {
    public static void main(String[] args) {
        // 그래프를 2차원 배열로 표현
        // 인덱스와 노드를 일치시키기 위해 0번 인덱스는 비워둠
        int[][] graph = {
            {},             // 0번 인덱스는 사용하지 않음
            {2, 3, 4},     // 1번 노드의 인접 노드
            {5},           // 2번 노드의 인접 노드
            {6, 7},        // 3번 노드의 인접 노드
            {8},           // 4번 노드의 인접 노드
            {9},           // 5번 노드의 인접 노드
            {10},          // 6번 노드의 인접 노드
            {},            // 7번 노드의 인접 노드
            {},            // 8번 노드의 인접 노드
            {},            // 9번 노드의 인접 노드
            {}            // 10번 노드의 인접 노드
        };

        boolean[] visit = new boolean[11]; // 0~10번 노드

        System.out.println(bfs(1, graph, visit));
        // 예상 결과값: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 ->
    }

    static String bfs(int start, int[][] graph, boolean[] visit) {
        StringBuilder sb = new StringBuilder();
        Queue<Integer> queue = new LinkedList<Integer>();

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

        while (!queue.isEmpty()) {
            int node = queue.poll();
            sb.append(node + " -> ");
            
            for (int i = 0; i < graph[node].length; i++) {
                int temp = graph[node][i];
                if (!visit[temp]) {
                    visit[temp] = true;
                    queue.offer(temp);
                }
            }
        }
        return sb.toString();
    }
}

 

출력 결과

 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10

 

위와 같이 시작노드(위 코드에서는 1)를 시작으로 인접한 노드를 방문하고, 방문하지 않았다면 큐에 넣습니다.

 

그리고 해당 노드를 방문처리를 해주고, 큐가 빌 때까지 이 과정을 반복하면서 모든 노드를 너비 우선으로 탐색합니다.

 

이렇게 BFS는 현재 노드와 가까운 노드들을 우선적으로 탐색하면서, 레벨 단위로 그래프를 탐색하는 특징을 가집니다. 최단 경로를 찾는 문제나 레벨 단위의 탐색이 필요한 문제에서 유용하게 사용됩니다.