그래프를 탐색하는 방법은 여러가지가 있습니다. 그 중에 대표적인 두 가지 방법을 소개하려고 합니다.
바로 BFS와 DFS입니다. 두 방법 모두 모든 자료를 하나씩 확인하는 공통점을 가지고 있지만, 탐색 순서에 차이가 있습니다.

---

DFS

• Depth First Search(깊이 우선 탐색)
• stack을 이용해 그래프를 탐색합니다.

1. 시작 노드를 stack에 넣습니다.
2. stack 안의 노드를 꺼내 탐색할 때 방문처리를 하고, 해당 노드의 인접 노드들을 stack에 넣습니다.
3. stack이 비워질 때까지 2번 과정을 반복합니다.

DFS 예제

// 위 그림에 해당하는 그래프(인접 리스트로 구현)
const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F", "G"],
  D: ["B", "H", "I"],
  E: ["J"],
  F: ["C"],
  G: ["C"],
  H: ["D"],
  I: ["D"],
  J: ["E"]
}

// dfs 함수
const dfs = function (graph, startNode) {
  let visited = []; // 방문 처리 된 노드들
  let stack = []; // 탐색할 노드들을 담을 stack

  stack.push(startNode); // 시작 노드를 스택에 삽입

  while (stack.length !== 0) { // 탐색을 해야 할 노드가 남아 있다면
    let node = stack.pop(); // 스택에서 탐색할 노드를 꺼냄
    
    if (!visited.includes(node)) { // 노드를 방문하지 않았다면
      visited.push(node); // 노드 방문 처리
      stack = stack.concat(graph[node].reverse()); // 스택에 노드가 인접한 노드들을 추가, A 다음에 B를 탐색할 것이므로 노드의 인접 노드들을 reverse()해서 스택에 담음
    }
  }

  return visited;
};

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

---

BFS

• Breadth First Search(너비 우선 탐색)
• queue를 이용해 그래프를 탐색합니다.

1. 시작 노드를 queue에 넣습니다.
2. queue 안의 노드를 꺼내 탐색할 때 방문처리를 하고, 해당 노드의 인접 노드들을 queue에 넣습니다.
3. queue가 비워질 때까지 2번 과정을 반복합니다.

BFS 예제

// 위 그림에 해당하는 그래프(인접 리스트로 구현)
const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F", "G"],
  D: ["B", "H", "I"],
  E: ["J"],
  F: ["C"],
  G: ["C"],
  H: ["D"],
  I: ["D"],
  J: ["E"]
};

// bfs 함수
const bfs = function (graph, startNode) {
  let visited = []; // 방문 처리 된 노드들
  let queue = []; // 탐색할 노드들을 담을 queue
  
  queue.push(startNode); // 시작 노드를 큐에 삽입
  
  while (queue.length !== 0) { // 탐색을 해야 할 노드가 남아 있다면
    let node = queue.shift(); // 큐에서 탐색할 노드를 꺼냄
    
    if (!visited.includes(node)) { // 노드를 방문하지 않았다면
      visited.push(node); // 노드 방문 처리
      queue = queue.concat(graph[node]); // 큐에 노드가 인접한 노드들을 추가
    }
  }
  return visited; // 방문 처리된 노드들 리턴
}

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

주의!
이전에 방문했던 노드는 다시 방문하지 않습니다. 방문처리가 되었다면, 그 다음 노드를 탐색합니다.