대표적인 그래프 탐색 알고리즘

📌 차이점

📌 공통점

• 일반적인 BFS, DFS 시간 복잡도

  • 노드 수: V

  • 간선 수: E

  • 시간 복잡도: O(V + E)

📌 구현 원리

🔹 BFS

• 그림으로 보기 STEP 1: A노드 부터 탐색을 시작할 것. STEP 2: A노드를 Visited 리스트에 넣음. A노드에 인접한 B, C를 큐에 넣음. STEP 3: 큐의 맨 앞에 있는 B를 Visited 리스트에 넣음. B에 인접한 노드 D를 큐에 넣음. STEP 4: 큐의 맨 앞에 있는 C를 Visited 리스트에 넣음. C에 인접한 노드 F를 큐에 넣음. STEP 5: 큐의 맨 앞에 있는 D를 Visited 리스트에 넣음. D에 인접한 F는 이미 큐에 있으므로 넘어감. STEP 6: 큐의 맨 앞에 있는 F를 Visited 리스트에 넣음. 큐는 비어있게 되므로 탐색을 종료.
  

🔹 DFS

• Step 1: 스택에 시작 노드를 넣음.
• Step 2: 스택이 비어있으면 실행을 멈추고 False 반환.
• Step 3: 스택의 맨 위 노드가 찾고자 하는 노드라면 탐색을 종료하고 True 반환.
• Step 4: Step 3에서 스택의 맨 위 노드가 찾고자 하는 노드가 아니라면 해당 노드를 POP함. 스택에 들어온 적이 없는 POP한 노드의 모든 이웃 노드를 찾아서 순서대로 스택에 넣음.
• Step 5: Step 3로 돌아감.

• 그림으로 보기 STEP 1: A를 시작노드로 함. STEP 2: A에 인접한 B, C가 스택에 저장됨. STEP 3: 스택의 맨 위에 있는 C를 꺼내서 Visited 배열에 넣음. C의 인접한 노드인 D, F가 스택에 저장됨. STEP 4: 스택의 맨 위에 있는 F를 꺼내서 Visited 배열에 넣음. F에 인접한 노드인 D는 이미 Stack에 있으므로 넘어감. STEP 5: 스택의 맨 위에 있는 D를 꺼내서 Visited 배열에 넣음. D에 인접한 C, F는 Visited 배열에 있으며 B는 스택에 있으므로 넘어감. STEP 6: 스택의 맨 위에 있는 B를 꺼내서 Visited 배열에 넣음. 스택이 비어있으므로 탐색을 종료함.
  

📌 예제

• BFS 방식: A - B - C - D - G - H - I - E - F - J
• DFS 방식: A - B - D - E - F - C - G - H - I - J

🔹 코드

// 1️⃣ [자바스크립트로 그래프 표현하기]
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']
};

// 2️⃣ [BFS 구현]
const BFS = (graph, startNode) => {
  const 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"]

// 3️⃣ [DFS 구현]
const DFS = (graph, startNode) => {
  const visited = []; // 탐색을 마친 노드들
  let needVisit = []; // 탐색해야할 노드들

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

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

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

---

참고

• 잔재미코딩 - 깊이 우선 탐색 (DFS), 너비 우선 탐색 (BFS)
• 나무위키 - 깊이 우선 탐색, 너비 우선 탐색
• sangbooom - [JS] BFS, DFS
• covenant - DFS BFS란? 백준 문제추천