[99일차]그래프 너비우선탐색법 (BFS)

그래프 너비 우선 탐색법

너비 우선탐색은 깊이탐색과 함께 등장하는 탐색방법이다.
깊이우선탐색은 갈수있는데까지 깊이 갔다오는걸 반복한다면,
너비우선 탐색은 갈수있는 길목을 한단계씩 차례대로 가보는거다.

ex)깊이우선탐색

깊이우선탐색설명

ex)너비우선탐색

보다시피 깊이우선탐색은 일단 깊이 찌르는것과 달리
갈수있는 길목을 한칸씩만 가고 다음길목으로 가서 또 갈길을 체크한다.

갈수있는 길목을 순차적으로 살피게 해줄 도구가 필요한데,
바로 큐 자료구조를 이용하는것이다.

이해를 돕기위해 숫자 순서를 섞는다.

bfs도 순서를 나열하면 간단하다.

1. 현재 위치한곳에 방문기록을 표시한다.

2. 디큐한다.

3. 갈 수 있는 길목중에 방문한적이 없고 큐에 없는 노드를 인큐한다.

4. 큐에있는 노드들을 bfs(재귀)한다.

start에 방문기록 표시

디큐한다

현재 큐에 아무것도 없다.

start에서 갈수있는 곳은 3, 5, 1 셋다 방문기록전무, 큐에도 암것도없다

그래서 큐에 3, 5, 1 이 추가된걸 볼수있다.

큐를순회하면서 시작지점을 큐의 각요소로 잡고 BFS를 한다.

3을 BFS한다 -> 현재위치한 3에 방문기록을 표시한다.

디큐한다.

갈수있는 길목인 4를 인큐한다.

큐를순회하면서 시작지점을 큐의 각요소로 잡고 BFS를 한다.

5를 BFS한다 -> 현재 위치한 5에 방문기록을 표시한다.

디큐한다.

갈수있는 길목이 있긴하지만, 큐에 이미있다.

큐를순회하면서 시작지점을 큐의 각요소로 잡고 BFS를 한다.

1을 BFS한다 -> 현재 위치한 1에 방문기록을 표시한다.

디큐한다.

더이상 갈 곳이없고 큐에 넣을것도 없다.

큐를순회하면서 시작지점을 큐의 각요소로 잡고 BFS를 한다.

4를 BFS한다 -> 현재 위치한 4에 방문기록을 표시한다.

디큐한다.

갈수있는 길목인 2를 인큐한다.

큐를순회하면서 시작지점을 큐의 각요소로 잡고 BFS를 한다.

2를 BFS한다 -> 현재 위치한 2에 방문기록을 표시한다.

디큐한다.

함수종료

javascript 코드로 구현해보자.

const graph = {//2차원배열의 1번째인덱스는 방문여부이다.
  start: [[3, 5, 1], false],
  3: [[4, 'start'], false],
  5: [[4, 1, 'start'], false],
  1: [['start', 5], false],
  4: [[2, 5, 3], false],
  2: [[4], false]
}
const que = [];
function BFS(begin){
  //현재노드에 방문기록을 남긴다.
  graph[begin][1] = true;
  console.log(`${begin} 에 방문함`);
  //디큐한다.
  que.shift();
  //방문한적이 없고, 큐에 없는 노드를 인큐한다.
  for(let el of graph[begin][0]){
    if(!graph[el][1] && que.indexOf(el) === -1){
      que.push(el)
    }
  }
  //큐를 순회하며 각요소를 BFS한다
  for(let el of que){
    BFS(el)
  }
}

위 예제와 같은 인접리스트 배열로 그래프를 대강 만들어봤다.
지금 중점은 탐색이니 그래프의 여러기능을 구현한 포스트는 여기