# 그래프 순회
트리는 '일대다' 관계를 나타내지만, 그래프는 자유도가 더 높아 임의의 '다대다' 관계를 표현할 수 있다. 따라서 트리는 그래프의 특수한 경우로 볼 수 있다. **트리 순회 역시 그래프 순회의 특수한 경우다**.
그래프와 트리 모두 탐색 알고리즘을 이용하여 순회한다. 그래프 순회도 너비 우선 순회와 깊이 우선 순회의 두 가지로 나뉜다.
## 너비 우선 순회
**너비 우선 순회는 가까운 곳에서 먼 곳으로 진행하는 순회 방식이다. 한 노드에서 출발하여 항상 거리가 가장 가까운 정점을 먼저 방문하고, 한 층씩 바깥으로 확장한다**. 아래 그림에서는 왼쪽 위 정점에서 출발하여 해당 정점의 모든 인접 정점을 먼저 순회한 다음, 다음 정점의 모든 인접 정점을 순회한다. 이를 모든 정점을 방문할 때까지 반복한다.
### 알고리즘 구현
BFS는 보통 큐로 구현하며, 코드는 다음과 같다. 큐의 '선입선출' 성질은 BFS의 '가까운 곳부터 먼 곳으로'라는 발상과 잘 맞는다.
1. 순회의 시작 정점 `startVet`를 큐에 넣고 반복문을 시작한다.
2. 매 반복에서 큐의 맨 앞 정점을 꺼내 방문을 기록한 다음, 해당 정점의 모든 인접 정점을 큐의 끝에 넣는다.
3. 모든 정점을 방문할 때까지 `2.` 단계를 반복한 뒤 종료한다.
같은 정점을 여러 번 순회하지 않도록 해시 집합 `visited`를 사용하여 방문한 노드를 기록한다.
!!! tip "참고"
해시 집합은 `value` 없이 `key`만 저장하는 해시 테이블로 볼 수 있다. `key`의 추가, 삭제, 조회, 수정 연산을 $O(1)$ 시간에 수행한다. `key`는 중복될 수 없으므로, 해시 집합은 데이터 중복 제거 등에 자주 사용된다.
```src
[file]{graph_bfs}-[class]{}-[func]{graph_bfs}
```
코드만으로는 추상적일 수 있으므로 아래 그림과 함께 살펴보며 이해를 깊이 다져 보자.
=== "<1>"
=== "<2>"
=== "<3>"
=== "<4>"
=== "<5>"
=== "<6>"
=== "<7>"
=== "<8>"
=== "<9>"
=== "<10>"
=== "<11>"
!!! question "너비 우선 순회 순서는 유일한가?"
유일하지 않다. 너비 우선 순회는 '가까운 곳부터 먼 곳으로' 순회하기만 하면 되므로, **거리가 같은 여러 정점의 방문 순서는 자유롭게 바꿀 수 있다**. 위 그림에서는 정점 $1$, $3$의 방문 순서를 바꿀 수 있고, 정점 $2$, $4$, $6$의 순서도 자유롭게 바꿀 수 있다.
### 복잡도 분석
**시간 복잡도**: 모든 정점은 큐에 한 번 들어갔다가 한 번 나오므로 $O(|V|)$ 시간이 걸린다. 인접 정점을 순회할 때는 무방향 그래프이므로 모든 간선을 $2$ 번씩 방문하여 $O(2|E|)$ 시간이 걸린다. 전체 시간은 $O(|V| + |E|)$이다.
**공간 복잡도**: 리스트 `res`, 해시 집합 `visited`, 큐 `que`에 저장되는 정점 수는 각각 최대 $|V|$이므로 $O(|V|)$ 공간을 사용한다.
## 깊이 우선 순회
**깊이 우선 순회는 먼저 끝까지 나아가고, 더 갈 곳이 없으면 되돌아오는 순회 방식이다**. 아래 그림에서는 왼쪽 위 정점에서 출발하여 현재 정점의 인접 정점 하나를 방문한다. 끝에 도달하면 되돌아오고, 다시 끝까지 나아갔다가 돌아오는 과정을 모든 정점을 순회할 때까지 반복한다.
### 알고리즘 구현
'끝까지 갔다가 돌아오는' 알고리즘 패턴은 보통 재귀로 구현한다. 너비 우선 순회와 마찬가지로 깊이 우선 순회에서도 해시 집합 `visited`로 이미 방문한 정점을 기록하여 중복 방문을 방지한다.
```src
[file]{graph_dfs}-[class]{}-[func]{graph_dfs}
```
깊이 우선 순회의 진행 과정은 아래 그림과 같다.
- **직선 점선은 아래로 내려가는 재귀 호출을 나타내며**, 새 정점을 방문하기 위해 새로운 재귀 메서드를 호출했다는 뜻이다.
- **곡선 점선은 위로 되돌아가는 백트래킹을 나타내며**, 재귀 메서드가 반환되어 이를 호출한 위치로 돌아왔다는 뜻이다.
이해를 깊이 다지기 위해 아래 그림과 코드를 함께 보면서, 각 재귀 메서드가 언제 호출되고 언제 반환되는지까지 포함하여 전체 DFS 과정을 머릿속으로 따라가 보자(또는 직접 그려 보자).
=== "<1>"
=== "<2>"
=== "<3>"
=== "<4>"
=== "<5>"
=== "<6>"
=== "<7>"
=== "<8>"
=== "<9>"
=== "<10>"
=== "<11>"
!!! question "깊이 우선 순회 순서는 유일한가?"
너비 우선 순회와 마찬가지로 깊이 우선 순회 순서도 유일하지 않다. 한 정점에서 어느 방향을 먼저 탐색해도 되므로, 인접 정점의 순서를 자유롭게 바꾸어도 모두 깊이 우선 순회에 해당한다.
트리 순회를 예로 들면 '루트 $\rightarrow$ 왼쪽 $\rightarrow$ 오른쪽', '왼쪽 $\rightarrow$ 루트 $\rightarrow$ 오른쪽', '왼쪽 $\rightarrow$ 오른쪽 $\rightarrow$ 루트'는 각각 전위, 중위, 후위 순회에 해당한다. 세 방식은 방문 우선순위가 다르지만 모두 깊이 우선 순회다.
### 복잡도 분석
**시간 복잡도**: 모든 정점을 $1$ 번씩 방문하는 데 $O(|V|)$ 시간이 걸리고, 모든 간선을 $2$ 번씩 방문하는 데 $O(2|E|)$ 시간이 걸린다. 전체 시간은 $O(|V| + |E|)$이다.
**공간 복잡도**: 리스트 `res`와 해시 집합 `visited`의 정점 수는 각각 최대 $|V|$이고, 재귀 깊이도 최대 $|V|$이므로 $O(|V|)$ 공간을 사용한다.