그래프란?
정점(node)과 그 정점을 연결하는 간선으로 이루어진 자료구조의 일종을 말한다.
그래프를 탐색한다는 것은 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문한다는 것을 말한다.
그래프를 탐색하는 방법은 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 방법으로 나뉜다.
💡깊이 우선 탐색(DFS)
: 루트 노드(Root Node) 혹은 다른 임의 노드(Node)에서 시작해서 다음 분기(Branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
출처 https://developer-mac.tistory.com/64
미로찾기를 할 때 한 방향으로 가능한 만큼 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식이라고 할 수 있다.
- 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.
- 너비 우선 탐색(BFS)보다 좀 더 간단하다.
- 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.
장점
- 현 경로상의 노드들만 기억하면 되므로 저장공간 수요가 비교적 적다.
- 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
단점
- 해가 없는 경로가 깊을 경우 탐색시간이 오래 걸릴 수 있다.
- 얻어진 해가 최단 경로가 된다는 보장이 없다.
💡너비 우선 탐색(BFS)
: 루트 노드(Root Node) 혹은 다른 임의 노드(Node)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
출처 https://developer-mac.tistory.com/64
- 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다.
🔍깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 비교
| 깊이우선탐색(DFS) | 너비우선탐색(BFS) |
|---|---|
| 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 | 현재 정점에서 연결된 가까운 점들부터 탐색 |
| 스택 또는 재귀함수로 구현 | 큐를 이용해서 구현 |
| 경로의 특징을 저장해둬야 하는 문제 | 최단거리를 구해야 하는 문제 |
| 검색 대상이 큰 경우 | 검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않는 경우 |
🔍시간복잡도
DFS와 BFS모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다.
두 방식 모두 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 된다.
N은 노드, E는 간선일 때
인접 리스트 : O(N+E)
인접 행렬 : O(N²)참고
https://developer-mac.tistory.com/64
https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90
