728x90
그래프를 탐색하는 방법에는 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다.
- 그래프 : 정점(node)과 그 정점을 연결하는 간선(dege)으로 이루어진 자료구조의 일종
- 그래프를 탐색한다 : 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
+ 트리 : 그래프 중에서 방향성이 있는 비순환 그래프
1. 깊이 우선 탐색(DFS; Depth-First Search)
- 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동
2. 너비 우선 탐색(BFS; Breadth-First Search)
- 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동
3. DFS와 BFS 비교
| DFS | BFS |
| 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 | 현재 정점에 연결된 가까운 점들부터 탐색 |
| 스택 또는 재귀함수로 구현 | 큐를 이용해서 구현 |
- DFS와 BFS의 시간복잡도
두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일합니다.
DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 됩니다.
[출처]
728x90