[Algorithm] BFS (너비 우선 탐색. Breadth-first search)

그래프와 완전탐색

자료구조에서 말하는 그래프는 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한다.

직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있고, 간접적인 관계가 있는 경우 몇 개의 점과 선에 걸쳐 이어진다.

하나의 점을 정점(vertex)라고 표현하고 하나의 선은 간선(edge)라고 표현한다.

그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적이고 이를 완전탐색이라 부르기도 한다. 모든 정점 탐색 방법에는 여러 가지가 있다. 그 중 BFS가 있다.

 

---

 

위 그림과 같은 그래프가 있다고 가정하겠다. 이 그래프를 어떤 방법으로 완전 탐색하냐에 따라 방문하는 순서가 달라진다.

 

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

루트 노드 혹은 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법

방문 순서부터 말하면 A-B-C-D-E-F-G-H-I-J-K 이다.

BFS는 방문한 노드와 같은 레벨의 노드를 먼저 탐색한 후 그 아래 노드로 넘어간다. 전체적으로 보면 한 레벨씩 가로로 넓게 탐색이 진행된다.

큐를 통해 구현한다. (해당 노드의 주변부터 탐색해야하기 때문)

• 최소 비용(즉, 모든 곳을 탐색하는 것보다 최소 비용이 우선일 때)에 적합

Ex) 큐를 이용한 구현

const bfs = (graph, startNode) => {
  let visited = []; // 탐색한 노드를 담기 위한 배열 생성
  let queue = []; // 탐색을 위한 큐 배열 생성
  
  queue.push(startNode); // 탐색 시작
  
  while(queue.length > 0){ // 큐가 비워질 때까지 반복
    let node = queue.shift(); // 큐의 첫번째 노드를 뽑는다
    if(!visited.includes(node.value)){ // 그 노드를 탐색한 적이 없다면!!
      visited.push(node); // 탐색 배열에 추가
      queue = [...queue, ...graph[node]]; // 해당 노드와 같은 레벨에 있는 노드들을 담는다
    }
  }
  
  return visited;
}

시간 복잡도

• 인접 행렬 : O(V^2)
• 인접 리스트 : O(V+E)