BFS, DFS, 트리 순회

BFS (Breadth-First Search)

너비 우선 탐색이라고하고, 주로 두 정점 사이의 최단 경로를 찾을 때 사용합니다.

만약 경로를 하나씩 전부 방문한다면, 최악의 경우 모든 경로를 다 살펴봐야 합니다.

 

DFS (Depth-First Search)

깊이 우선 탐색이라고 하고, 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용합니다. BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있습니다.

 

DFS와 BFS는 모든 정점을 한번만 방문한다는 공통점을 지니고 있지만, 사용할 때의 장단점은 분명하기에 상황에 맞는 탐색 기법을 사용해야합니다.