knowledge

[ 알고리즘 ] DFS ( 깊이 우선 탐색 ) 와 BFS ( 너비 우선 탐색 )의 이해 및 구현

트리나 그래프를 탐색하는 방법은 크게 DFS 알고리즘과 BFS알고리즘 , 두 가지로 나누어진다. 1. DFS ( Depth-First-Search , 깊이 우선 탐색 ) DFS란 시작점부터 다음 분기로 넘어가기 전 해당 분기를 완전히 탐색하는 방법을 말한다. DFS는 재귀함수나 스택으로 구현되며 모든 분기를 탐색하고자 할 때 사용된다. DFS는 아래 서술할 BFS보다 구현은 쉽지만 탐색 속도가 느리다. 2. BFS ( Breadth-First-Search , 너비 우선 탐색 ) BFS란 임의의 노드 ( 주로 root 노드 ) 부터 인접한 노드들을 먼저 탐색하는 방법을 말한다. 즉 시작 정점에서 가까운 노드들부터 먼저 방문하고 멀리 있는 노드는 비교적 나중에 탐색하는 순환 방법이라 할 수 있겠다. BFS는..