DFS와 BFS?
트리, 그래프, 탐색 알고리즘에 자주 쓰인다. 이둘을 바이너리 트리에서 구분해보고, 로직을 그래프까지 확장시켜보자
DFS vs BFS
BFS
Breadth First Search로 너비를 우선적으로 탐색한다.
root가 11인 트리는 연결된 자식 노드인 6과 16을 먼저 탐색한다. (11->6-16)
그후 6의 자식 노드와 16의 자식노드를 탐색한다. (3->9->14-16)
DFS
Depth First Search로 깊이를 우선적으로 탐색한다. 수평적으로 탐색한 bfs와 다르게 수직적으로 탐색을 실시한다. dfs에서는 연결된 노드의 끝까지 탐색을 하고 역행하여 다시 탐색하지 않은 방향으로 다시 탐색하게 된다.
예시를 살펴보면 11->6->3->2->1 역행 9->8->7
