hello-algo/ko/docs/chapter_graph/graph_traversal.md

그래프 순회

트리는 '일대다' 관계를 나타내지만, 그래프는 자유도가 더 높아 임의의 '다대다' 관계를 표현할 수 있다. 따라서 트리는 그래프의 특수한 경우로 볼 수 있다. 트리 순회 역시 그래프 순회의 특수한 경우다.

그래프와 트리 모두 탐색 알고리즘을 이용하여 순회한다. 그래프 순회도 너비 우선 순회와 깊이 우선 순회의 두 가지로 나뉜다.

너비 우선 순회

너비 우선 순회는 가까운 곳에서 먼 곳으로 진행하는 순회 방식이다. 한 노드에서 출발하여 항상 거리가 가장 가까운 정점을 먼저 방문하고, 한 층씩 바깥으로 확장한다. 아래 그림에서는 왼쪽 위 정점에서 출발하여 해당 정점의 모든 인접 정점을 먼저 순회한 다음, 다음 정점의 모든 인접 정점을 순회한다. 이를 모든 정점을 방문할 때까지 반복한다.

알고리즘 구현

BFS는 보통 큐로 구현하며, 코드는 다음과 같다. 큐의 '선입선출' 성질은 BFS의 '가까운 곳부터 먼 곳으로'라는 발상과 잘 맞는다.

1. 순회의 시작 정점 startVet를 큐에 넣고 반복문을 시작한다.
2. 매 반복에서 큐의 맨 앞 정점을 꺼내 방문을 기록한 다음, 해당 정점의 모든 인접 정점을 큐의 끝에 넣는다.
3. 모든 정점을 방문할 때까지 2. 단계를 반복한 뒤 종료한다.

같은 정점을 여러 번 순회하지 않도록 해시 집합 visited를 사용하여 방문한 노드를 기록한다.

!!! tip "참고"

해시 집합은 `value` 없이 `key`만 저장하는 해시 테이블로 볼 수 있다. `key`의 추가, 삭제, 조회, 수정 연산을 $O(1)$ 시간에 수행한다. `key`는 중복될 수 없으므로, 해시 집합은 데이터 중복 제거 등에 자주 사용된다.

[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로 이미 방문한 정점을 기록하여 중복 방문을 방지한다.

[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|) 공간을 사용한다.