그래프 용어: 정점, 간선, 트리, DAG

빌드 도구나 작업 스케줄러 문서를 읽다 보면 이런 문장을 만난다. "작업을 노드로, 'a가 끝나야 b를 시작한다'를 a에서 b로 가는 화살표, 곧 간선으로 그린다. 간선에 방향이 있고 돌아오는 길(순환)이 없는 그래프를 DAG라고 한다." 한 문장에 노드, 간선, 방향, 순환, DAG까지 용어가 다섯 개다. 하나라도 낯설면 그다음 문단이 읽히지 않는다(이 문장은 『한입 알고리즘』 9장 위상 정렬에도 그대로 나온다).

이 용어들은 계산이 필요한 수학이 아니다. 관계를 점과 선으로 그릴 때 붙이는 이름이다. 팔로우 관계, 모듈의 import, 빌드 작업 순서, 지하철 노선이 모두 같은 그림이 된다. 이 Unit은 그 그림의 이름을 하나씩 붙이고, 이름마다 코드로 무엇을 세는지 본다.

그래프: 점과 선

그래프(graph)는 점과 그 점들을 잇는 선으로 된 구조다. 수학에서는 점을 정점(vertex)이라 부르고, 코드와 『한입 알고리즘』·『한입 CS』에서는 노드(node)라고 부른다. 같은 것이다. 이 Unit도 이 문장부터는 노드라고 쓴다. 두 노드를 잇는 선은 간선(edge)이다.

수학 책은 그래프를 이렇게 적는다.

$G = (V, E)$

그래프 $G$는 노드의 모음 $V$(vertex의 V)와 간선의 모음 $E$(edge의 E) 한 쌍이라는 뜻이다. 예를 들어 노드가 a, b, c이고 a–b, b–c가 이어져 있으면 $V = \{a, b, c\}$, $E = \{(a, b), (b, c)\}$다. 노드 3개, 간선 2개짜리 그래프다.

간선에 방향이 있으면 방향 그래프(directed graph)다. 팔로우가 그렇다. a가 b를 팔로우해도 b가 a를 팔로우한다는 보장은 없으니 a → b 화살표 하나만 긋는다. 지하철 노선은 방향이 없다. 두 역이 이어져 있으면 어느 쪽으로든 갈 수 있다. 역 사이에 걸리는 분처럼 간선에 수를 붙이기도 하는데, 이 수를 가중치(weight)라고 한다. 이 책에서는 가중치를 다루지 않는다.

인접 리스트와 차수: 화살표를 센다

그래프를 코드에 담는 가장 흔한 방법은 인접 리스트(adjacency list)다. 노드마다 그 노드에서 나가는 화살표가 가리키는 노드, 곧 이웃의 목록을 둔다. TypeScript에서는 객체나 Map에 노드 → 노드[]로, Python에서는 dict에 담는다. 간선 목록 [a, b]를 한 번 훑으며 adj[a]에 b를 붙이면 된다.

노드에 붙은 간선 수를 차수(degree)라고 한다. 방향 그래프에서는 들어오는 쪽과 나가는 쪽을 따로 센다. 들어오는 간선 수가 진입 차수(in-degree)다. 팔로우 그래프에서 진입 차수는 팔로워 수, 나가는 간선 수(adj[a]의 길이)는 팔로잉 수다.

a → b
a → c
b → c
c → a
d → c

1const nodes = ['a', 'b', 'c', 'd']2const edges: [string, string][] = [['a', 'b'], ['a', 'c'], ['b', 'c'], ['c', 'a'], ['d', 'c']]3const adj: Record<string, string[]> = {}4const indeg: Record<string, number> = {}5for (const v of nodes) {6  adj[v] = []7  indeg[v] = 08}9for (const [a, b] of edges) {10  adj[a].push(b)11  indeg[b] += 112}13for (const v of nodes) {14  console.log(`${v}: 나감 ${adj[v].length}, 들어옴 ${indeg[v]}`)15}16let total = 017for (const v of nodes) total += indeg[v]18console.log(`진입 차수 합 ${total}, 간선 ${edges.length}개`)

a: 나감 2, 들어옴 1
b: 나감 1, 들어옴 1
c: 나감 1, 들어옴 3
d: 나감 1, 들어옴 0
진입 차수 합 5, 간선 5개

방금 본 사실을 식으로 쓰면 이렇다. 시그마(summation, Σ)는 Unit 4에서 본 "모두 더하라"는 기호다.

$\sum_{v} \text{진입 차수}(v) = \text{간선 수}$

"모든 노드 $v$의 진입 차수를 더하면 간선 수와 같다"고 읽는다.

방향 없는 그래프에서는 간선 하나가 양 끝 두 노드의 차수를 하나씩 올린다. 그래서 합이 두 배가 된다.

$\sum_{v} \text{차수}(v) = 2 \times \text{간선 수}$

역 4개가 A–B–C–D로 한 줄에 이어진 노선이면 차수는 1, 2, 2, 1이고 합은 6 = 2 × 3(간선 3개)이다. 방향 없는 그래프를 인접 리스트에 담을 때는 흔히 간선 하나를 양쪽 화살표 두 개(['A', 'B'], ['B', 'A'])로 적는다. 그러면 이 노선은 화살표 6개, 진입 차수 합 6이 된다.

인접 리스트는 간선 목록을 한 번 훑어 만드니, 노드 V개·간선 E개면 O(V + E)(노드 수와 간선 수를 더한 만큼)다(빅오 표기법 노트). 이웃을 꺼낼 때도 그 노드의 목록만 보면 된다.

순환: 출발한 곳으로 돌아오는 길

화살표(또는 선)를 따라가다가 출발한 노드로 돌아오는 길을 순환(사이클, cycle)이라고 한다. 앞의 팔로우 예에도 순환이 있다. a → c → a, 그리고 a → b → c → a다. 서로 팔로우하는 두 사람만 있어도 순환이다.

실무에서 순환은 대개 경고와 함께 나타난다.

• 모듈 import: a.ts가 b.ts를 import하고 b.ts가 다시 a.ts를 import하면 순환 의존이다. 순환 import면 아직 안 만들어진 값을 읽게 된다(모습은 모듈 방식마다 달라서, CommonJS require는 undefined로 보이고, ES 모듈 import는 let·const·class면 ReferenceError가 나며, export function 함수 선언은 미리 만들어져 순환 속에서도 부를 수 있다. 출처는 Node.js 문서: Cycles, MDN: 순환 import, MDN: TDZ, ECMAScript 명세: InitializeEnvironment).
• 작업 순서: a가 b를, b가 a를 기다리면 어느 쪽도 시작할 수 없다. 빌드 도구가 "순환 의존" 오류를 내는 자리다.
• 지하철: 서울 지하철 2호선처럼 마지막 역이 다시 첫 역으로 이어지는 노선은 방향 없는 그래프의 순환이다. 여기서는 문제가 아니라 그냥 모양이다.

순환이 있는지에 따라 그래프에 붙는 이름이 갈린다. 순환이 없는 두 가지 모양이 트리와 DAG다.

트리: 순환 없이 연결된 그래프

어느 두 노드 사이든 선을 따라가는 길이 있으면 그 그래프는 연결돼(connected) 있다. 트리(tree)는 순환이 없고 연결된 그래프다. 폴더 구조가 대표적이다.

src              깊이 0 (뿌리)
├─ app           깊이 1
│  └─ page.tsx   깊이 2 (잎)
├─ lib           깊이 1
│  └─ api.ts     깊이 2 (잎)
└─ main.ts       깊이 1 (잎)

맨 위의 출발 노드를 뿌리(root)라고 한다. 바로 아래에 달린 노드를 자식(child), 바로 위의 노드를 부모(parent)라고 하며, 뿌리를 뺀 모든 노드는 부모가 정확히 하나다. 자식이 없는 노드는 잎(leaf)이다. 뿌리에서 그 노드까지 내려가는 간선 수가 깊이(depth)다. 위 그림에서 page.tsx는 src → app → page.tsx로 간선 2개를 내려가니 깊이 2다. 코드에서는 뿌리를 root라고 쓰는 일이 많다.

DAG: 화살표가 한쪽으로만 흐른다

방향 그래프에 순환이 없으면 DAG(directed acyclic graph)다. "방향(directed)이 있고 순환이 없는(acyclic) 그래프"의 머리글자다. 빌드 작업 순서, 패키지 의존, 스프레드시트의 셀 참조 관계가 모두 DAG여야 한다.

DAG는 트리보다 넓다. 『한입 알고리즘』 9장의 패키지 예에서 web은 ui와 api를 둘 다 기다린다(ui → web, api → web). 트리라면 부모가 하나여야 하니 이 그래프는 트리가 아니다. 그래도 순환이 없으니 DAG다.

왜 순환이 있으면 순서를 못 정하나. 화살표 a → b는 "a가 b보다 먼저"라는 약속이다. 모든 화살표가 앞에서 뒤로 가도록 노드를 한 줄로 세우는 일이 위상 정렬(topological sort)이다. 그런데 a → b → c → a가 있으면 a가 b보다 먼저, b가 c보다 먼저, c가 a보다 먼저다. 이어 붙이면 "a가 a보다 먼저"가 되어 어떻게 세워도 지켜지지 않는다. 그래서 위상 정렬은 DAG에서만 된다. 반대로 DAG는 언제나 위상 정렬이 된다.

진입 차수가 여기서 다시 쓰인다. 진입 차수가 0인 노드는 기다릴 것이 없어 맨 앞에 세울 수 있다. DAG에는 이런 노드가 꼭 있다. 모든 노드의 진입 차수가 1 이상이면, 아무 노드에서 출발해 들어오는 화살표를 거꾸로 따라가도 끝이 나지 않는다. 노드 수는 정해져 있으니 언젠가 지나온 노드로 돌아오고, 그 길이 순환이다.

다만 진입 차수 0인 노드가 하나 있다고 순환이 없는 것은 아니다. utils → ui → web → ui에서 utils는 0이지만 ui와 web이 순환을 이룬다. 진입 차수 0인 노드를 꺼내고, 그 노드에서 나가는 화살표를 지우고, 새로 0이 된 노드를 또 꺼내는 일을 끝까지 되풀이해야 순환이 있는지 판단할 수 있다. 이것이 칸 알고리즘(Kahn's algorithm)이고, 『한입 알고리즘』 9장에서 코드로 따라간다. 다 꺼냈는데 남은 노드가 있으면 순환이 있다.

AI가 짠 그래프 함수 검토하기

그래프 함수는 이름 하나만 헷갈려도 오류 없이 엉뚱한 값을 낸다. 검토 기준은 앞 절에 다 나왔다. 팔로워 수가 화살표의 어느 끝을 세는 값인지(2절), 트리에서 간선과 노드의 개수가 어떤 관계인지(4절), 순환이 없다고 판정하려면 진입 차수 0인 노드를 어디까지 따라가야 하는지(5절)를 줄마다 견준다.

이 Unit이 쓰이는 곳

• 『한입 알고리즘』 4장 큐와 BFS: 격자의 칸을 노드로, 붙은 두 칸을 간선으로 보고 출발 칸부터 거리를 한 겹씩 매긴다. 마지막 절은 트리를 깊이별로 묶어 꺼낸다.
• 『한입 알고리즘』 5장 DFS와 백트래킹: 폴더 트리를 한 갈래씩 끝까지 내려갔다 돌아오며 용량을 더한다. 트리가 깊으면 재귀가 멈추는 이유도 여기서 본다.
• 『한입 알고리즘』 8장 힙: 이진 힙(binary heap)은 위층부터 빈틈없이 채운 이진 트리(binary tree)를 배열 하나에 담은 것이다.
• 『한입 알고리즘』 9장 위상 정렬: 의존을 간선으로 그리고, 진입 차수 0인 노드부터 꺼내며(칸 알고리즘) 순환을 잡아낸다.
• 『한입 알고리즘』 11장 트라이: 글자 하나가 간선 하나인 트리다. 뿌리에서 걸어 내려간 글자들이 단어가 된다.
• 『한입 CS』 8장 데이터베이스: B-트리 인덱스는 뿌리 페이지에서 잎 페이지로 내려가며 찾는다. 트리의 높이가 읽는 페이지 수다.
• 『한입 CS』 9장 코드는 어떻게 실행될까: 파서가 만든 AST(추상 구문 트리)에서 곱하기가 더하기보다 아래에 달리는 것이 우선순위다.

용어 정리는 그래프, BFS, DFS, 트리 순회 노트에 있다.

이 Unit으로 『개발 수학』이 끝난다. Unit 1의 2진수부터 이 Unit의 그래프 용어까지는 모두 『한입 알고리즘』·『한입 CS』에서 막히기 쉬운 수학이었다. 각 Unit 끝의 "이 Unit이 쓰이는 곳" 목록에서 읽다 막혔던 장을 골라 다시 읽어 보자.

n = 4 → 최대 ?개
n = 5 → 최대 ?개