DFS & BFS

들어가기 전, 

그래프의 탐색이란? 어떤 정점에서 출발하여 그래프의 모든 정점을 방문하는 것

                          깊이를 우선으로 하는 깊이 우선 탐색과 너비를 우선으로 하는 너비 우선 탐색이 있다.

 

1. DFS (Depth First Search) 깊이 우선 탐색

• 개념? 현재 정점에서 이동할 수 있는 점들까지 들어가면서 탐색하는 방법
• 모든 정점(혹은 노드라고도 부름)를 방문하고자 하는 경우에 사용
• 다른 정점으로 이동할 수 없을때, 이전 정점으로 돌아가야하므로 거쳐온 정점들을 모두 저장해 주어야 한다.
• 구현 방법? 스택 또는 재귀함수로 구현, 즉 후입선출(LIFO) 원칙으로 탐색
• 어떤 정점을 방문했는지의 여부를 반드시 검사해야한다. *검사안할 경우 무한루프에 빠질 수 있다.*

(ex)

dfs 

 

2. BFS (Breadth Frist Search) 너비 우선 탐색

• 개념? 현재 정점에서 가까운 정점부터 순서대로 탐색하는 방법
• 두 정점 사이의 최단 경로 혹은 임의의 경로를 찾고자 하는 경우에 사용
• 구현 방법? 큐로 구현, 즉 선입선출(FIFO) 원칙으로 탐색
• DFS와 마찬가지로, 어떤 정점을 방문했는지의 여부를 반드시 검사해야한다.

(ex)

bfs

 

마지막으로 dfs와 bfs를 비교해보자면,

간단함	검색속도
DFS 가 BFS 보다 구현이 간단하다.	DFS 가 BFS에 비해서 느리다
DFS는 모든 정점을 방문할때, BFS는 정점들 사이의 최단거리를 구할때 사용한다는 것을 다시 한번더 기억하자.