Algorithum] DFS vs BFS

Graph 탐색

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.

🌼 DFS(Depth First Search)

DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다.

DFS는 Stack(FILO) 형태의 자료구조를 사용하기 때문에 Recursion 사용하면 간결하게 코드 작성 가능하다는 장점이 있다. (단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 사용에 주의해야 한다.)

• 모든 재귀함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.

• 재귀 함수를 사용하지 않을 경우, 아래의 메서드를 사용하여 Stack 구조를 구현할 수도 있다.

  삽입: Array.push()
  삭제: Array.pop()

// Example. n!을 재귀함수를 사용하여 구현하시오. (단,0!, 1!은 1이다.)

const num = 5;

function solution(num) {
  if (num <= 1) {
    return 1
  } else {
    return num * solution(num - 1);
  }
};

solution(num);  // 120

🌼 BFS(Breadth First Serach)

BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다.

BFS는 Queue(FIFO) 형태의 자료구조를 사용한다.

  삽입: Array.push();
  삭제: Array.shift();

출처: YOUTUBE-동빈나