깊이 우선 탐색(DFS):
하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 알고리즘.
아직 방문하지 않은 노드 중 제일 가까운 노드로 넘어간다. 연결된 노드가 모두 방문한 적이 있거나 연결된 노드가 없다면 그전 노드로 back하여 다시 방문 가능한 노드를 찾아 같은 과정을 반복한다. 모든 노드를 방문하고자 하는 경우에 이 방법을 사용한다.
검색 속도는 BFS보다 느리다.
예제) 1 -> 2 -> 4 -> 8 -> 5 -> 6 -> 3 -> 7
너비 우선 탐색(BFS):
하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 알고리즘.
시작 정점에서 시작하여 가까운 정점을 방문하고 멀리 떨어진 정점은 가장 나중 방문하는 순회방법. 큐를 사용하여 선입선출 원칙으로 탐색한다. 루트노드와 연결된 모든 노드를 방문하고 다시 방문한 노드와 연결된 모든 노드중 방문하지 않은 노드가 있다면 방문하고 없다면 해당 노드를 큐에서 제거해준다. 검색 속도는 BFS보다 빠르며, 재귀적으로 동작하지 않는다.
예제) 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
DFS와 BFS차이
java