1. 그래프 순회
- 비선형 구조인 그래프의 모든 정점을 빠짐없이 탐색하는 것
- 너비 우선 탐색과 깊이 우선 탐색으로 순회할 수 있다.
2. BFS (Breadth First Search)
- 탐색 시작점의 인접 정점을 모두 방문한 이후, 방문한 정점을 시작점으로 하여 차례로 방문한다.
- 그래프는 계층형 구조가 아니기 때문에 루트의 개념이 없어 임의의 정점에서 시작 가능하다.
- 선입선출 형태의 큐를 활용한다.
'알고리즘' 카테고리의 다른 글
| [알고리즘] [19] 동적 계획법 (0) | 2024.02.27 |
|---|---|
| [알고리즘] [18] 최소신장트리 (1) | 2024.02.22 |
| [알고리즘] [17] 서로소 집합 (0) | 2024.02.21 |
| [알고리즘] [16] 그래프 순회2 (0) | 2024.02.20 |
| [알고리즘] [14] 그래프 (1) | 2024.02.15 |
| [알고리즘] [13] 분할정복 백트래킹 (0) | 2024.02.14 |
| [알고리즘] [12] 탐욕 알고리즘 (0) | 2024.02.13 |
| [알고리즘] [11] 트리 탐색 (1) | 2024.02.07 |
