[알고리즘] BFS (Breadth-First Search) : 너비 우선 탐색 알고리즘이란?

너비 우선 탐색 BFS(Breadth-First Search)

트리나 그래프를 탐색하는 기법 중 하나로, 시작 노드로부터 자식 노드들을 순서대로 탐색하면서 너비를 우선으로 탐색하는 알고리즘이다. 

 

BFS는 완전탐색 알고리즘에 속하며, 가중치가 없는 그래프에서 같은 거리에 있는 모든 노드를 탐색한 후, 다음 거리의 노드를 탐색하기 시작하는 방식으로 진행된다. 따라서, 가중치 없는 그래프에서 최단거리를 구하는 문제에 활용될 수 있다.

 

BFS는 Queue를 활용해 다음 방문할 노드를 추적하며, While 반복문을 통하여 문제를 해결한다.

---

BFS 탐색 과정

BFS 알고리즘의 기본 단계는 다음과 같이 요약할 수 있다.

 

1. 시작 노드에서 시작하고 대기열(Queue)에 넣는다.
2. 대기열에서 노드를 제거하고 검사한다.(poll)
3. 대기열에서 빼낸 노드가 목표 노드이면 검색이 완료된다.
4. 그렇지 않은 경우 큐에서 빼낸 노드의 방문하지 않은 자식을 큐에 넣는다.(offer)
5. 대기열이 비어 있거나 목표 노드를 찾을 때까지 2-4단계를 반복한다.

 

 

BFS의 탐색과정을 이해하기 위해 아래의 애니메이션을 보자.

Queue에 담긴 상태는        연두색, Queue에서 제거된 상태는        초록색으로 이해하면 된다.

 

먼저 시작 노드를 Queue에 넣고 시작한다.

 

Queue에는 현재 0만 담겨 있는 상태이므로, 0을 꺼내고 자식을 Queue에 넣는다.

 

왼쪽부터 넣게 되면 Queue에는 1과 2가 들어가게 된다.

다음은 Queue에서 poll()을 통해 1을 꺼내고 1의 자식들을 Queue에 다시 넣는다.

 

이때 Queue 에는 2가 미리 들어가 있는 상태로 3 , 4가 들어가게 되므로

 

다음 poll()을 할 때, 2가 나오게 된다.

 

다음은 Queue에서 2를 꺼내고 자식들을 넣는다.

 

마찬가지로 남은 노드들도 3 , 4 , 5... 순서대로 반복해 주면 BFS의 완전탐색이 완료된다.

 

---

BFS의 장단점

 

BFS의 장점:

 

1. 간단하고 이해하기 쉬운 편이다.
2. 연결된 구성 요소에서 모든 노드를 찾는 데 사용할 수 있다.

 

BFS의 단점:

1. 많은 메모리가 필요하므로 큰 그래프에는 적합하지 않다.
2. 그래프를 순회할 때 가중치를 고려하지 않기 때문에 가중치 간선이 있는 그래프에는 적합하지 않다.
3. 다음 깊이로 이동하기 전에 노드의 모든 하위 항목을 탐색하기 때문에 분기 계수가 큰 그래프에는 비효율적이다.
4. 다음 깊이로 이동하기 전에 현재 깊이의 모든 노드를 방문하기 때문에 노드 수가 많은 그래프에는 비효율적이다.
5. 목표 노드가 시작 노드에서 멀리 떨어져 있으면 다음 깊이로 이동하기 전에 주어진 깊이의 모든 노드를 탐색하기 때문에 비효율적이다.

 

BFS는 메모리를 많이 사용하고, 노드 수가 많은 그래프에는 적합하지 않으며, 가중 간선이 있는 그래프에서는 제대로 작동하지 않는다는 점을 알아두는 것이 중요하다.

 

 

---

BFS의 구현방법

그래프를 선언해 주었을 때, 경로를 찍어주는 예제이다.

아래의 주석 부분에 그래프를 선언해 주고 bfs 함수를 호출하여 탐색을 시작한다.

 

0번 시작 노드를 Queue에 넣고 while문을 Queue가 비워질 때까지 반복하며 탐색을 거친다.

 

또한, 선형 구조를 갖게 되어 중복이 발생할 경우를 대비해 boolean 배열 visited를 선언하여 방문처리를 해주는 것으로 구현한다.

 

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

public class example {
    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        // initialize graph here

        bfs(0, graph);
    }

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

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

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

            for (int next : graph.get(current)) {
                if (!visited[next]) {
                    queue.add(next);
                    visited[next] = true;
                }
            }
        }
    }
}

 

---

BFS 예시문제

 

추후에 추가할 예정이다.