[JavaScript] DFS와 BFS에 대해서

오늘은 DFS와 BFS에 대해서 알아보았다. 

DFS와 BFS는 그래프를 순회하며 탐색하는 알고리즘으로 DFS는 깊이 우선 탐색, BFS는 너비 우선 탐색으로 DFS는 Depth-First Search BFS는 Breadth-First Search를 뜻한다.

그래프란 정점과 간선으로 이루어진 자료구조의 일종으로 그래프를 탐색한다는 것은 어느 특정한 정점을 시작으로 모든 정점을 방문하는 것을 뜻한다.

그래프 더 알아보기

[Data-Structure] Graph (그래프)

 

 

• DFS (Depth-First Search) 깊이 우선 탐색

깊이 우선 탐색 (DFS)는 루트 노드( 또는 어느 특정 노드)에서 시작하여 해당 분기를 모두 검색하고 다음 분기로 넘어가는 방식이다. 
모든 노드를 방문하고 싶을 때 이 알고리즘을 사용하며 너비 우선 탐색(BFS)에 비해 속도는 느리나 구현이 좀 더 간결하다.

재귀 구조를 가지며 자료구조 중 스택과 유사하다. 재귀 구조를 가지기 때문에 알고리즘을 구현할 때 어느 정점을 방문했는지 꼭 체크가 필요하다.
(넓게 찾기 전에 깊게 찾는다. 미로찾기와 비슷)

다음은 JavaScript코드를 통해 구현해보도록 하겠다. 
(유튜브에서 동빈나님의 알고리즘 강의를 보면서 공부했다.)

탐색할 그래프 예시

 

let check = []; // 방문점을 체크하기 위한 배열

// 배열안에 배열구조로 인접 정점을 담기
let stack = [[],[],[],[],[],[],[],[]]; // 스택을 이용한건 아니지만 스택처럼 사용하기 위해 stack으로 선언했다.

function dfsFunction (x){
  if(check[x]){ // 모든 정점을 체크하면 리턴
      return;
  }
  check[x] = true; // 방문 표시
  console.log(x); 

  for(let i=0; i<stack[x].length; i++){
    let y = stack[x][i]; // 인접 정점
    dfsFunction(y); // 재귀 구조로 순회
  }
}

// 1과 2연결 
stack[1].push(2);
stack[2].push(1);

// 1과 3연결
stack[1].push(3);
stack[3].push(1);

// 2와 3연결
stack[2].push(3);
stack[3].push(2);

// 2와 4연결
stack[2].push(4);
stack[4].push(2);

// 2와 5연결
stack[2].push(5);
stack[5].push(2);

// 3과 6연결
stack[3].push(6);
stack[6].push(3);

// 3과 7연결
stack[3].push(7);
stack[7].push(3);

// 4와 5연결
stack[4].push(5);
stack[5].push(4);

// 6과 7연결
stack[6].push(7);
stack[7].push(6);

dfsFunction(1); // 1 2 3 6 7 4 5

 

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

너비 우선 탐색(BFS)는 루트 노드( 또는 어느 특정 노드)에서 시작하여 인접 노드를 먼저 탐색하는 방식이다. 두 노드 사이의 최단 경로를 찾을 때 이 알고리즘을 사용하며 DFS보다 구현이 조금 어렵다.

선입 선출 방식으로 자료구조 중 큐와 유사하며 재귀 구조는 아니지만 어느 정점을 방문했는지 체크하지 않으면 무한 루프에 빠질 위험이 있다. 
(깊게 찾기 전에 넓게 찾는다. 최단 경로 찾기와 비슷 ) 

다음은 JavaScript코드를 통해 구현해보도록 하겠다. 
(유튜브에서 동빈나님의 알고리즘 강의를 보면서 공부했다.)

탐색할 그래프 예시

 

let check = []; // 방문점을 체크하기 위한 배열

// 배열안에 배열구조로 인접 정점을 담기
let arr = [[], [], [], [], [], [], [], []]; 

function bfsFunction(start) {
    let queue = []; // queue를 쓰진 않았으나 queue처럼 사용하겠다.
    queue.push(start);
    check[start] = true;

    while(queue.length > 0){ // queue안이 비어있지 않을 때까지 루프
        let x = queue[0]; // queue의 front -> 0번 인덱스
        queue.splice(0, 1); // queue의 pop -> 맨 앞 인덱스 제거
        console.log(x); 
        for(let i=0; i<arr[x].length; i++){ // 인접 정점 탐색
            let y = arr[x][i]; 
            if(!check[y]){ // 인접 정점을 방문하지 않았다면
                queue.push(y); // queue에 넣고
                check[y] = true; // 방문 체크
            }
        }
    }
}

// 1과 2연결 
arr[1].push(2);
arr[2].push(1);

// 1과 3연결
arr[1].push(3);
arr[3].push(1);

// 2와 3연결
arr[2].push(3);
arr[3].push(2);

// 2와 4연결
arr[2].push(4);
arr[4].push(2);

// 2와 5연결
arr[2].push(5);
arr[5].push(2);

// 3과 6연결
arr[3].push(6);
arr[6].push(3);

// 3과 7연결
arr[3].push(7);
arr[7].push(3);

// 4와 5연결
arr[4].push(5);
arr[5].push(4);

// 6과 7연결
arr[6].push(7);
arr[7].push(6);

bfsFunction(1); // 1 2 3 4 5 6 7

 

구현은 해보았지만 아직 활용에 있어서 어려움을 느껴 많은 관련 알고리즘 문제들을 풀면서 좀 더 공부해보아야겠다. 
척척 이용하기에는 나는 아직 부족한 것 같다.