[알고리즘] BFS (Java)

 

BFS란?

 

Breadth First Search, 너비 우선 탐색

가까운 노드부터 탐색하는 알고리즘

 

동작 과정

 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

* 방문처리: 큐에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 방문 처리를 함으로써 각 노드를 한 번씩만 처리할 수 있다.

 

자세히 살펴보기

 

일반적으로 인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리한다.

* 방문 처리된 노드는 회색으로, 큐에서 꺼내 현재 처리하는 노드는 하늘색으로 표현했다.

 

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

 

2. 큐에서 노드 '1'을 꺼내고 방문하지 않은 인접 노드 '2'. '3', '8'을 모두 큐에 삽입하고 방문 처리를 한다.

 

3. 큐에서 노드 ‘2’를 꺼내고 방문하지 않은 인접 노드 ‘7’을 큐에 삽입하고 방문 처리를 한다.

 

4. 큐에서 노드 ‘3’을 꺼내고 방문하지 않은 인접 노드 ‘4’와 ‘5’를 모두 큐에 삽입하고 방문 처리를 한다.

 

5. 큐에서 노드 ‘8’을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시한다.

 

6. 큐에서 노드 '7’을 꺼내고 방문하지 않은 인접 노드 ‘6’을 큐에 삽입하고 방문 처리를 한다.

 

7. 남아 있는 노드에 방문하지 않은 인접 노드가 없다.

따라서 모든 노드를 차례대로 꺼내면 최종적으로 다음과 같다.

 

노드 탐색 순서

1 - 2 - 3 - 8  -7 - 4 - 5 - 6

 

특징

 

1. 큐 자료구조에 기초한다. -> 구현이 간단하다.

2. Queue 클래스를 사용하는 것이 좋다.

3. 데이터의 개수가 N개인 경우 O(N)의 시간복잡도를 가진다.

4. 일반적인 경우에 실제 수행 시간은 DFS보다 적다.

 

구현 코드

 

public class BFS {
    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph;

    // BFS 함수 정의
    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.print(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) {
        // 그래프 정의
        graph = new ArrayList<>() {{
            add(new ArrayList<>(List.of()));
            add(new ArrayList<>(List.of(2, 3, 8)));
            add(new ArrayList<>(List.of(1, 7)));
            add(new ArrayList<>(List.of(1, 4, 5)));
            add(new ArrayList<>(List.of(3, 5)));
            add(new ArrayList<>(List.of(3, 4)));
            add(new ArrayList<>(List.of(7)));
            add(new ArrayList<>(List.of(2, 6, 8)));
            add(new ArrayList<>(List.of(1, 7)));
        }};

        // 정의된 BFS 함수 호출
        bfs(1);
    }

 

출력 결과

1 2 3 8 7 4 5 6

 

 

Reference

이것이 코딩테스트다 - 나동빈