[Algorithm] dfs, bfs

DFS 알고리즘

DFS알고리즘은 스택(Stack) 자료 구조나 재귀를 통해서 구현할 수 있다.

1. 한 분기를 탐색한 후, 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색한다.
2. 더 이상 탐색이 불가능한 상태가 되면 이전 분기로 돌아와 다음 분기를 탐색한다.
3. 모든 정점을 방문한 후, 탐색을 종료한다.

스택을 활용한 DFS (Iteractive DFS)

1. 시작 정점을 스택에 삽입한다.
2. 스택에서 하나의 정점을 꺼낸다.
3. 스택에서 꺼낸 정점이 아직 방문하지 않은 정점이라면, 방문 표시 후 이웃 정점들을 스택에 삽입한다.
4. 스택에 담긴 정점이 없을 때까지 2-3번 과정을 반복한다.

function dfs(graph, start, visited) {
  const stack = [];
  stack.push(start);

  while (stack.length) {
    let v = stack.pop();
    if (!visited[v]) {
      console.log(v);
      visited[v] = true;

      for (let node of graph[v]) {
        if (!visited[node]) {
          stack.push(node);
        }
      }
    }
  }
}
const graph = [[1, 2, 4], [0, 5], [0, 5], [4], [0, 3], [1, 2]];
const visited = Array(7).fill(false);

dfs(graph, 0, visited);
// 0 4 3 2 5 1

재귀함수를 활용한 DFS (Recursive DFS)

1. 시작 정점을 인자로 받는 DFS 함수를 정의 한다.
2. 현재 정점을 방문 처리한다.
3. 현재 정점과 연결된 인접 정점들을 확인한다.
4. 인접 정점 중 방문하지 않은 정점을 재귀적으로 DFS에 호출한다.

재귀 함수는 항상 탈출 조건이 있어야 한다

const dfs = (graph, v, visited) => {
  // 현재 노드를 방문 처리
  visited[v] = true;
  console.log(v);

  // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for (let node of graph[v]) {
    if (!visited[node]) {
      dfs(graph, node, visited);
    }
  }
}

const graph = [[1, 2, 4], [0, 5], [0, 5], [4], [0, 3], [1, 2]];
const visited = Array(7).fill(false);

dfs(graph, 0, visited);
// 0 1 5 2 4 3

dfs(지금 몇번째, 지금까지 결과)
	if 끝까지 갔으면
		결과가 조건에 맞으면 count + 1
			return;
	dfs(다음 + 결과1)

dfs를 쓰는 경우

• 경로의 특징을 저장해 둬야 하는 문제
• 검색 대상 그래프가 큰 경우(노드와 간선이 많은 경우)

BFS 구현 함수 (JS)

탐색 스택, 방문 배열을 생성
탐색을 시작하는 정점을 탐색스택에 쌓는다.
탐색 스택의 length가 0이 아닐 때 까지 아래 과정을 반복
1) 스택 최상단에 있는 것을 없애고, 이를 탐색한다.
2) 탐색 시에 방문 했는지 체크, 했다면 패스
3) 방문 안했다면, 이를 방문 배열에 넣고 그 정점과 이어진 정점들을 배열에 다시 쌓는다.

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"]
};

// graph 자료구조와 startNode를 입력
const BFS = (graph, startNode) => {
  let visited = []; // 탐색을 마친 노드들
  let needVisit = []; // 탐색해야할 노드들

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

  while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
    const node = needVisit.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"]

let queue = [[시작점, 거리]];
visited[시작점] = true;

while(queue.length){
    let [현재, 거리] = queue.shift();

    if(도착) return 거리;

    for(다음 후보들){
        if(갈 수 있고 && 방문 안 했으면){
            visited = true;
            queue.push([다음, 거리 + 1]);
        }
    }
}

최단 거리 문제에서 bfs를 활용한다.

BFS와 DFS의 시간 복잡도

DFS와 BFS는 노드 수 + 간선 수 만큼의 복잡도를 지닌다. 즉, O(n)

---

참고 블로그 : https://velog.io/@lovesyung/Algorithm-DFS-BFS-Feat.-JS