[자료구조] BFS(Breadth-First Search)

그래프 탐색

• 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것.
• 그래프는 관계에 특화된 자료 구조로서 데이터가 서로 어떻게 연결되는지 쉽게 이해시켜 준다.
• 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) 원칙으로 탐색한다.

1. 그래프 내 아무 정점에서나 시작한다. 이 정점을 시작 정점이라 부른다.
2. 시작 정점을 해시 테이블에 추가해 방문했다고 표시한다.
3. 시작 정점을 큐에 추가한다.
4. 큐가 빌 때까지 실행하는 루프를 시작한다.
5. 루프 안에서 큐의 첫 번째 정점을 삭제한다. 이 정점을 현재 정점이라 부른다.
6. 현재 정점의 인접 정점을 순회한다.
7. 이미 방문한 인접 정점이면 무시한다.
8. 아직 방문하지 않은 인접 정점이면 해시 테이블에 추가해 방문했다고 표시한 후 큐에 추가한다.
9. 큐가 빌 때까지 루프(4단계부터)를 반복한다.

 

1. A를 시작 정점으로 삼는다. A에 방문했다고 표시하고 큐에 추가한다.
2. 큐에서 첫 정점을 삭제 해 현재 정점으로 만든다. 큐에 항목이 A뿐이니 현재 정점은 A다. 큐는 비어있다.
   • A의 인접 정점을 순회한다.
3. B로 넘어간다. B에 방문했다고 표시한 후 큐에 추가한다.
   • A의 인접 정점이 남아 있으므로 현재 정점은 여전히 A다. 하지만 B에 방문했다고 표시했고, 큐에도 들어가 있다.
4. C로 넘어가 C에 방문했다고 표시한 후 큐에 추가한다. (B - C)
5. D로 넘어가 D에 방문했다고 표시한 후 큐에 추가한다. (B - C - D)
6. E로 넘어가 E에 방문했다고 표시한 후 큐에 추가한다. (B - C - D - E)
7. A의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 B를 디큐해 현재 정점으로 만든다. (C - D - E)
   • B의 인접 정점을 순회한다.
8. A는 이미 방문했으니 무시한다.
9. F로 넘어가 F에 방문했다고 표시한 후 큐에 추가한다. (C - D - E - F)
10. B의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 C를 디큐해 현재 정점으로 만든다. (D - E - F)
    • C의 인접 정점을 순회한다.
11. A는 이미 방문했으니 무시한다.
12. H로 넘어가 H에 방문했다고 표시한 후 큐에 추가한다. (D - E - F - H)
13. C의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 D를 디큐해 현재 정점으로 만든다. (E - F - H)
    • D의 인접 정점을 순회한다.
14. A는 이미 방문했으니 무시한다.
15. E도 이미 방문했으니 무시한다.
16. G로 넘어가 G에 방문했다고 표시한 후 큐에 추가한다. (E - F - H - G)
17. D의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 E를 디큐해 현재 정점으로 만든다. (F - H - G)
    • E의 인접 정점을 순회한다.
18. A는 이미 방문했으니 무시한다.
19. D는 이미 방문했으니 무시한다.
20. E의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 F를 디큐해 현재 정점으로 만든다. (H - G)
    • F의 인접 정점을 순회한다.
21. B는 이미 방문했으니 무시한다.
22. H도 이미 방문했으니 무시한다.
23. F의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 H를 디큐해 현재 정점으로 만든다. (G)
    • H의 인접 정점을 순회한다.
24. F는 이미 방문했으니 무시한다.
25. C도 이미 방문했으니 무시한다.
26. H의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 G를 디큐해 현재 정점으로 만든다.
    • G의 인접 정점을 순회한다.
27. D는 이미 방문했으니 무시한다.
28. I로 넘어가 I에 방문했다고 표시한 후 큐에 추가한다.
29. G의 인접 정점을 모두 순회했으므로 큐의 첫 항목인 I를 디큐해 현재 정점으로 만든다.
30. 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

18장 그래프로 뭐든지 연결하기

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

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog