[data structure] BFS / DFS

Hyebin·2021년 4월 23일

Data structure / Algorithm

목록 보기

9/19

그래프 데이터는 배열처럼 정렬되어 있지 않아 원하는 자료를 찾을 때까지 모두 탐색해야 한다.
그래프 탐색은 하나의 정점을 시작으로 모든 정점들을 한 번씩 방문(탐색)하는 것이 핵심이다. 또한 어떤 정점을 방문했는지 방문 여부를 검사 해야 한다. 탐색은 여러가지 방법으로 할 수 있는데 그 중 DFS와 BFS를 많이 사용한다.

DFS/BFS 둘 다 어떤 순서로 탐색하느냐 다를 뿐 모든 자료를 하나씩 확인하는 것은 같다.

BTS(Breadth First Search)

너비 우선 탐색(BFS)
시작 정점에서 가장 가까운 정점을 먼저 탐색하고, 멀리 떨어져 있는 정점은 나중에 탐색하는 방법이다.
말 그대로 깊이가 아닌 너비를 우선 탐색하는 방법이다.

너비 우선 탐색은 아래 그림의 숫자 순서대로 정점을 방문하여 탐색한다.

주로 두 정점 사이의 최단 경로나 임의의 경로를 찾고 싶을 때 사용한다.
예를 들어, 한국에서 미국으로 가는 최단 경로를 구한다 가정하면
한국에서 가장 가까운 정점인 중국, 터키부터 탐색을 한다. 해당 정점에는 미국이 없기 때문에 다음으로 가까운 정점인 일본, 인도, 미국을 방문하게 되고, 미국을 찾았으므로 탐색을 종료한다.

만약, DFS로 탐색을 한다면 최악의 경우에는 모든 경로를 다 살펴봐야하는 경우가 생길 수 있다.

BFS 특징

직관적이지 않은 면이 있다.
BFS는 주로 queue(큐)를 사용해 구현한다.
BFS는 층별로 방문하여 탐색하기 때문에 선입선출 원리를 가진 queue를 이용하면 차례로 저장 후 꺼내서 탐색하기 유용하다.
그래프의 규모가 작고, depth가 얕으면 BFS 탐색을 고려해야한다.

BFS 알고리즘

인접 행렬일 때 정점간에 간선이 존재하는지 너비 우선 탐색으로 탐색한다.

function getDirections(matrix, from, to) {  //matrix : 인접 행렬
  
  let queue = [from]; //시작점을 queue에 넣어야 이게 맞는지 아닌지 확인할 수 있도록 넣어준다. 
  let enqueue = (n) => queue.push(n);
  let dequeue = () => queue.shift();

  //한번 간 곳은 가지 않는다. -> 방문한 곳을 표시해준다.
  let isVisted = new Array(matrix.length).fill(false);
  isVisted[from] = true;  //첫 정점 방문 여부 표시

 
  //이제 queue의 길이가 0일 때까지 순회를 한다. == 탐색해야할 정점이 없을 때까지
  while(queue.length > 0) {
    //큐에서 하나 뽑음
    let curVer = dequeue();	//queue에서 현재 vertex를 꺼낸다.
    
    //현재 정점이 목적지라면 true를 반환한다. 
    if(curVer === to) return true;
    
    //해당 정점의 간선들을 확인한다. 
    for(let i=0; i<matrix[curVer].length; i++) {
      if(matrix[curVer][i] && !isVisted[i]) {
        enqueue(i); //다음 정점을 큐에 넣는다.
        isVisted[i] = true; //해당 정점 방문 표시를 한다. 
      }
    }
  } 
  return false;
}