2022-01-21 자료구조/ BFS & DFS

그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들를 한 번씩 방문(탐색)하는 것이 목적!

 

정점 탐색 방법중 DFS와 BFS를 알아보자!

 

 

Depth-First Search : 깊이 우선 탐색

출처 https://developer-mac.tistory.com/64 

- 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

- 예를 들어 미로찾기 를 할때 계속 한 방향으로 쭉 가다가 막히면

 

다시 가까운 갈림길로 돌아와서 다른 방향으로 탐색하는 것

 

 

DFS 특징

 

1. 모든 노드를 방문하고자 할때 선택

 

2. 너비 우선 탐색보다 간단함

 

3. 검색 속도 자체는 너비 우선 탐색에 비해 느림

 

4. 스택 또는 재귀함수로 구현

 

5. 경로의 특징을 저장(스택)해둬야 하는 문제에 많이 쓰임 

 

 

 

 

Breadth-First Search : 너비 우선 탐색

 

출처 https://developer-mac.tistory.com/64 

 - 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 떄 아래로 이동

 

 루트 노드에서 시작해 인접한 노드를 먼저 탐색!

 

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 법!

 

BFS의 특징

 

1. 두 노드 사이의 최단 경로를 찾고 싶을 때 선택

 

2.  근데 만약 리프 노드에 원하는것이 있다면 최악의 경우 모든 경로를 다 살펴보아야 함.

 

3. 큐를 이용해서 구현

 

 

 

자바스크립트로 DFS / BFS 구현하기

 

자바스크립트로 그래프 표현하기

 

const graph = {
  1: [2, 5, 9],
  2: [1, 3],
  3: [2, 4],
  4: [3],
  5: [1, 6, 8],
  6: [5, 7],
  7: [6],
  8: [5],
  9: [1, 10],
  10: [9]
};

DFS 구현

- 자료구조 스택 1개와 큐 1개를 활용

 

- DFS는 이전 노드가 아니라 자기 자신과 연결되었던 노드들을 먼저 탐색하기 때문에 stack(경로 특징 저장)을 사용한다.

 

const graph = {
  1: [2, 5, 9],
  2: [1, 3],
  3: [2, 4],
  4: [3],
  5: [1, 6, 8],
  6: [5, 7],
  7: [6],
  8: [5],
  9: [1, 10],
  10: [9]
};


const dfs = (graph, startNode) => {
  let needVisitStack = []; // 탐색을 해야 할 노드들
  let visitedQueue = []; // 탐색을 마친 노드들

  needVisitStack.push(startNode); // 방문도장 꾹!

  // 탐색을 해야 할 노드가 남아 있다면
  while (needVisitStack.length !== 0) {
    const node = needVisitStack.pop(); // 맨뒤의 요소가 pop으로 리턴됨
    if (!visitedQueue.includes(node)) { // 만약 탐색을 마친 노드에 pop된 요소가 들어있지 않다면
      visitedQueue.push(node); // 탐색했다고 집어넣어주고
      needVisitStack = [...graph[node], ...needVisitStack]; // 탐색마친 요소들에 방금 탐색된 요소를 합쳐줌.
    }
  }

  return visitedQueue;

};
console.log(dfs(graph, 1)); // [1, 9, 5, 2, 10, 8, 6, 3, 7, 4]

 

 

 

 

• DFS와 BFS의 장단점은 또 무엇이 있을까요?

 

• 그래프가 굉장히 크다면 어떤 탐색 기법을 고려해야 할까요? DFS

 

• 반대로, 그래프의 규모가 작고, depth가 얕다면 어떤 탐색 기법을 고려해야 할까요?  BFS

 

 

참고 : https://devuna.tistory.com/32

https://ryusm.tistory.com/48

 

https://jun-choi-4928.medium.com/javascript%EB%A1%9C-%ED%8A%B8%EB%A6%AC-bfs-dfs-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-e96bcdadd1f3