WEEK 5: DFS, BFS

완전탐색, 백트래킹 이론을 공부하면서 DFS, BFS 알고리즘 이론 공부가 더 필요하다고 느껴 스터디 커리큘럼에 추가하게 되었다.

DFS(Depth-First Search)

깊이 우선 탐색. 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법.

사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
BFS와 비교
- 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
- 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.
특징
- 자기 자신을 호출하는 순환 알고리즘의 형태
- 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
- 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 함 -> 안하면 무한루프에 빠질 위험 있음
구현 방법(2): 순환 호출, 명시적인 스택 사용
시간 복잡도
- DFS는 그래프(정점의 수: N, 간선의 수: E)의 모든 간선을 조회
  - 인접 리스트로 표현된 그래프: O(N+E)
  - 인접 행렬로 표현된 그래프: O(N^2)
- 즉, 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph) 의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.

너비 우선 탐색. 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때
특징
- 직관적 x
- 재귀적으로 작동 x
- 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 함 -> 안하면 무한루프에 빠질 위험 있음
- 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용 -> 선입선출(FIFO) 원칙
시간 복잡도
- 인접 리스트로 표현된 그래프: O(N+E)
- 인접 행렬로 표현된 그래프: O(N^2)
- 깊이 우선 탐색(DFS)과 마찬가지로 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph) 의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.