BFS

BFS란 ? (너비 우선 탐색)

그래프 혹은 트리에서 모든 노드를 한번씩 탐색하기 위한 기본적인 방법.

완전 탐색을 수행하기 위해 사용할 수 있는 방법중 하나.

(모든 간선길이가 동일할 때)최단거리를 탐색하기 위한 목적으로 사용할 수 있음.

queue 자료구조를 사용.

기본적으로

DFS - stack
BFS - queue

기본동작 방식

BFS

• 시작노드를 큐에 넣고 [방문처리]
• 큐에서 원소를 하나씩 꺼내면서 방문하지 않은 인접된 노드가 있는지 확인.
  있으면 방문하지 않은 인접노드를 큐에 모두 삽입하고 방문처리.
  while문으로 false가 될때까지 반복.

// 그래프를 인접 리스트로 표현하는 객체
const graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F', 'G'],
  D: ['B'],
  E: ['B'],
  F: ['C'],
  G: ['C'],
};

// 방문한 노드를 저장하기 위한 Set 객체 생성
const visited = new Set();

// BFS 함수 정의
function bfs(startNode) {
  // 시작 노드를 큐에 추가하고 방문 처리
  const queue = [startNode];
  visited.add(startNode);

  // 큐가 비어있을 때까지 반복
  while (queue.length > 0) {
    // 큐의 맨 앞 노드를 꺼내고 인접 노드들을 확인
    const currentNode = queue.shift();
    console.log(currentNode);

    for (const neighbor of graph[currentNode]) {
      // 방문하지 않은 인접 노드라면 큐에 추가하고 방문 처리
      if (!visited.has(neighbor)) {
        queue.push(neighbor);
        visited.add(neighbor);
      }
    }
  }
}

// 시작 노드를 'A'로 설정하여 BFS 호출
bfs('A');

DFS 와 BFS 를 봤는데 개념적인 부분보다 문제를 많이 접해봐야 할 것 같다.

github에 알고리즘 적어두고 보기