이 글은 고전적인 컴퓨터 과학 개념을 Ruby로 실제 문제 해결에 적용하는 방법을 다루는 "실전 컴퓨터 과학(Practical Computer Science)" 시리즈의 연속 편입니다.
오늘은 그래프 이론(Graph Theory)에 대해 이야기해 보겠습니다.
이진 트리(binary tree)라는 자료구조를 들어보셨을 겁니다. 이진 트리는 다음과 같은 모습을 하고 있죠.
사실 이진 트리는 그래프의 특수한 형태 중 하나입니다. 즉, 그래프가 얼마나 폭넓게 활용되는지 짐작할 수 있는 부분이죠.
먼저 그래프 이론의 기본 개념을 살펴본 뒤, 실제 활용 사례와 Ruby에서의 구현 방법까지 차근차근 알아보겠습니다!
그래프의 기본 개념
그래프는 두 가지 요소로 구성됩니다.
- 노드(Node, 정점(vertex)이라고도 함)
- 엣지(Edge)
노드는 그래프에서 하나의 요소를 나타냅니다. 예를 들어 지도를 그래프로 표현한다면 도시나 거리가 노드가 되고, 엣지는 노드 사이의 연결 관계를 나타냅니다.
컴퓨터 과학이나 수학 교재를 보면 그래프가 다음 공식으로 정의된 것을 볼 수 있습니다: G(V, E)
여기서 G는 그래프(Graph), V는 정점(vertex)의 집합, E는 엣지(edge)의 집합을 의미합니다.
그래프는 방향 그래프(directed graph)와 무방향 그래프(undirected graph)로 나눌 수 있습니다. 말 그대로 한 방향으로만 이동할 수 있는지(방향 그래프), 양방향으로 이동할 수 있는지(무방향 그래프)의 차이입니다.
가장 널리 사용되는 그래프 유형은 DAG(Directed Acyclic Graph, 방향 비순환 그래프)입니다. Acyclic(비순환)은 순환이 없다는 뜻으로, 되돌아가는 경로가 존재하지 않습니다.
그래프의 활용 분야
기본 개념을 살펴봤으니, 이제 그래프가 실제로 어떤 용도로 쓰이는지 알아보겠습니다.
그래프를 활용하면 다음과 같은 작업을 할 수 있습니다.
- 두 지점 간의 최단(또는 최장) 경로 찾기
- 두 대상 간의 연관 여부 확인하기
- 추천 엔진 만들기
- 의존성 분석하기
그 외에도 목적지까지의 최적 경로를 찾는 예시(GPS 기기를 떠올리면 됩니다)가 있습니다.
그래프 구현 및 사용 방법
직접 그래프를 구현할 수도 있지만, 이 글에서는 이미 구현체를 제공하는 RGL 젬(gem)을 사용하겠습니다.
RGL로 기본적인 그래프를 만드는 방법은 다음과 같습니다.
require 'rgl/adjacency' graph = RGL::DirectedAdjacencyGraph.new graph.add_edge 1,2 graph.add_edge 3,4 graph.add_edge 1,4 graph.add_edge 4,3
이 코드는 아래와 같은 그래프를 생성합니다.
다음과 같이 그래프를 시각적으로 표현할 수도 있습니다.
require 'rgl/dot' graph.print_dotted_on
이 메서드의 출력 결과를 dot 언어를 처리할 수 있는 사이트에 붙여넣으면 그림으로 확인할 수 있습니다.
또는 Graphviz를 로컬 머신에 설치해 직접 이미지를 생성하는 방법도 있습니다.
이제 그래프가 준비되었으니, 그래프를 순회(traverse)하면서 원하는 정보를 얻어볼 차례입니다.
그래프 탐색에는 두 가지 기본 알고리즘이 있습니다.
- 너비 우선 탐색(BFS, Breadth-First Search)
- 깊이 우선 탐색(DFS, Depth-First Search)
BFS는 시작점에 가까운 노드부터 먼저 방문하고, DFS는 각 노드에서 가능한 한 깊게 들어간 후 탐색을 이어갑니다. 이 알고리즘들은 스택(stack) 자료구조를 이용해 구현할 수 있습니다.
RGL 젬에는 이러한 알고리즘이 이미 구현되어 있습니다.
require 'rgl/traversal' graph.bfs_iterator.to_a # [1, 2, 4, 3] graph.dfs_iterator.to_a # [1, 4, 3, 2]
앞서 만든 그래프를 다시 보면서, 눈으로(원한다면 손가락으로도!) 이 알고리즘들이 따라간 경로를 추적해 보세요. 어떤 일이 벌어지고 있는지 감을 잡는 데 큰 도움이 됩니다.
가중치 그래프
그래프에 가중치(weight) 형태로 추가 정보를 담으면 훨씬 더 유용하게 활용할 수 있습니다.
가중치는 엣지, 즉 두 노드("정점"이라고도 함) 사이의 경로에 부여되며, 한 지점에서 다른 지점으로 이동하는 비용을 나타냅니다.
예를 들어, 한 나라의 지도를 그래프로 표현하고 최대한 빠른 시간 안에 특정 목적지에 도달하고 싶다면, 가중치는 두 도시 사이의 거리를 의미하게 됩니다.
반면 컴퓨터 네트워크라면, 가중치는 특정 네트워크에 도달하기 위해 거쳐야 하는 홉(hop) 수를 나타낼 수 있습니다.
"컴퓨터 네트워킹에서 홉(hop)은 출발지와 목적지 사이 경로의 한 구간을 의미합니다. 데이터 패킷은 출발지에서 목적지로 이동하는 동안 브리지, 라우터, 게이트웨이를 통과합니다. 패킷이 다음 네트워크 장치로 전달될 때마다 하나의 홉이 발생합니다." – 위키백과(Wikipedia)
가중치 그래프의 코드 예제는 다음과 같습니다.
graph = RGL::DirectedAdjacencyGraph.new
graph.add_vertices "Los Angeles", "New York", "Chicago", "Houston", "Seattle"
edge_weights =
{
["New York", "Los Angeles"] => 2445,
["Los Angeles", "Chicago"] => 2015,
["Los Angeles", "Houston"] => 1547,
["Chicago", "Houston"] => 939,
["Seattle", "Los Angeles"] => 1548
}
edge_weights.each { |(city1, city2), w| graph.add_edge(city1, city2) }
이제 한 지점에서 다른 지점까지의 최단 경로를 검색할 수 있습니다. 바로 다음 섹션의 주제이기도 합니다!
최단 경로 찾기
그래프 내에서 최단 경로를 찾는 대표적인 알고리즘은 "다익스트라 최단 경로(Dijkstra's Shortest Path)" 알고리즘입니다.
가중치 그래프가 주어졌을 때, 다익스트라 알고리즘으로 다음 질문을 해결할 수 있습니다.
"A 지점에서 B 지점까지 가장 빠르게 이동하는 방법은 무엇일까?"
RGL 젬을 사용한 코드 예제입니다.
p graph.dijkstra_shortest_path(edge_weights, "New York", "Houston") # ["New York", "Los Angeles", "Houston"]
그래프에 담긴 정보를 바탕으로 뉴욕에서 휴스턴까지의 최단 경로를 알려줍니다.
정리
이번 글에서는 그래프 자료구조가 무엇인지, 그리고 RGL 젬으로 어떻게 활용하는지 배웠습니다.
또한 DFS, BFS, 다익스트라 알고리즘처럼 그래프를 다룰 때 자주 쓰이는 대표 알고리즘들도 함께 살펴봤습니다.
이 글이 도움이 되었다면 주변에 공유해 주세요. 더 많은 사람들이 함께 즐길 수 있습니다 🙂