[자료구조와 알고리즘] BFS와 DFS

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

- BFS는 큐의 개념이 사용됨

• 노드 ' S ' 부터 저장되고 사용됨 ( FIFO )
• 순서 : S -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

- BFS ( 너비우선탑색 ) 은 노드가 적은 경우 최단경로를 탐색할 때 유용함

- 너비우선적으로 노드를 탐색하는 경우, 큐를 활용하므로 노드가 많아지는 경우 메모리 저장공간이 증가하는 단점이 있음

- BFS는 재귀적으로 동작하지 않는데, 인접한 노드에 대해 먼저 탐색을 하기 때문에 재귀적으로 재호출할 필요가 없음

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

- DFS는 스택의 개념이 사용됨

• LIFO
• 순서 : 1 -> 2 -> 4 -> 5 -> 3

- 깊이우선탐색 알고리즘은 다른 경로를 역추적하고 탐색하기 전에 가능한 그래프를 분할함

- 백트래킹은 DFS에서 활용되는 방법인데, 쉽게 말해서 노드가 있을만한 곳을 되돌아가서 모두 살펴본다는 개념

- DFS는 깊이우선적으로 탐색을 진행하고, 재귀적으로 아래에서부터 탐색하지 않은 정점이 있는지 확인하는 방법

- DFS는 그래프의 모든 노드를 방문하는 경우 사용됨

• DFS의 단점은 최단 경로를 찾지 못하고, 시간이 오래 걸릴 수 있음