너비 우선 탐색(BFS)

• 그래프의 모든 꼭지점 또는 트리 데이터 구조의 모든 노드를 너비 우선 순서로 방문하는 그래프 순회 알고리즘입니다.

• 그래프들을 큐(Queue)에 넣어놓고 사용한다.

• 그런 다음 거리 2에 있는 모든 정점, 등등. BFS는 가중치가 없는 그래프에서 두 꼭지점 사이의 최단 경로를 찾거나 무방향 그래프에서 연결된 모든 구성 요소를 찾는 데 사용됩니다.

  function bfs(graph, start, end) {
    const queue = [];
    const visited = new Set();
    const path = new Map();
  
    queue.push(start);
    visited.add(start);
  
    while (queue.length > 0) {
      const node = queue.shift();
  
      if (node === end) {
        return constructPath(path, start, end);
      }
  
      for (const neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
          queue.push(neighbor);
          visited.add(neighbor);
          path.set(neighbor, node);
        }
      }
    }
  
    return null;
  }
  
  function constructPath(path, start, end) {
    const result = [];
    let current = end;
  
    while (current !== start) {
      result.unshift(current);
      current = path.get(current);
    }
  
    result.unshift(start);
  
    return result;
  }
  

깊이 우선 탐색(DFS)

• 루트 노드에서 시작하여 역추적하기 전에 각 분기를 따라 가능한 한 멀리 탐색하는 그래프 순회 알고리즘입니다.
• 즉, DFS 알고리즘은 다음 노드로 역추적하고 거기에서 탐색하기 전에 시작 노드에서 가능한 한 깊이 탐색하여 그래프의 노드를 방문합니다.
• 재귀 함수를 사용하여 노드를 깊숙히 검색한다.

구현

function DFS(node) {
  console.log(node.value);
  visited[node.value] = true;
  for (let i = 0; i < node.neighbors.length; i++) {
    if (!visited[node.neighbors[i].value]) {
      DFS(node.neighbors[i]);
    }
  }
}

const visited = {};
DFS(node);

역추적(backtracking)

모든 잠재적 솔루션을 점진적으로 탐색하고 현재 경로를 따라 솔루션을 더 이상 찾을 수 없을 때사용하는 알고리즘 입니다.(즉, 가장 최근 단계 실행 취소)

현재 상태에서 가능한 각 솔루션 경로를 탐색하기 위해 함수를 재귀적으로 호출하는 재귀 접근 방식을 사용합니다.

재귀의 각 단계에서 알고리즘은 현재 경로가 유효한 솔루션으로 이어지는지 여부를 결정합니다. 그렇다면 알고리즘은 경로를 따라 계속 진행하고, 그렇지 않으면 이전 단계로 되돌아가 다른 경로를 시도합니다. 알고리즘은 유효한 솔루션을 찾거나 가능한 모든 경로를 소진할 때까지 이러한 방식으로 계속됩니다.