[알고리즘 공부] 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)

---

너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)

너비우선탐색(Breadth-First Search, BFS)는 하나의 요소를 방문하고 그 요소에 인접한 모든 요소를 우선 방문하는 방식
깊이우선탐색(Depth-First Search, DFS)는 트리의 한 요소(노드)와 다음 수준(level)의 자식 노드를 따라가는 방향으로 탐색하는 방식
길 찾기 등에 주로 쓰이는 알고리즘
: 단순 길찾기에는 BFS/DFS만 써도 무방하지만,
장애물이 존재하는 등 추가적 연산이 필요할 때 완전탐색 병용하기도 함.

BFS 알고리즘 구현 (Js)

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "G", "H", "I"],
  D: ["B", "E", "F"],
  E: ["D"],
  F: ["D"],
  G: ["C"],
  H: ["C"],
  I: ["C", "J"],
  J: ["I"]
};

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

  needVisit.push(startNode); // 노드 탐색 시작

  while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
    const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
    if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
      visited.push(node); 
      needVisit = [...needVisit, ...graph[node]];
    }
  }
  return visited;
};

console.log(bfs(graph, "A"));
// ["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]

DFS 알고리즘구현(Js)

BFS 구조는 두 개의 큐를 활용하는데, DFS는 한 개의 스택과 한 개의 큐를 사용한다는 차이가 있다.
BFS 구조는 이전 노드와 연결된 노드들을 먼저 탐색해야 하기 때문에 queue를 사용.
DFS는 이전 노드가 아니라 자기 자신과 연결되었던 노드들 먼저 탐색하기 때문에 stack을 사용.

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "G", "H", "I"],
  D: ["B", "E", "F"],
  E: ["D"],
  F: ["D"],
  G: ["C"],
  H: ["C"],
  I: ["C", "J"],
  J: ["I"],
};

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

  needVisitStack.push(startNode);

  // 탐색을 해야 할 노드가 남아 있다면
  while (needVisitStack.length !== 0) {
    const node = needVisitStack.pop();
    if (!visitedQueue.includes(node)) {
      visitedQueue.push(node);
      needVisitStack = [...needVisitStack, ...graph[node]];
    }
  }

  return visitedQueue;
};

console.log(dfs(graph, "A"));

// ["A", "C", "I", "J", "H", "G", "B", "D", "F", "E"]

시간복잡도

DFS와 BFS는 모두 노드 수+간선 수만큼의 복잡도를 지닌다. 즉, O(n)

출처
출처2