-
들어가기 전,
그래프의 탐색이란? 어떤 정점에서 출발하여 그래프의 모든 정점을 방문하는 것
깊이를 우선으로 하는 깊이 우선 탐색과 너비를 우선으로 하는 너비 우선 탐색이 있다.
1. DFS (Depth First Search) 깊이 우선 탐색
- 개념? 현재 정점에서 이동할 수 있는 점들까지 들어가면서 탐색하는 방법
- 모든 정점(혹은 노드라고도 부름)를 방문하고자 하는 경우에 사용
- 다른 정점으로 이동할 수 없을때, 이전 정점으로 돌아가야하므로 거쳐온 정점들을 모두 저장해 주어야 한다.
- 구현 방법? 스택 또는 재귀함수로 구현, 즉 후입선출(LIFO) 원칙으로 탐색
- 어떤 정점을 방문했는지의 여부를 반드시 검사해야한다. *검사안할 경우 무한루프에 빠질 수 있다.*
(ex)
2. BFS (Breadth Frist Search) 너비 우선 탐색
- 개념? 현재 정점에서 가까운 정점부터 순서대로 탐색하는 방법
- 두 정점 사이의 최단 경로 혹은 임의의 경로를 찾고자 하는 경우에 사용
- 구현 방법? 큐로 구현, 즉 선입선출(FIFO) 원칙으로 탐색
- DFS와 마찬가지로, 어떤 정점을 방문했는지의 여부를 반드시 검사해야한다.
(ex)
마지막으로 dfs와 bfs를 비교해보자면,
간단함 검색속도 DFS 가 BFS 보다 구현이 간단하다. DFS 가 BFS에 비해서 느리다 DFS는 모든 정점을 방문할때, BFS는 정점들 사이의 최단거리를 구할때 사용한다는 것을 다시 한번더 기억하자. '알고리즘' 카테고리의 다른 글
Greedy Algorithm (0) 2020.03.17 Floyd-Warshall (0) 2020.03.17 Dijkstra (0) 2020.03.17 Binary Serach (0) 2020.03.16 DP (0) 2020.03.16