DFS, BFS

그래프를 탐색하는 방법

DFS(깊이우선탐색)	BFS(너비우선탐색)
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀함수로 구현	큐를 이용해서 구현

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

모든 노드를 방문하고자 하는 경우에 선택한다.

DFS는 그래프(정점의 수 : N, 간선의 수: E)의 모든 간선을 조회함

• 인접 리스트로 표현된 그래프 : O(N+E)
• 인접 행렬로 표현된 그래프 : O(N^2)

깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

BFS 너비 우선 탐색 (Breadth-First Search)

두 노드 사이의 최단 경로를 찾고 싶을 때 선택한다.

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로,
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모름
너비 우선 탐색의 경우 - Sam과 가까운 관계부터 탐색

DFS와 BFS의 시간복잡도는 동일하다.

다음 노드가 방문하였는지를 확인하는 시간 + 각 노드를 방문하는 시간

DFS, BFS의 적합한 문제 유형

DFS, BFS 모두 적합한 유형

• 그래프의 모든 정점을 방문하는 것이 주요한 문제 단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없다.

DFS가 적합한 유형

• 검색 대상 그래프가 큰 경우
• 경로의 특징을 저장해둬야 하는 문제(a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제)
• 각각의 경로마다 특징을 저장해둬야 할 때

BFS가 적합한 유형

• 최단거리 구해야 하는 문제
• 미로 찾기
• 최단거리를 구해야 할 경우
• 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않은 경우

출처

lucky-korma