자료구조
[자료구조] BFS(Breadth-First Search)
Voyage_dev
2024. 3. 31. 14:28
그래프 탐색
- 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것.
- 그래프는 관계에 특화된 자료 구조로서 데이터가 서로 어떻게 연결되는지 쉽게 이해시켜 준다.
- SNS 예시로는 한 사람은 한 노드로, 사람 간 친구 관계는 선으로 표현한다. → 방금 가입해 친구가 0명인 회원이 있다면 노드는 존재하지만 연결된 친구가 한 명도 없는 상태이다.
기초 그래프 구현
const friends = new Map([
["Alice", ["Bob", "Diana", "Fred"]],
["Bob", ["Alice", "Cynthia", "Diana"]],
["Cynthia", ["Bob"]],
["Diana", ["Alice", "Bob", "Fred"]],
["Elise", ["Fred"]],
["Fred", ["Alice", "Diana", "Elise"]],
]);
friends.get("Alice"); // [ 'Bob', 'Diana', 'Fred' ]
- 기초 해시 테이블로 기본적인 그래프를 표현해 보자
- 해시 테이블의 모든 키 값은 한 단계로 찾을 수 있으므로 앨리스의 친구를 O(1)에 찾을 수 있다.
BFS(Breadth-First Search)
- 흔히 BFS로 부르는 너비 우선 탐색은 말 그대로 깊은 탐색이 아니라 넓게 그래프를 탐색하는 방법 중 하나로 재귀를 쓰지 않고 큐로 문제를 해결한다.
- 루트 노드에서 시작해서 인접한 노드를 먼저 탐색한다. 즉, 가까운 노드로 갔다가 멀리 떨어져 있는 노드를 나중에 방문하는 순회 방법이다.
사용하는 경우
- 두 노드 사이의 최단 경로를 찾고 싶을 때
- 임의의 경로를 찾고 싶을 때
너비 우선 탐색(BFS)의 과정
큐(Queue)를 사용해 선입선출(FIFO) 원칙으로 탐색한다.
- 그래프 내 아무 정점에서나 시작한다. 이 정점을 시작 정점이라 부른다.
- 시작 정점을 해시 테이블에 추가해 방문했다고 표시한다.
- 시작 정점을 큐에 추가한다.
- 큐가 빌 때까지 실행하는 루프를 시작한다.
- 루프 안에서 큐의 첫 번째 정점을 삭제한다. 이 정점을 현재 정점이라 부른다.
- 현재 정점의 인접 정점을 순회한다.
- 이미 방문한 인접 정점이면 무시한다.
- 아직 방문하지 않은 인접 정점이면 해시 테이블에 추가해 방문했다고 표시한 후 큐에 추가한다.
- 큐가 빌 때까지 루프(4단계부터)를 반복한다.
- A를 시작 정점으로 삼는다. A에 방문했다고 표시하고 큐에 추가한다.
- 큐에서 첫 정점을 삭제 해 현재 정점으로 만든다. 큐에 항목이 A뿐이니 현재 정점은 A다. 큐는 비어있다.
- A의 인접 정점을 순회한다.
- B로 넘어간다. B에 방문했다고 표시한 후 큐에 추가한다.
- A의 인접 정점이 남아 있으므로 현재 정점은 여전히 A다. 하지만 B에 방문했다고 표시했고, 큐에도 들어가 있다.
- C로 넘어가 C에 방문했다고 표시한 후 큐에 추가한다. (B - C)
- D로 넘어가 D에 방문했다고 표시한 후 큐에 추가한다. (B - C - D)
- E로 넘어가 E에 방문했다고 표시한 후 큐에 추가한다. (B - C - D - E)
- A의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 B를 디큐해 현재 정점으로 만든다. (C - D - E)
- B의 인접 정점을 순회한다.
- A는 이미 방문했으니 무시한다.
- F로 넘어가 F에 방문했다고 표시한 후 큐에 추가한다. (C - D - E - F)
- B의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 C를 디큐해 현재 정점으로 만든다. (D - E - F)
- C의 인접 정점을 순회한다.
- A는 이미 방문했으니 무시한다.
- H로 넘어가 H에 방문했다고 표시한 후 큐에 추가한다. (D - E - F - H)
- C의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 D를 디큐해 현재 정점으로 만든다. (E - F - H)
- D의 인접 정점을 순회한다.
- A는 이미 방문했으니 무시한다.
- E도 이미 방문했으니 무시한다.
- G로 넘어가 G에 방문했다고 표시한 후 큐에 추가한다. (E - F - H - G)
- D의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 E를 디큐해 현재 정점으로 만든다. (F - H - G)
- E의 인접 정점을 순회한다.
- A는 이미 방문했으니 무시한다.
- D는 이미 방문했으니 무시한다.
- E의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 F를 디큐해 현재 정점으로 만든다. (H - G)
- F의 인접 정점을 순회한다.
- B는 이미 방문했으니 무시한다.
- H도 이미 방문했으니 무시한다.
- F의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 H를 디큐해 현재 정점으로 만든다. (G)
- H의 인접 정점을 순회한다.
- F는 이미 방문했으니 무시한다.
- C도 이미 방문했으니 무시한다.
- H의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 G를 디큐해 현재 정점으로 만든다.
- G의 인접 정점을 순회한다.
- D는 이미 방문했으니 무시한다.
- I로 넘어가 I에 방문했다고 표시한 후 큐에 추가한다.
- G의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 I를 디큐해 현재 정점으로 만든다.
- I의 인접 정점은 G 하나인데 G는 이미 방문했다.
- 큐에 더 이상 삭제할 항목이 없으므로 모두 순회했다.
코드 구현
// 너비 우선 탐색 메서드
bfsTraverse(startingVertex) {
const queue = new Queue();
const visitedVertices = new Map();
visitedVertices.set(startingVertex.value, true);
queue.enqueue(startingVertex);
// 큐가 빌 때까지 실행한다
while (queue.read()) {
const currentVertex = queue.dequeue();
console.log(currentVertex.value);
for (let adjacentVertex of currentVertex.adjacentVertices) {
if (!visitedVertices.get(adjacentVertex.value)) {
visitedVertices.set(adjacentVertex.value, true);
queue.enqueue(adjacentVertex);
}
}
}
}
// 큐 클래스
class Queue {
constructor() {
this.data = [];
}
enqueue(element) {
this.data.push(element);
}
dequeue() {
return this.data.shift();
}
read() {
return this.data[0];
}
}
- 알고리즘에 필요한 큐를 생성하고, 방문했던 정점을 기록할 해시 테이블도 생성한다.
- startingVertex에 방문했다고 표시한 후 큐에 추가한다.
- 큐가 빌 때까지 실행하는 while 문을 실행한다.
- 큐에서 첫 항목을 dequeue해 현재 정점으로 만들고, 현재 정점의 모든 인접 정점을 for 문으로 순회한다.
- 방문하지 않은 정점에 대해 해시 테이블에 추가해 방문했다고 표시한 후 큐에 추가한다.
BFS vs DFS
- 너비 우선 탐색은 시작 정점과 가장 가까운 정점을 모두 순회한 후 멀어지고 깊이 우선 탐색은 즉시 시작 정점에서 최대한 멀어진다.
- 시나리오에 따라 깊이 우선 탐색이 빠르고, 다른 시나리오에선 너비 우선 탐색이 더 빠를 수 있다.
- SNS에서 친구의 친구가 아닌, 진짜 친구만을 찾는다면 시작 정점과 가장 가까운 정점을 바로 찾는 너비 우선 방식이 빠를 것.
- 증손주를 찾는다면 모든 자식과 손주를 순회하는 것이 아니라 바로 증손주에 도달하는 깊이 우선 탐색이 더 빠르다.
⇒ 항상 그래프를 탐색하는 동안 시작 정점 가까이 있고 싶다면 너비 우선 탐색 , 시작 정점과 빨리 멀어져야 한다면 깊이 우선 탐색
Reference