Ch4-1. 그래프
코딩 인터뷰 완전 분석(저 : 게일 라크만 맥도웰) 참조
그래프
앞서 이야기한 트리는 그래프의 한 종류이다. 하지만 모든 그래프가 트리는 아니다.
트리는 사이클이 없는 하나의 연결 그래프라고 말할 수 있다.
그래프는 노드와 노드를 연결하는 간선을 하나로 모아 놓은 것이다.
그래프에는 방향성이 있을 수도 있고 없을 수도 있다. 방향성이 있는 간선은 일방통행, 방향성이 없는 간선은 양방향 통행이라고 생각하면 된다.
모든 노드 쌍에 대해 경로가 존재하는 그래프를 “연결 그래프”라고 한다.
그래프에는 사이클이 있을 수도 없을 수도 있다. 사이클이 없는 그래프를 “비순환 그래프(acyclic graph)”라고 한다.
그래프 탐색
깊이 우선 탐색(depth-first search)
깊이 우선 탐색(DFS)은 루트 노드에서 시작해서 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방법이다.
즉, a 노드를 방문한 뒤 a 와 이웃한 노드 b를 방문했다면, a 와 인접한 다른 노드를 방문하기 이전에 b 의 이웃 노드들을 전부 방문해야 한다.
전위 순회를 포함한 트리 순회는 모두 DFS의 한 종류이다. DFS는 그래프에서 모든 노드를 방문하고자 할 때 더 선호되는 편이다.
너비 우선 탐색(breadth-first search)
너비 우선 탐색(BFS)은 a 노드에서 시작했을 때, a 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다.
즉, BFS는 a 에서 시작해서 거리에 따라 단계별로 탐색한다고 봉 수 있다.
BFS는 재귀적으로 동작하지 않는다. BFS는 큐를 이용해서 방문할 노드를 저장하고 이를 탐색한다.
양방향 탐색(bidirectional search)
양방향 탐색은 출발지와 도착지 사이의 최단 경로를 찾을 때 사용된다.
출발지와 도착지 두 노드에서 동시에 너비 우선 탐색을 수행한 뒤, 두 탐색 지점이 충돌하는 경우에 경로를 찾는 방식이다.
노드 s에서 노드 t까지 너비 우선 탐색으로 4단계를 거쳐야하는 경우를 생각해보자.
s와 t 두 지점에서 동시에 탐색을 시작하면 각 노드의 2단계 이후에 탐색 지점이 충돌한다.
이를 수행시간으로 비교해보자.
전통적인 너비 우선 탐색을 통해 k개의 노드를 탐색하는 과정을 d번 반복하면 O(kd) 개의 노드를 탐색해야 한다.
양방향 탐색을 이용한다면 두 노드의 중간 지점 정도인 d/2 반복에서 충돌할 것이다.
따라서 s와 t 각각에서 방문하게 될 노드의 수는 대략 kd/2 개가 될 것이고, 전체 노드는 2*kd/2, O(kd/2) 의 수행시간이 된다.
kd/2 * kd/2 = kd 인 것을 생각해 보면, 양방향 탐색은 일반적인 너비 우선 탐색보다 kd/2 만큼 더 빠르다.