- 탐색 알고리즘 : 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘
그래프
- 정점과 간선으로 구성된, 한정된 자료구조
- 각각의 지점을 정점, 정점과 정점의 연결을 간선이라고 한다.
DFS(깊이 우선 탐색)
- 가장 직관적이고 구현하기 쉬운 탐색 방법
- 현재 정점과 연결된 정점들을 하나씩 갈 수 있는지 검사하고, 특정 정점으로 갈 수 있다면 그 정점에 가서 같은 행위를 반복한다.
- 같은 정점을 다시 방문하지 않도록 정점에 방문했다는 것을 표시해준다.
- 재귀 함수를 통해 구현한다.
- 단점 : 재귀 함수를 이용하기 때문에 함수 호출 비용이 추가로 들어가며, 재귀 깊이가 지나치게 깊어지면 메모리 비용을 예측하기 어렵다. 최단 경로를 알 수 없다.
BFS(너비 우선 탐색)
- 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘
- 큐를 이용하여 구현한다.
- 출발점을 먼저 큐에 넣고, 다음 로직을 반복한다.
- 큐에 저장된 정점을 하나 Dequeue한다.
- 그리고 Dequeue된 정점과 연결된 모든 정점을 큐에 넣는다.
- 큐가 비어있다면 반복을 종료한다.
- 장점 : 효율적인 운영이 가능하고, 시간/공간 복잡도 면에서 안정적이다. 간선의 비용이 모두 같을 경우, 최단 경로를 구할 수 있다.(간선의 비용이 각각 다를 경우, 다익스트라 알고리즘 등의 최단거리 알고리즘을 활용해야 한다.)
- 단점 : DFS에 비해 코드 구현이 어렵다. 모든 지점을 탐색할 경우를 대비해, 큐의 메모리가 미리 준비되어 있어야 한다.