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

너비 우선 탐색?

어떤 노드를 방문하여 확인한 후, 목표한 노드가 아니면 그 노드와 연결된 정점들 중에서 우선 순위가 동일한 다른 노드를 찾고 그 순위에 없으면 그 다음 순위 노드를 차례대로 찾는 방법

즉, 깊게 탐색하기 전 넓게 탐색하는 방법이다.

 

* 두 노드의 최단 경로를 찾고 싶은 경우에 이 방법을 선택

* BFS보다 복잡하다.

 

구현 방법

큐(Queue)를 사용한다.

 

문제

다음과 같이 입력이 주어질 때 너비 우선 탐색을 한 순서대로 노드의 인덱스를 공백 구분으로 출력하시오.

데이터
graph = {'E': ['D', 'A'],
         'F': ['D'],
         'A': ['E', 'C', 'B'],
         'B': ['A'],
         'C': ['A'],
         'D': ['E','F']}

출력
E D A F C B

문제 풀이

 

가까운 정점을 먼저 방문하고, 먼 정점은 나중에 방문하게 되며 다음과 같이 거리와 노드를 나눌 수 있다.

자, 이제 아래와 같이 큐를 통해서 탐색을 시작한다.

E가 먼저 큐에 쌓이게 되고, 실행되며 Current로 이동한다.

이 때, D와 A가 큐에 쌓이게 된다.

(E는 방문경로로 이동)

큐는 FIFO(First In First Out) 방식으로, D가 실행되며 Current로 이동한다.

이 때, 큐에는 F가 쌓이게 된다.

(D는 방문경로로 이동한다.)

 

 

스택과 다르게, 큐에서는 먼저 쌓인 A가 실행되며 Current로 이동한다.

이 때, C와 B가(A 이후에 실행되는 경로 노드) 큐에 쌓이게 된다.

(A는 방문경로로 이동한다.)

 

이러한 방식으로 너비 우선 탐색을 실행하게 되며 결과적으로는 다음과 같은 방문경로가 나온다.

 

코드 풀이

function dfs(graph, start) {
  let visited = []
  let stack = [start]

  // stack의 값이 다 빠져나갈 때 종료
  while (stack.length !== 0) {
    let n = stack.shift()
    // 방문했던 상위 노드 제외 로직
    if (!visited.includes(n)) {
      visited.push(n)
      let sub = graph[n].filter(x => !visited.includes(x))
      for (let i of sub) {
        stack.push(i)
      }
    }
  }

  return visited;
}

console.log(dfs(graph, 'E'))

 

[참고]

인프런, 제주코딩베이스캠프 Code Festival: JavaScript 100제: 모든 이미지와 풀이는 해당 강의 자료를 참고했습니다.

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html