그래프 탐색 알고리즘, BFS(Breadth First Search)

BFS(너비 우선 탐색)

그래프 혹은 트리에서 모든 노드를 한 번씩 탐색하기 위한 기본적인 방법

• 완전 탐색을 수행하기 위해 사용할 수 있는 방법 중 하나
• (모든 간선의 길이가 동일할 때) 최단 거리를 탐색하기 위한 목적으로 사용 가능
• 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미
• 대표적인 그래프 탐색 알고리즘 중 하나
• 큐 자료 구조 이용(DFS-스택, BFS-큐)

 

큐 구현

class Queue {
    constructor() {
        this.queue = {};
        this.headIndex = 0;
        this.tailIndex = 0;
    }
    enqueue = (value) => {
        this.queue[this.tailIndex++] = value;
    };
    dequeue = () => {
        const item = this.queue[this.headIndex];
        delete this.queue[this.headIndex];
        this.headIndex++;
        return item;
    };
    peek = () => this.item[this.headIndex];
    getLength = () => this.tailIndex - this.headIndex;
}

const queue = new Queue();

queue.enqueue(5);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(7);
queue.dequeue();
queue.enqueue(1);
queue.enqueue(4);
queue.dequeue();

while (queue.getLength() != 0) {
    console.log(queue.dequeue());
}

 

그래프 표현

인접 리스트

0
1	2, 3
2	1, 5
3	1, 4, 5
4	3, 5
5	2, 3, 4

 

 

 

기본 동작 방식

1. 시작 노드를 큐에 넣고 [방문 처리]
2. 큐에서 원소를 꺼내어 방문하지 않은 인접 노드가 있는지 확인
   있다면, 방문하지 않은 인접 노드를 큐에 삽입하고 [방문 처리]
3. 2번 과정을 더 이상 반복할 수 없을 때까지 반복

[예시]

1. 시작 노드 A를 큐에 넣고 방문 처리

2. 큐에서 A를 꺼내어 인접한 노드 중에서 방문하지 않은 노드인 B, C, D 방문

3. 큐에서 B를 꺼냈지만 인접한 노드 중에서 방문하지 않은 노드가 없으므로 무시

4. 큐에서 C를 꺼내어 인접한 노드 중에서 방문하지 않은 노드인 E, F 방문

5. 큐에서 D를 꺼내어 인접한 노드 중에서 방문하지 않은 노드인 G를 방문

6. 큐에서 E를 꺼내어 인접한 노드 중에서 방문하지 않은 노드인 H를 방문

7. 큐에서 F를 꺼냈지만 인접한 노드 중에서 방문하지 않은 노드가 없으므로 무시

8. 큐에서 G를 꺼냈지만 인접한 노드 중에서 방문하지 않은 노드가 없으므로 무시

9. 큐에서 H를 꺼냈지만 인접한 노드 중에서 방문하지 않은 노드가 없으므로 무시

10. 큐가 비었으므로 탐색 종료

 

BFS 사용 예시

• 간선의 비용이 동일한 상황에서 최단 거리 문제를 해결하는 경우
  - BFS는 다익스트라 최단 경로 알고리즘과 유사한 특징 존재
  - 다익스트라는 간선의 비용이 서로 다를 수 있을 때 사용
  - 다익스트라 알고리즘은 일반 큐 대신에 우선순위 큐 사용
  - 다익스트라는 특정 노드에 대하여 [최단 거리]값이 갱신될 수 있음(더 짧은 경로를 찾는 경우)
• 완전 탐색을 위해 사용한 DFS 솔루션이 메모리/시간 초과를 받아 BFS로 재시도하는 경우
  - DFS와 BFS 모두 그래프 탐색 목적으로 사용할 수 있으나, 구현이 익숙하다면 BFS 추천
• 코딩테스트에서 DFS로 해결할 수 있는 문제는 BFS로도 해결할 수 있는 경우가 많음
  - DFS는 일반적으로 최단 거리 문제 해결 X

 

BFS 코드 예시

function bfs(graph, start, visited) {
    queue = new Queue();
    queue.enqueue(start);
    visited[start] = true; // 현재 노드를 방문 처리
    while (queue.getLength() != 0) {
        const v = queue.dequeue();
        console.log(v);
        for (const i of graph[v]) {
            if (!visited[i]) {
                queue.enqueue(i);
                visited[i] = true;
            }
        }
    }
}

const graph = [[], [2, 3, 4], [1], [1, 5, 6], [1, 7], [3, 8], [3], [4], [5]];
const visited = Array(9).fill(false);
bfs(graph, 1, visited);