그래프 자료구조를 설명할 때, 노드와 간선을 이용하여 설명하는데 비유를 하면 네이버 지도의 길찾기와 같은 느낌인 것 같다.
대중교통으로 어떤 길을 찾아갈 때, 어느 지점(노드)에 버스를 타서 어느 지점에 내려서 어느 지점에 지하철을 타서 어느 지점에 지하철을 내려서 도착. 각 지점이 노드고 각 지점 사이는 간선이라고 볼 수 있다.
이 그래프를 표현할 때, 딕셔너리 + 리스트를 이용한다. 지점은 딕셔너리의 키 값을 이용하고, 해당 지점과 연결된 노드들은 딕셔너리의 값을 리스트를 이용하여 저장한다.
(참고로 이 표현은 고정된 방식은 아니고 다른 방식도 가능하다. '배열 + 링크드리스트' 조합도 가능하고 '2차원 배열'을 이용하여도 표현이 가능하다. 여기서는 아주 개인적으로 자주 봤던 조합을 이용하였다.)
graph_dict = {
"A": ["B", "C"],
"B": [],
"C": ["D"],
"D": []
}위와 같이 코드를 작성하면, A노드는 B, C 노드와 연결되어 있고 B와 D는 연결한 지점이 없고 C노드는 D와 연결되어 있다.
추가로 여기서 위의 코드는 '방향성'이 있는 자료구조이다.
A노드에서 B, C노드로 갈 수는 있으나 B, C노드에서는 A노드로 갈 수 없다.
방향성이 없는 양방향 간선들을 만들려면 반대방향으로 동일하게 추가해주면 된다. 이렇게 하면 데이터 총량이 2배 증가한다.
양방향 그래프는 아래와 같이 된다.
graph_dict = {
"A": ["B", "C"],
"B": ["A"],
"C": ["A", "D"],
"D": ["C"]
}
그림으로 보면, 아래와 같이 된다.
이제 그래프 자료구조 탐색을 해야하는데 크게 두 종류가 있다.
- DFS (Depth First Search) : 깊이 우선 탐색
- BFS (Breadth First Search) : 너비 우선 탐색
BFS와 DFS 탐색 방식의 방문 우선 순위의 차이만 있는 것 같고 행위는 비슷한 것 같다.
DFS
BFS도 그렇지만 탐색을 하기 위해서는 기본적으로 2가지 자료구조를 이용하여 탐색한다.
DFS의 경우, 스택 자료구조 + 리스트 조합을 여기서 사용할 것이다.
(여기서도 꼭 리스트만을 써야하는 것은 아니고 상황에 따라 다른 방법들도 가능하다.)
각 자료구조의 용도는
- 스택은 앞으로 탐색할 노드 대상들을 보관하는 용도로 사용
- 리스트는 방문했던 노드들을 기록하는 대장으로 사용
(기록하고 방문했는지 확인만 할 수 있다면 딕셔너리가 됐던 배열을 이용하던 상관없는 것 같다.)
탐색은 총 5단계를 반복하는 것과 같다.
- 스택에서 방문할 노드를 하나 꺼낸다.
- 리스트에 방문한 노드를 저장한다. (리스트에 방문 이력 남김)
- 해당 노드와 연결된(인접한) 노드 리스트를 가져온다.
- 연결된 노드 리스트 중 방문하지 않았던 노드들은 스택에 저장한다.
- 스택에 값이 없을 때까지 반복
방금 소개한 그래프 예제(양방향 기준)를 이용하여 작동 방식을 길~~게 설명하자면
시작노드를 A노드로 지정. A 노드를 스택에 먼저 넣어준다.
1. 스택에서 하나를 Pop해준다(=노드를 방문한다). A 노드가 나왔네? 일단 A 노드를 방문했으니 방문 이력 리스트에 추가해준다.
2. A 노드와 연결된(인접한) 노드들을 가져온다. graph_dict['A'] 값은 ['B', 'C']이므로 B, C가 연결된 노드다.
3. A 노드와 연결된 노드 중에서 기존에 방문했는지 방문 이력 리스트 안에서 확인해보고 방문을 하지 않았다면 모두 스택에 넣어준다. B, C 순서대로 스택에 넣어줌.
4. 스택에서 하나를 Pop하여 노드를 하나 가져온다. C 노드가 나왔다.
5. C 노드를 방문했으니 리스트에 추가해준다.
6. C 노드에 연결된 노드들을 가져온다. 연결된 노드들 중에서 방문 안했던 노드들을 스택에 넣어준다. graph_dict['C'] 값은 A와 D 노드. 방문 이력 리스트에서 확인해봤을 때, A노드 값은 있고(방문했고) D 노드 값은 없으니(방문 안했으니) D 노드만 스택에 넣어준다.
7. 스택에서 또 하나를 Pop해준다. D가 나왔다.
8. D를 방문했으니 역시 방문 이력 리스트에 추가해준다.
9. D와 연결된 노드들을 가져온다. graph_dict['D'] 값은 비어있는 리스트이니 스택에 넣어줄 것은 없다.
10. 스택에 하나를 Pop해준다. B 노드가 나왔다.
11. B 노드를 방문 이력 리스트에 추가해준다.
12. 하지만 B 노드는 연결된 노드가 없으므로 별도로 스택에 넣어주는 값이 없다.
13. 스택을 보니 더 이상 방문할 노드가 없다. 끝.
이와 같이 노드를 방문할 때마다 방문 이력 리스트에 노드들을 넣어주고 각 방문마다 연결된 노드들 중에서 미방문한 곳이 있다면 스택에 넣어줘서 Pop하면서 방문지를 결정하는 구조이다.
BFS
너비 우선 탐색은 앞서 DFS의 스택 대신 큐(Queue)를 사용하는 것 외에는 모든 것이 동일하다.
큐를 사용하게 되면 먼저 들어간 노드가 먼저 나오게 된다.
이것을 다르게 표현하면 연결된(인접한) 노드들 전부 먼저 선방문하는 구조가 된다.
예를 들어, DFS는 방문 순서가 A노드에서 B, C 노드는 스택에 넣어놓고 C 노드 먼저 방문하고 C 노드에 연결된 D 노드까지 방문 후 A 노드에 연결된 B 노드를 방문하는 순서였다. 순서 A, C, D, B
하지만 큐에 넣을 경우, A노드에서 B, C 노드를 큐에 넣어놓고 먼저 들어간 B 노드, C 노드 방문 후 C 노드 방문 때, 큐에 넣은 D 노드까지 마지막으로 방문하는 순서로 진행된다. 순서 A, B, C, D
결론
깊이 우선 탐색 단어 말 그대로 한 곳만 집중적으로 파고 들다가 어느 한 쪽 끝까지 도달하면 되돌아가면서(스택의 Pop) 또 다른 곳을 파고 드는 알고리즘이다.
너비 우선 탐색은 연결된 노드들을 먼저 전부 선방문(Dequeue) 후에 더 깊은 노드들을 탐색하는 알고리즘이다.
결론은 스택을 쓰느냐, 큐를 쓰느냐에 따라 DFS, BFS 행동이 결정된다.