DFS
일반적으로 재귀를 사용하여 구현한다.
BFS
큐를 사용하여 구현한다.
BFS는 정의상 시작점으로부터 가까운 지점부터 방문하게 되기 때문에 그림에서처럼 가중치가 전부 동일한 그래프에서는 최단거리를 확실하게 구해줄 수 있는 것이다.
BFS를 이용한 최단거리는, 가중치만 전부 동일하다면 방향 그래프에서도 동일하게 적용된다.
'Python > Algorithm' 카테고리의 다른 글
| [Python] 백트래킹 (0) | 2023.04.06 |
|---|---|
| [Python] 냅색 알고리즘(Knapsack Problem) - Dynamic Programming(DP) (0) | 2023.03.19 |
| 트리 (0) | 2022.06.18 |
| 스택, 큐, 덱 (0) | 2022.06.12 |
| 이진탐색 (0) | 2022.06.12 |