그래프 - 관계 자체가 데이터다

지하철 노선도를 보면 역 이름보다 역과 역을 잇는 선이 먼저 눈에 들어온다. 이 글이 다루는 그릇이 정확히 그것이다.

관계가 곧 데이터다

지금까지 본 그릇은 전부 값을 담았다. 배열은 값을 나란히, 트리는 값을 크기 순으로, 힙은 값을 급한 순으로 담았다. 담는 방식은 달라도 담기는 건 값이었다.

그래프는 다르다. 값들 사이의 관계가 담기는 내용이다.

노선도에서 “강남역”이라는 이름은 별 정보가 없다. 값은 강남역이 어느 역들과 이어져 있는가에 있다. 역 목록만 있고 선이 없으면 그건 노선도가 아니다.

그래서 그래프로 풀리는 문제는 하나같이 “무엇이 무엇과 이어져 있나” 꼴이다. 누가 누구와 친구인가, 어느 서비스가 어느 서비스를 부르는가, 어느 작업이 어느 작업 뒤에 와야 하는가.

점과 선

구성은 단순하다. **점(정점)과 그 점들을 잇는 선(간선)**이 전부다.

역이 점이고 구간이 선이다. 사람이 점이고 친구 관계가 선이다. 지금까지 본 트리도 사실 그래프의 한 종류다. 위아래가 정해져 있고 되돌아오는 길이 없는 그래프가 트리다.

이 말은 뒤집으면 이렇게 된다. 그래프는 트리에서 제약을 걷어낸 것이다. 위아래가 없어도 되고, 한 점에 여러 갈래가 들어와도 되고, 돌아서 제자리로 와도 된다. 제약이 없어진 만큼 표현할 수 있는 게 늘고, 다루기는 어려워진다.

세 가지가 갈린다

그래프라고 다 같은 그래프가 아니다. 셋을 먼저 갈라놓아야 문제를 제대로 읽는다.

방향이 있나. 친구 관계는 양쪽이 같지만, “A가 B를 팔로우한다”는 한쪽이다. 노선도는 대개 양방향이지만 일방통행 도로는 아니다. 서비스 호출도 한쪽이다.

선에 값이 있나. 역과 역 사이에 걸리는 시간이 다르면 그 값을 선에 적어둔다. 이걸 가중치라고 하고, 최단 경로가 “역 수가 적은 길”이 아니라 “시간이 적은 길”로 바뀐다.

돌아오는 길이 있나. 출발한 곳으로 되돌아오는 길이 있으면 순환이 있다고 한다. 순환이 있느냐 없느냐가 실무에서 특히 크게 갈리는데, 이유는 뒤에서 본다.

담는 두 가지 방법

그래프를 메모리에 담는 방법은 크게 둘이다.

표로 담는다. 점이 n개면 n × n 표를 만들고 “i와 j가 이어져 있나”를 칸에 적는다. 두 점이 이어졌는지 한 번에 확인된다. 대신 점이 1만 개면 칸이 1억 개인데, 실제 선은 몇만 개뿐일 수 있다. 대부분이 빈칸이다.

점마다 이웃 목록을 든다. 강남역이 들고 있는 목록에 이웃 역들만 적는다. 있는 선만큼만 자리를 쓴다. 대신 “A와 B가 이어졌나”를 물으면 A의 목록을 훑어야 한다.

실무에서 만나는 그래프는 대개 선이 희박하다. 사람이 수백만 명이어도 한 사람의 친구는 수백 명이다. 그래서 뒤엣것이 기본값이고, 표로 담는 건 점이 적고 선이 빽빽할 때 쓴다.

가까운 곳부터: 너비 우선

그래프에서 하는 일은 결국 돌아다니는 것이다. 돌아다니는 방식이 둘 있는데, 놀랍게도 둘의 차이는 앞에서 본 그릇 두 개 중 무엇을 쓰느냐뿐이다.

너비 우선은 가까운 곳을 전부 본 다음 그다음 층으로 간다. 한 정거장 거리를 다 보고, 두 정거장 거리를 다 보고.

이렇게 하려면 “다음에 갈 곳”을 먼저 온 것부터 꺼내야 한다. 큐를 쓴다.

너비 우선이 값을 하는 자리는 분명하다. 선에 값이 없을 때 최단 경로는 이걸로 나온다. 가까운 것부터 봤으니 처음 닿은 길이 가장 짧은 길이다. “세 다리 건너 아는 사람”도 이걸로 센다.

파고들기: 깊이 우선

깊이 우선은 반대다. 한 갈래를 끝까지 파고들었다가 막히면 돌아 나와 다음 갈래로 간다.

이렇게 하려면 “다음에 갈 곳”을 마지막에 넣은 것부터 꺼내야 한다. 스택을 쓴다. 재귀로 짜면 코드에 스택이 안 보이는데, 그건 없어진 게 아니라 함수 호출 스택이 대신 하고 있는 것이다.

깊이 우선은 “길이 있나”를 확인하거나 모든 경우를 훑어야 할 때 쓴다. 그리고 다음에 볼 순환 찾기가 여기 걸린다.

⚠️ 둘 다 한 번 본 곳을 표시해 둬야 한다. 안 그러면 순환이 있는 그래프에서 영원히 돈다. 트리에는 없던 걱정인데, 돌아오는 길이 생기면서 새로 생긴 문제다.

순환을 찾는 일

실무에서 그래프를 꺼내 드는 가장 흔한 이유는 최단 경로가 아니다. 순환이 있는지 보는 것이다.

순환이 있으면 “무엇부터 해야 하나”에 답이 없어진다. A가 끝나야 B를 하는데 B가 끝나야 A를 할 수 있으면, 어느 쪽도 시작할 수 없다. 이 모양이 이름을 바꿔가며 도처에 나온다.

• 빌드 순서 - 모듈 A가 B를 참조하고 B가 A를 참조하면 컴파일 순서가 안 정해진다
• 패키지 의존성 - 설치 순서가 안 정해진다
• 데이터베이스 락 - 서로가 서로를 기다리면 교착 상태다
• 의존성 방향 - 상위 모듈과 하위 모듈이 서로를 알면 둘 다 따로 못 쓴다

순환이 없는 방향 그래프라면 순서를 하나 정할 수 있다. 이걸 위상 정렬이라 부르고, 빌드 도구와 패키지 관리자가 매번 하는 일이 이거다. “순환 의존이 발견되었습니다”라는 에러는 위상 정렬이 실패했다는 말이다.

실무에서: 의존 관계로 읽는다

그래프 자료구조를 직접 짜는 일은 드물다. 대신 눈앞의 문제가 그래프라는 걸 알아보는 것이 값을 한다.

마이크로서비스로 나눈 시스템은 그 자체가 호출 그래프다. 이렇게 보면 평소 말로만 하던 이야기가 구조로 읽힌다.

• 한 점에 선이 몰려 있으면 거기가 단일 장애점이다. 그 서비스가 죽으면 이어진 것이 전부 멈춘다.
• 순환이 있으면 따로 배포할 수 없다. 서비스로 나눠놓고 같이만 배포한다면 이 순환을 못 끊은 것이다.
• 경로가 길면 한 요청이 여러 홉을 지난다. 지연이 더해지고, 어디서 느려졌는지 찾기 어려워진다.

같은 눈으로 코드도 읽힌다. 모듈 의존 그래프에서 화살표가 한 방향으로만 흐르는지, 어디에 되돌아오는 화살표가 있는지. “의존성이 꼬였다”는 느낌을 그래프로 옮기면 순환이라는 이름이 붙고, 이름이 붙으면 도구로 찾을 수 있다.

정리

• 그래프는 값이 아니라 관계를 담는다. 트리는 제약이 붙은 그래프다.
• 방향·가중치·순환 셋으로 갈린다. 무엇을 가진 그래프인지가 문제를 정한다.
• 실무의 그래프는 대개 선이 희박해서 점마다 이웃 목록을 드는 쪽이 기본이다.
• 돌아다니는 두 방식의 차이는 큐를 쓰느냐 스택을 쓰느냐뿐이다. 가까운 곳부터냐, 파고드느냐.
• 실무에서 가장 자주 하는 일은 최단 경로가 아니라 순환 찾기다. 순환이 있으면 순서가 안 정해진다.

다음 글로 이 시리즈를 닫는다. 지금까지 연 그릇들을 한 장에 놓고, 눈앞의 문제에서 무엇을 고를지 정리한다.