자료구조

BFS (너비 우선 탐색, Breadth-First Search)

임의의 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 있는 정점을 나중에 방문하는 방법
두 노드 사이의 최단 경로를 찾고 싶을 때 사용
재귀적으로 동작하지 않음
Queue로 구현됨

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

임의의 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
모든 노드를 방문하고자 하는 경우에 사용
재귀적인 형태를 지님
Stack이나 재귀함수로 구현됨

BFS와 DFS의 비교 및 정리

BFS가 DFS에 비해 검색 속도가 빠름
DFS가 BFS보다 좀 더 간단함
BFS는 경로의 특징을 가지지 못함
BFS와 DFS 둘 다 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것 (이를 검사하지 않을 경우 무한루프에 빠질 위험이 있음)