[알고리즘] 깊이 우선 탐색(DPS)과 너비 우선 탐색(BFS)

1. 그래프 탐색

: 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

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

: 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

• 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
• 깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단함
• 검색 속도 자체는 너비 우선 탐색에 비해서 느림

1) 깊이 우선 탐색(DFS)의 특징

• 자기 자신을 호출하는 순환 알고리즘의 형태를 지님
• 어떤 노드를 방문했었는지 여부를 반드시 검사해야 함

2) 깊이 우선 탐색(DFS)의 과정

3) 깊이 우선 탐색(DFS)의 시간 복잡도

• 그래프(정점의 수: N, 간선의 수:E)의 모든 간선을 조회함
• 인접 리스트로 표현된 그래프 : O(N+E)
• 인접 행렬로 표현된 그래프 : O(N^2)

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

: 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법

• 시작 정점으로 부터 가까운정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택함

1) 너비 우선 탐색(BFS)의 특징

• 재귀적으로 동작하지 않음
• 어떤 노드를 방문했었는지 여부를 반드시 검사해야 함
• 큐를 사용함(FIFO 원칙으로 탐색)

2) 너비 우선 탐색(BFS)의 과정