알고리즘_깊이우선탐색(DFS),너비우선탐색(BFS) / JS

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

먼저 제일 밑으로 내려갔다가 더 내려갈 곳이 없으면 옆으로 이동하는 순서

1번	5번	9번
2번	6번	10번
3번	7번	11번
4번	8번	12번

깊이 우선 탐색은 스택 또는 재귀함수로 구현한다.

출처 : [자료구조 알고리즘]Graph 검색 DFS, BFS 구현 in Java_엔지니어 대한만국

위에 사진에서 볼 수 있는 것이 DFS로 방식으로 출력된 순서이다.
스택은 바닥이 막힌 원형통으로 가장 위에 있는 것만 꺼낼 수 있는 후입선출방식이라고 생각하면 편하다

재귀함수를 이용한 코드로 DFS를 구현해 봤다.

let dfs = function (node) {
  let result = [node.value]

  node.children.forEach((n) => {
    result = result.concat(dfs(n))
  })
  return result
};

// Node라는 클래스를 생성
let Node = function (value) {
  this.value = value;
  this.children = [];
};

// 자식 노드에 인스턴스(객체)를 넣는 방식
// Node.prototype 은 객체를 표현
Node.prototype.addChild = function (child) {
  this.children.push(child);
  return child;
};

node.children을 *forEach를 이용해 탐색한 다음 *concat을 이용해 배열을 합쳐준다

//예시

let root = new Node(1);
let rootChild1 = root.addChild(new Node(2));
let rootChild2 = root.addChild(new Node(3));
let leaf1 = rootChild1.addChild(new Node(4));
let leaf2 = rootChild1.addChild(new Node(5));
let output = dfs(root);

이렇게 예시를 넣는다면 결과 값(output)은 [1,2,4,5,3]이 출력되게 된다

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

옆으로 먼저 이동한 뒤 더 이상 옆으로 갈 수 없을 때 밑으로 내려가는 순서

1번	2번	3번
4번	5번	6번
7번	8번	9번
10번	11번	12번

BFS는 큐를 이용해서 구현한다.

출처 : [자료구조 알고리즘]Graph 검색 DFS, BFS 구현 in Java_엔지니어 대한만국

BFS의 출력 순서이다.
큐는 양쪽이 뚫려 있는 원형 통으로 먼저 들어온 것이 먼저 출력되는 선입선출 방식이라고 생각하면 편하다.

코드 구현은 아래와 같다.

BFS도 클래스를 만들고 객체를 넣는 방식은 DFS와 같이 진행한다.

let bfs = function (node) {

  let queue = [node];
  const values = [];
  while (queue.length > 0) {
    const head = queue[0];
    //console.log(head)
    queue = queue.slice(1);
	//console.log(queue)
    values.push(head.value);

    head.children.forEach((child) => queue.push(child));
  }
  return values;
};

let Node = function (value) {
  this.value = value;
  this.children = [];
};

Node.prototype.addChild = function (child) {
  this.children.push(child);
  return child;
};

이번엔 head와 queue의 값이 어떻게 변화 하는지 알아보기 위해 console.log 를 찍어봤다

queue의 길이가 *push로 추가되고 *slice로 없어지는 것을 알 수 있다

이렇게 value값을 추가해주고 자식 노드를 queue에 추가시키는 방식으로 진행된다

//예시

let root = new Node(1);
let rootChild1 = root.addChild(new Node(2));
let rootChild2 = root.addChild(new Node(3));
let leaf1 = rootChild1.addChild(new Node(4));
let leaf2 = rootChild1.addChild(new Node(5));
let output = dfs(root);

output은 [1,2,3,4,5]가 된다

---

* forEach() for문과 비슷하게 반복문을 해주는 메서드로 각 배열 요소에 대해 한번 씩 callback 함수 실행
map함수와도 비슷하다

* concat() 인자로 주어진 배열이나 값들을 기존 배열에 합쳐서 새 배열 반환

* push() 배열의 끝에 하나 이상의 요소를 추가하고 배열의 새로운 길이 반환

* slice() start부터 end까지 얕은 복사본으로 새로운 배열 객체로 반환
위의 코드처럼 slice(1)로 작성하면 1번째 인덱스부터 끝까지를 의미한다

---

참고

https://devuna.tistory.com/32

https://youtu.be/_hxFgg7TLZQ