그래프의 탐색방법인 깊이 우선 탐색과 너비 우선 탐색을 알아본다.
DFS BFS란? 백준 문제추천
너비 우선 탐색 (BFS, Breadth-First-Search)
루트 노드 혹은 다른 임의의 노드에서 인접한 노드를 탐색하는 방법
장점
- 최단 경로를 보장한다.
- 최단 경로가 존재하면 깊이가 어찌됐든 답을 구할 수 있다.
단점
- 경로가 길 경우에는 탐색가지가 급격히 증가함으로 많은 메모리를 필요로 한다.
- 해가 존재하지 않을경우 모든 그래프를 탐색 후 실패로 끝난다.
- 무한 그래프의 경우에는 해를 찾지 못하고 끝내지도 못한다.
시간복잡도
- 인접 리스트 : O(V + E)
- 인접 행렬 : O(V^2) * [V : 접점(Vertex) E : 간선 (Edge)]
구현방법
![[출처 : developer-mac.tistory.com/64]](https://s3-us-west-2.amazonaws.com/secure.notion-static.com/21da9d46-30ad-4d07-a573-b3c76df40297/img1.daumcdn.gif)
[출처 : developer-mac.tistory.com/64]
깊이 우선 탐색 (DFS, Depth-First-Search)
해당 분기를 완벽하게 탐색 후 다음 분기로 넘어가는 탐색방법
장점
- 현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용한다.
- 찾으려는 노드가 깊은 단계에 있을때 BFS보다 빠르게 찾을 수 있다.
단점
- 해가 없는 경로를 탐색 할 경우 단계가 끝날 때 까지 탐색한다.
효율을 높이기 위해서 미리 지정한 임의 깊이까지만 탐색하고
해를 발견하지 못하면 빠져나와 다른 경로를 탐색하는 방법을 사용한다.
- 얻어진 해가 최단 경로라는 보장이 없다.
시간복잡도
- 인접 리스트 : O(V + E)
- 인접 행렬 : O(V^2) * [V : 접점(Vertex) E : 간선 (Edge)]
구현방법
![[출처 : developer-mac.tistory.com/64]](https://s3-us-west-2.amazonaws.com/secure.notion-static.com/fa748a77-83ab-4671-a7e8-892f3fcc0cbd/Depth-First-Search.gif)
[출처 : developer-mac.tistory.com/64]
탐색방법
인접행렬