[week5] DFS 와 BFS

DFS

DFS는 Depth First Search의 약자로 깊이 우선 텀색을 말한다.

DFS는 자기 자신을 호출하는 순환 알고리즘의 형태를 지닌다. 

위의 그림처럼 0에서 1로, 1에서 3으로 갔을 때 더 이상 갈 곳이 없으면 백트래킹을해서 다시 1로 가게 됨

이후에 방문하지 않은 4를 방문하게 되는 형태

 

해당 분기에서 갈 수 있을떄까지 계속 가다가 더 이상 갈 수 없게 되면

다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방식

 

대게 Stack을 사용하고 모든 노드를 방문하고자 할 때 사용한다. 

BFS보다 더 간단하게 구현되지만 검색 속도 자체는 BFS에 비해 느리다. 

 

BFS

BFS는 Breadth First Search의 약자로 너비 우선 탐색을 말한다. 

 

BFS는 재귀적으로 동작하지 않고 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 큐(Queue)를 사용한다. 

즉, 선입선출 원칙으로 탐색

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하기 때문에 

대게 두 노드 사이의 최단 경로를 찾을 때 주로 사용한다. 

 

https://binco.tistory.com/entry/Java-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-DFS%EC%99%80BFS-%EC%99%84%EB%B2%BD%EC%A0%95%EB%A6%AC

Java 알고리즘 DFS와 BFS 완벽 정리