BFS와 DFS는 트리나 그래프 등의 비선형 구조를 무차별 탐색할 때 사용한다. 여기서 무차별 탐색이란 가능한 경우의 수를 전부 시도한다는 의미이다. 거리, 지도 탐색 등에 많이 사용된다.

BFS (Breadth-First Search) 넓이 우선 검색

BFS는 넓이 우선 검색으로, 같은 depth를 모두 확인한 후에 내려가서 다시 검색한다.자식 노드를 전부 방문하고 그 뒤에 후손 노드를 방문하는 식이다.
큐를 이용해서 구현한다.

const  BFS = (graph, start) => {
    	const visited = []; //방문한 노드
      	const queue = []; //탐색 예정 노드
      
      	queue.push(start);
      
      	while(queue.length !==0){
      		const node = queue.shift(); // 선입선출
          	if(!visited.includes(node)){
            	visited.push(node);
                queue.push(...graph[node]);
            }
        }
      return visited;
    }

DFS (Depth-First Search) 깊이 우선 검색

DFS는 깊이 우선 검색으로, 자식 노드를 끝까지 탐색한 후에 다시 되돌아가서 그 옆 노드를 검색한다. 스택을 이용해서 구현하며, 재귀를 사용하면 더 간단하게 구현 가능하다.

	const  DFS = (graph, start) => {
    	const visited = []; //방문한 노드
      	const stack = []; //탐색 예정 노드
      
      	stack.push(start);
      
      	while(stack.length !==0){
      		const node = stack.pop(); // 후입선출
          	if(!visited.includes(node)){
            	visited.push(node);
                stack.push(...graph[node].reverse());
            }
        }
      return visited;
    }