그래프

그래프는 무엇과 무엇이 이어져 있는지를 담는 자료구조입니다. 항목마다 점을 하나씩 찍어 두고, 이어진 짝끼리 선을 긋습니다. 줄로 세우거나 계층으로 나누어서는 적기 힘든 얽힌 관계를 얽힌 채로 적습니다. 수치를 그린 막대그래프도 같은 이름으로 부르지만, 이 글이 다루는 것은 관계를 담는 쪽입니다.

쉽고 빠른 이해

그래프는 항목 사이의 이어짐을 담는 자료구조입니다. 지하철 노선도가 그 꼴입니다. 역이 점입니다. 한 정거장 거리로 붙어 있는 역끼리 선이 그어져 있습니다.

이어짐을 표 한 장에 늘어놓으면 "여기서 저기까지 갈 수 있나" 를 물을 때마다 표를 처음부터 다시 훑게 됩니다. 이어진 짝을 점 옆에 붙여 두면 같은 질문을 선만 따라가며 풉니다.

1. 항목마다 점을 하나씩 둡니다
2. 이어진 짝끼리 선을 긋습니다
3. 궁금한 점에서 출발해 선을 따라가며 닿는 점을 모읍니다

대가가 있습니다. 점에 순서가 없어서 "그다음 것" 이 저절로 정해지지 않습니다. 어디부터 볼지, 이미 본 점을 어떻게 기억할지를 쓰는 쪽이 매번 정해야 합니다.

상세

도시를 잇는 항공 노선을 떠올려 봅니다. 서울·부산·제주·도쿄 네 도시가 있습니다. 직항이 있는 도시끼리만 이어져 있습니다.

어느 도시에서 어느 도시로 바로 갈 수 있는지는 도시 이름만 봐서는 알 수 없습니다. 이어짐을 따로 적어 두어야 합니다.

이어짐을 목록 한 줄로만 적어 두면 "여기서 저기까지 갈 수 있나" 를 물을 때마다 목록 전체를 다시 훑게 됩니다. 이어진 상대를 항목 옆에 붙여 두면 같은 질문이 선을 따라가는 일로 바뀝니다.

그래프는 그 이어짐을 담는 자료구조입니다. 담는 것은 둘뿐입니다. 항목 하나를 가리키는 점과, 두 점이 이어져 있다는 사실을 가리키는 선입니다.

점이 노드입니다. 정점도 같은 것을 가리키는 말입니다. 노드와 노드를 잇는 선이 간선입니다.

앞의 네 도시를 그리면 이렇습니다.

flowchart TD
    S["서울"] --- B["부산"]
    S --- J["제주"]
    B --- J
    S --- T["도쿄"]

서울은 셋 모두와 이어져 있습니다. 도쿄는 서울 하나와만 이어져 있습니다. 부산에서 도쿄로 가는 간선은 없습니다.

그래도 부산에서 서울을 거쳐 도쿄까지 갈 수는 있습니다. 한 번에 갈 수 있느냐와 결국 닿을 수 있느냐는 다른 질문입니다.

한 노드에 붙은 간선의 수가 차수입니다. 위 그림에서 서울의 차수는 셋입니다. 도쿄의 차수는 하나입니다. 차수가 높은 노드는 그만큼 많은 길이 지나가는 목이 됩니다.

간선에 붙는 방향과 가중치

간선에는 두 가지가 더 붙을 수 있습니다. 어느 쪽으로 흐르는지를 나타내는 방향과, 그 이어짐을 지나는 데 드는 값입니다. 무엇을 담느냐에 따라 붙이기도 하고 안 붙이기도 합니다.

방향이 붙은 간선은 한쪽으로만 흐릅니다. 팔로우 관계가 그렇습니다. 민수가 지연을 팔로우해도 지연이 민수를 팔로우한다는 뜻은 아닙니다. 이런 그래프가 방향 그래프입니다.

민수가 지연을, 지연이 태호를, 태호가 민수를 팔로우합니다. 그리면 이렇습니다.

flowchart TD
    N1["민수"] --> N2["지연"]
    N2 --> N3["태호"]
    N3 --> N1

화살표를 따라가면 민수에서 출발해 민수로 돌아옵니다. 이렇게 제자리로 돌아오는 길이 사이클입니다.

사이클이 하나도 없는 방향 그래프는 DAG(Directed Acyclic Graph, 방향 비순환 그래프)라는 이름을 따로 받습니다. 되돌아오는 길이 없으니 노드를 한 줄 순서로 늘어놓을 수 있습니다. 설치 순서나 빌드 순서가 이 모양입니다.

간선에 붙는 값이 가중치입니다. 도시 사이의 거리, 회선의 지연, 작업에 드는 비용처럼 "이 이어짐을 쓰는 데 얼마가 드는가" 를 적습니다. 가중치가 있으면 길이 있느냐뿐 아니라 어느 길이 싼가까지 물을 수 있습니다.

트리·연결 리스트와 갈리는 대목

트리와 연결 리스트도 노드와 간선으로 이루어집니다. 그래프와 다른 것은 간선을 긋는 데 조건이 붙어 있다는 점입니다. 조건을 하나씩 풀면 그래프가 됩니다.

연결 리스트는 노드마다 다음 노드 하나만 가리킵니다. 트리는 여럿을 가리킬 수 있습니다.

대신 트리는 한 노드로 들어오는 간선이 하나뿐입니다. 사이클도 없습니다. 그래프에는 그런 제한이 없습니다.

제한이 풀린 대가는 보장이 사라지는 것입니다. 트리에서는 위로 거슬러 올라가면 반드시 뿌리에 닿습니다. 그래프에서는 따라가다 같은 노드로 되돌아올 수 있습니다. 그래서 그래프를 훑는 절차는 이미 본 노드를 기억해 두지 않으면 영영 끝나지 않습니다.

담을 관계가 한 줄로만 이어지거나 위아래 계층으로만 갈라지면 리스트나 트리 쪽이 단순합니다. 그래프는 그 제한이 실제 관계와 안 맞을 때 고르는 모양입니다.

인접 행렬과 인접 리스트

이어짐을 메모리에 적어 두는 방법은 크게 둘입니다. 어느 쪽을 고르느냐에 따라 같은 그래프라도 드는 공간과 질문에 답하는 비용이 달라집니다.

첫째는 인접 행렬입니다. 노드를 가로와 세로에 늘어놓습니다. 칸마다 이어졌는지를 적습니다. 앞의 항공 노선을 이렇게 적으면 다음과 같습니다.

이 노선에는 자기 자신으로 돌아오는 간선이 없으므로 대각선 네 칸은 모두 ✗ 입니다. 방향이 없어서 서울-부산 칸과 부산-서울 칸은 늘 같습니다.

서울과 도쿄가 이어졌는지는 두 이름이 만나는 칸 하나만 보면 됩니다. 대신 이어지지 않은 짝도 칸을 하나씩 차지합니다.

위 표는 칸이 열여섯입니다. 그중 여덟이 ✗ 입니다. 노드가 늘어도 간선이 그만큼 늘지 않으면 ✗ 칸의 비율은 계속 커집니다.

둘째는 인접 리스트입니다. 노드마다 칸을 하나씩 둡니다. 그 칸에 이어진 상대만 붙입니다. 이어지지 않은 짝은 어디에도 적히지 않습니다.

같은 항공 노선을 이렇게 적으면 네 줄이 됩니다.

오른쪽 칸에 적힌 상대는 순서가 아니라 목록입니다. 서울 줄은 "서울에서 부산으로, 부산에서 제주로" 가 아니라 "서울에 부산·제주·도쿄가 붙어 있다" 는 뜻입니다.

칸은 대개 배열로 둡니다. 거기 붙는 상대 목록은 배열이나 연결 리스트로 둡니다.

도쿄 칸에는 서울 하나만 붙어 있습니다. 행렬에서는 도쿄 줄이 네 칸을 차지했습니다.

둘의 비용을 나란히 놓으면 이렇습니다. 노드 수를 V, 간선 수를 E 로 적습니다.

O(V²) 처럼 적은 것은 V 가 늘 때 비용이 대략 어떻게 늘어나는지를 적는 표기입니다. 이 늘어나는 꼴을 재는 잣대가 시간 복잡도입니다. O(차수) 는 그 노드에 붙은 간선 수만큼 걸린다는 뜻입니다.

가르는 기준은 간선이 얼마나 빽빽한가입니다. 노드는 많은데 간선이 드물면 행렬은 빈칸으로 가득 차므로 리스트가 낫습니다. 거의 모든 짝에 간선이 있으면 행렬의 빈칸이 얼마 없습니다. 두 노드가 이어졌는지를 한 번에 답하는 이점만 남습니다.

그래프 위에서 도는 연산

그래프를 담아 두는 까닭은 그 위에서 질문에 답하기 위해서입니다. 질문은 몇 가지 꼴로 굳어져 있습니다. 꼴마다 이름 붙은 절차가 있습니다.

한 노드에서 출발해 닿는 노드를 모두 모으는 일이 탐색입니다. 가까운 노드부터 한 겹씩 넓혀 가면 너비 우선 탐색입니다. 한 갈래를 끝까지 파고들었다 되돌아 나오면 깊이 우선 탐색입니다. 앞의 그림에서 부산이 도쿄에 닿는지를 묻는 것이 이 질문입니다.

가중치가 붙어 있으면 가장 싼 길을 묻게 됩니다. 이것이 최단 경로 문제입니다. 가중치가 음수가 아닐 때 쓰는 대표적인 절차가 다익스트라 알고리즘입니다.

방향 그래프에서는 순서를 묻습니다. 화살표를 거스르지 않는 한 줄 순서를 뽑는 절차가 위상 정렬입니다. 앞의 DAG 가 이 절차를 쓰는 모양입니다. 사이클이 있으면 그런 순서가 없으므로, 이 절차는 사이클을 찾아내는 일도 겸합니다.

어느 절차든 이미 본 노드를 표시해 두는 일이 함께 갑니다. 그래프는 되돌아오는 길을 허용하므로, 표시가 없으면 같은 노드를 끝없이 다시 방문합니다.

그래프로 적히는 실제 관계

백엔드에서 만나는 그래프는 대개 그래프라는 이름을 달고 있지 않습니다. 노드와 간선이 무엇을 가리키는지만 다르고 모양은 같습니다.

첫째 줄이 소셜 그래프입니다. 친구의 친구를 찾는 질문이 곧 탐색입니다. 둘째 줄은 의존성 그래프입니다.

설치 순서를 정하려면 위상 정렬이 필요합니다. 두 패키지가 서로를 필요로 하면 사이클이라 순서를 못 뽑습니다.

그래프 데이터베이스는 관계 자체를 저장하고 질의하라고 만든 제품입니다. 표를 여러 번 이어 붙이는 대신 간선을 따라가는 질의를 직접 받습니다.

그래프가 담지 않는 정보

그래프가 담는 것은 이어짐뿐입니다. 왜 이어졌는지, 언제 이어졌는지, 그 이어짐이 아직 살아 있는지는 이 모양에 들어 있지 않습니다. 그런 값이 필요하면 노드와 간선에 속성으로 따로 붙입니다.

순서도 담지 않습니다. 배열에는 첫째 칸과 둘째 칸이 있지만 그래프의 노드에는 그런 차례가 없습니다. "어느 노드부터 볼 것인가" 는 구조가 아니라 훑는 절차가 정합니다.

그래서 같은 그래프를 두 절차로 훑으면 결과 순서가 다르게 나옵니다. 답이 여럿인 질문에 그래프는 답을 하나로 좁혀 주지 않습니다. 좁히는 규칙은 쓰는 쪽이 세워야 합니다.

관련 항목

그래프를 이루는 구성 요소

노드 · 간선 · 정점 · 가중치 · 차수 · 경로 · 사이클 · 이웃 노드

그래프의 하위 종류

방향 그래프 · 무방향 그래프 · 가중 그래프 · DAG · 트리 · 이분 그래프 · 완전 그래프 · 부분 그래프 · 신장 트리 · 다중 그래프

그래프를 메모리에 담는 표현

인접 행렬 · 인접 리스트 · 간선 리스트 · 배열 · 연결 리스트 · 해시테이블

그래프 위에서 도는 알고리즘

너비 우선 탐색 · 깊이 우선 탐색 · 위상 정렬 · 다익스트라 알고리즘 · 벨만-포드 알고리즘 · 크루스칼 알고리즘 · 사이클 검출 · 연결 요소 · 유니온 파인드

그래프로 적어 두고 푸는 계산 문제

최단 경로 · 최소 신장 트리 · 최대 유량 · 외판원 순회 · 그래프 채색 · 이분 매칭

그래프 탐색이 빌려 쓰는 자료구조

스택 · 큐 · 우선순위 큐 · 힙 · 집합

절차의 비용을 재는 잣대

시간 복잡도 · 공간 복잡도 · 점근 표기법

그래프로 관계를 적는 시스템

의존성 그래프 · 소셜 그래프 · 호출 그래프 · 제어 흐름 그래프 · 빌드 그래프 · 지식 그래프

그래프를 저장하고 질의하는 제품

그래프 데이터베이스 · Neo4j · 트리플 스토어 · SPARQL · Cypher