§ 1 · 정점과 간선그래프란
그래프(graph)는 관계를 전문으로 다루는 자료구조다. Facebook 친구 관계를 2차원 배열로 저장하면 Alice의 친구를 찾는 데 O(N)이 든다. 그래프를 쓰면 O(1)이다.
그래프에서 각 노드를 정점(vertex), 각 연결선을 간선(edge)이라 한다. 간선으로 이어진 정점들은 서로 인접(adjacent)하다고 한다.
friends = { "Alice" => ["Bob", "Diana", "Fred"], "Bob" => ["Alice", "Cynthia", "Diana"], "Diana" => ["Alice", "Bob", "Fred"] } friends["Alice"] # => O(1)로 친구 목록
§ 2 · 큐로 펼치기너비 우선 탐색
LinkedIn의 2단계·3단계 연결처럼, 한 정점에서 도달 가능한 전체 네트워크를 찾으려면 그래프를 순회해야 한다. 너비 우선 탐색(BFS, breadth-first search)은 큐를 써서 다음에 처리할 정점을 추적한다.
① 시작 정점을 큐에서 꺼내 "현재 정점"으로 삼고 방문 표시한다.
② 현재 정점의 방문하지 않은 인접 정점을 모두 방문 표시하고 큐에 넣는다.
③ 방문할 인접 정점이 없으면, 큐에서 다음 정점을 꺼내 현재 정점으로 삼는다.
④ 큐가 비면 알고리즘이 끝난다.
§ 3 · 정점이 곧 데이터그래프 데이터베이스
데이터를 그래프 형태로 저장하는 데이터베이스가 있다. Cindy의 친구 4명의 정보를 가져온다고 하자.
- 관계형 데이터베이스 — Friendships 테이블에서 친구 ID를 찾고, 각 ID로 Users 테이블을 이진 탐색(O(log N)). M명이면
O(M log N). - 그래프 데이터베이스 — 각 정점이 사용자 정보를 통째로 담는다. Cindy에서 간선을 따라가면 끝 — N명이면
O(N).
Neo4j, ArangoDB, Apache Giraph가 오픈 소스 그래프 데이터베이스의 예다. 다만 그래프 데이터베이스가 항상 최적은 아니니, 애플리케이션마다 신중히 평가해야 한다.
§ 4 · 간선에 숫자가중 그래프
가중 그래프(weighted graph)는 간선에 추가 정보—숫자—를 붙인다. 도시 지도라면 간선의 숫자는 도시 간 거리나 비행기 요금이 된다. 방향 가중 그래프도 가능하다 — Dallas→Toronto는 $138, Toronto→Dallas는 $216처럼.
class City attr_accessor :name, :routes def initialize(name) @name = name @routes = {} # 인접 도시 → 가격 end def add_route(city, price) @routes[city] = price end end
가중 그래프로 최단 경로 문제(shortest path problem)를 풀 수 있다 — "Atlanta에서 El Paso로 가장 적은 비용으로 가는 길은?"
§ 5 · 최단 경로다익스트라 알고리즘
1959년 Edsger Dijkstra가 발견한 다익스트라 알고리즘(Dijkstra's algorithm)이 최단 경로 문제를 푼다.
- 시작 정점을 현재 정점으로 삼는다.
- 현재 정점의 인접 정점들로 가는 가중치를 계산해 테이블에 기록한다(더 싸면 갱신).
- 시작 정점에서 가장 저렴한 미방문 정점을 다음 현재 정점으로 삼는다.
- 모든 정점을 방문할 때까지 반복한다.
같은 알고리즘을 간선 가중치가 거리나 시간일 때 적용하면, GPS의 경로 안내가 된다.
§ 6 · 정리이 장이 남긴 것
그래프는 관계를 다루는 극도로 강력한 도구다. 코드를 빠르게 하는 것을 넘어 까다로운 문제를 풀어준다. 지금까지 우리는 줄곧 속도—시간 복잡도—를 측정했다. 그러나 효율성은 다른 방식으로도 잴 수 있다. 다음 장에서는 메모리, 즉 공간 복잡도를 본다.