[알고리즘 정리] 02. 탐색

📌 이번시간에는 탐색 알고리즘에 대해 정리를 할 것 이다.

탐색

1. BFS(Breadth-First-Search)

너비 우선 탐색이다. depth가 같은 것들 부터 먼저 찾는 탐색 알고리즘이다.

1-1. while문 사용

코드

// DFS(Depth first Search)
// 그래프가 주어졌을때, stack을 사용하여, depth를 1씩 증가하면서 먼저 찾는 탐색기법
// 두 가지 방법이 있다.
// 1. while문 사용
// 2. 재귀함수 사용

const graph = {
  1: [1, 2, 3],
  2: [1, 4, 5],
  3: [1, 6, 7],
  4: [2],
  5: [2],
  6: [3],
  7: [3],
};

const BFS_while = graph => {
  let graphs = graph;
  let nodeNum = Object.keys(graphs).length;
  let visited = new Array(nodeNum).fill(false);
  let stack = [1];
  while (stack.length) {
    let size = stack.length;
    for (var i = 0; i < size; i++) {
      let popped = stack.shift();
      if (!visited[popped - 1]) {
        console.log(popped);
        visited[popped - 1] = true;
        stack.push(...graphs[popped]);
      }
    }
  }
};

BFS_while(graph);

1-2. 재귀함수 사용

const graph = {
  1: [1, 2, 3],
  2: [1, 4, 5],
  3: [1, 6, 7],
  4: [2],
  5: [2],
  6: [3],
  7: [3],
};

const BFS_recursive = (graph, needVisit, visit) => {
  let graphs = graph;
  let visited = [...visit];
  let need = [...needVisit];
  if (need.length === 0) {
    return 0;
  }
  let shifted = need.shift();
  if (!visited.includes(shifted)) {
    visited.push(shifted);
    console.log(shifted);
    need.push(...graphs[shifted]);
    BFS_recursive(graphs, need, visited);
  } else {
    BFS_recursive(graphs, need, visited);
  }
};

BFS_recursive(graph, [1], []);

2. DFS(Depth=First-Search)

깊이 우선 탐색이다. depth를 하나씩 증가시켜, 하나의 부모 노드에서부터 자식 노드들을 먼저 탐색하는 기법이다.

2-1. while문 사용

코드

// DFS(Depth first Search)
// 그래프가 주어졌을때, queue를 사용하여, depth를 1씩 증가하면서 먼저 찾는 탐색기법
// 두 가지 방법이 있다.
// 1. while문 사용
// 2. 재귀함수 사용

const graph = {
  1: [1, 2, 3],
  2: [1, 4, 5],
  3: [1, 6, 7],
  4: [2],
  5: [2],
  6: [3],
  7: [3],
};
const DFS_while = graph => {
  //시작노드는 1부터
  let graphs = graph;
  let nodeNum = Object.keys(graphs).length;
  let visited = new Array(nodeNum).fill(0);
  let queue = [1];
  while (queue.length) {
    let shifted = queue.shift();
    if (!visited[shifted - 1]) {
      console.log(shifted);
      visited[shifted - 1] = 1;
      queue.unshift(...graphs[shifted]);
    }
  }
};

DFS_while(graph);

2-2. 재귀함수 사용

코드

const graph = {
  1: [1, 2, 3],
  2: [1, 4, 5],
  3: [1, 6, 7],
  4: [2],
  5: [2],
  6: [3],
  7: [3],
};

const DFS_recursive = (graph, visit, needVisit) => {
  let graphs = graph;
  let visited = [...visit];
  let need = [...needVisit];
  for (var i = 0; i < need.length; i++) {
    if (!visited.includes(needVisit[i])) {
      console.log(needVisit[i]);
      visited.push(needVisit[i]);
      need.unshift(...graphs[needVisit[i]]);
      return DFS_recursive(graph, visited, need);
    }
  }
};
DFS_recursive(graph, [], [1]);