인접 행렬

인접 행렬은 그래프에서 두 항목이 이어져 있는지를 칸 하나만 보고 답하게 해 줍니다. 항목을 가로와 세로에 똑같이 늘어놓습니다. 두 항목이 만나는 칸마다 이어졌는지를 적어 둡니다. 대신 이어지지 않은 짝도 칸을 하나씩 차지합니다. 그래서 항목 수의 제곱만큼 메모리를 씁니다.

상세

이 절은 다섯 사람의 친구 관계를 인접 행렬에 담아 그 모양부터 봅니다. 그 표 위에서 이어짐을 묻는 일과 이웃을 꺼내는 일이 얼마나 드는지 따라간 뒤 파이썬 코드로 옮겨 봅니다.

뒤에서는 간선에 방향이 붙거나 수가 붙은 그래프로 넓힙니다. 끝으로 메모리가 얼마나 드는지 봅니다. 이어짐을 담는 다른 방법인 인접 리스트와 견준 뒤 인접 행렬이 맞는 경우와 안 맞는 경우를 가립니다.

그래프와 인접

그래프는 무엇과 무엇이 이어져 있는지를 담는 자료구조입니다. 친구 관계나 서비스 사이의 호출 관계가 그래프로 담깁니다.

이어지는 항목 하나를 노드라고 부릅니다. 친구 관계라면 사람 한 명이 노드 하나입니다.

두 노드를 잇는 선 하나는 간선이라고 부릅니다. 친구 관계라면 두 사람이 친구라는 사실 하나가 간선 하나입니다.

다섯 사람 A · B · C · D · E 의 친구 관계를 예로 듭니다. A 는 B, C 와 친구입니다. B 는 C 와 친구입니다. C 는 D 와 친구입니다. E 는 아무와도 친구가 아닙니다.

flowchart TD
    A["A"] --- B["B"]
    A --- C["C"]
    B --- C
    C --- D["D"]
    E["E"]

간선 하나로 바로 이어진 두 노드를 서로 인접하다고 합니다. A 와 B 는 인접합니다. A 와 D 는 C 를 거쳐야 닿으므로 인접하지 않습니다.

한 노드와 인접한 노드들을 그 노드의 이웃이라고 부릅니다. C 의 이웃은 A · B · D 입니다.

인접 행렬이라는 이름은 이 낱말에서 왔습니다. 「어느 짝이 인접한가」를 행렬에 적는다는 뜻입니다. 행렬은 수를 가로세로로 늘어놓은 표입니다.

노드 × 노드 표

인접 행렬을 만들려면 먼저 노드마다 0 부터 번호를 붙입니다. A 는 0, B 는 1 이고 E 는 4 입니다. 번호가 있어야 표의 몇째 줄 몇째 칸인지를 셀 수 있습니다.

표에서 가로 한 줄을 행이라고 부릅니다. 세로 한 줄은 열이라고 부릅니다. 행과 열이 만나는 곳이 칸 하나입니다.

인접 행렬은 노드 수만큼 행과 열을 둡니다. 다섯 사람이면 5 × 5 로 25 칸입니다. i 번 노드와 j 번 노드가 이어져 있으면 i 행 j 열의 칸에 1 을 적습니다. 이어져 있지 않으면 0 을 적습니다.

C 행을 보면 A · B · D 열에 1 이 있습니다. C 의 친구가 셋이라는 뜻입니다. E 행은 전부 0 입니다. 친구가 없어도 E 는 행 하나를 다 차지합니다.

대각선을 사이에 둔 대칭

친구 관계에는 방향이 없습니다. A 가 B 의 친구면 B 도 A 의 친구입니다. 이런 그래프를 무방향 그래프라고 부릅니다.

무방향 그래프에서는 간선 하나가 칸 두 개에 적힙니다. A 와 B 를 잇는 간선은 A 행 B 열에도, B 행 A 열에도 1 을 남깁니다. 그래서 간선 넷을 담은 위 표에는 1 이 여덟 개 있습니다.

왼쪽 위에서 오른쪽 아래로 내려가는 칸들을 대각선이라고 부릅니다. A 행 A 열, B 행 B 열처럼 행과 열이 같은 노드인 칸들입니다.

위 표를 대각선을 따라 접으면 양쪽 칸이 똑같이 포개집니다. 이런 행렬을 대칭 행렬이라고 합니다.

대각선 칸은 노드가 자기 자신과 이어졌는지를 적습니다. 자기 자신으로 돌아오는 간선을 자기 루프라고 부릅니다. 친구 관계에는 자기 루프가 없어서 대각선은 모두 0 입니다.

칸 하나로 끝나는 일

인접 행렬의 강점은 「i 와 j 가 이어졌나」를 칸 하나로 답한다는 것입니다. 번호 두 개로 행과 열을 바로 찾아가므로 표가 얼마나 크든 드는 시간이 같습니다.

바로 찾아갈 수 있는 까닭은 표를 대개 2차원 배열로 두기 때문입니다. 배열은 번호만 알면 앞의 칸을 훑지 않고 그 칸으로 곧장 갑니다.

간선을 넣고 빼는 일도 칸만 바꾸면 끝납니다. 넣을 때는 두 칸을 1 로 바꿉니다. 뺄 때는 두 칸을 0 으로 바꿉니다. 다른 칸은 건드리지 않습니다.

한 행을 다 읽어야 하는 일

한 노드의 이웃을 꺼내는 일은 사정이 다릅니다. C 의 이웃을 모으려면 C 행을 처음부터 끝까지 읽으며 1 인 칸을 골라야 합니다. 이웃이 하나뿐이어도 행 하나를 전부 봅니다.

한 노드에 붙은 간선 수를 그 노드의 차수라고 부릅니다. 인접 행렬에서 차수는 그 행에 적힌 1 의 개수입니다. C 행을 더하면 3 이라서 C 의 차수는 3 입니다.

그래프 전체를 훑는 일은 이 행 읽기를 노드마다 되풀이합니다. 노드가 다섯이면 25 칸을 다 봅니다. 간선이 몇 개든 보는 칸 수는 같습니다.

파이썬으로 담은 인접 행렬

파이썬에서는 리스트 안에 리스트를 넣어 표를 만듭니다. 바깥 리스트의 i 번째 원소가 i 행입니다. 그 안의 j 번째 값이 i 행 j 열의 칸입니다. 자바라면 int[][] 가 같은 모양입니다.

adj = [
    [0, 1, 1, 0, 0],  # A
    [1, 0, 1, 0, 0],  # B
    [1, 1, 0, 1, 0],  # C
    [0, 0, 1, 0, 0],  # D
    [0, 0, 0, 0, 0],  # E
]

주석의 A · B · C 는 그 행이 어느 노드인지 적은 것입니다. 이제 앞에서 본 두 부류의 일을 이 표로 해 봅니다.

adj[0][3]                        # 0
sum(adj[2])                      # 3
row = adj[2]
[j for j in range(5) if row[j]]  # [0, 1, 3]

adj[0][3] 은 A 와 D 가 이어졌는지를 칸 하나로 답합니다. 0 이라서 이어져 있지 않습니다. sum(adj[2]) 는 C 행의 1 을 세어 차수 3 을 냅니다.

마지막 두 줄은 C 의 이웃을 꺼냅니다. C 행 다섯 칸을 모두 보고 1 인 칸의 번호를 모읍니다. 나온 번호 0 · 1 · 3 이 곧 A · B · D 입니다.

간선을 넣는 함수는 대칭을 지키려고 두 칸을 함께 바꿉니다.

def add_edge(m, u, v):
    m[u][v] = 1
    m[v][u] = 1

한쪽 칸만 바꾸면 표가 어긋납니다. A 행에는 B 가 친구로 적힙니다. B 행에는 A 가 없습니다.

이 실수는 표 전체의 1 을 세어 보면 드러납니다. 간선을 넣은 횟수를 따로 세어 두었다고 해 봅니다. 무방향 그래프라면 1 의 합이 그 횟수의 두 배여야 합니다.

sum(sum(row) for row in adj)    # 8

간선 넷을 넣었으므로 8 이 맞습니다. 한쪽 칸만 바꾼 간선이 있으면 합이 모자랍니다.

방향이 있는 그래프

간선에 방향이 붙은 그래프를 방향 그래프라고 합니다. 「주문 서비스가 결제 서비스를 부른다」는 주문에서 결제로 가는 간선 하나입니다. 결제가 주문을 부른다는 뜻은 담겨 있지 않습니다.

서비스 넷의 호출 관계를 예로 듭니다. 주문은 결제와 재고를 부릅니다. 결제는 알림을 부릅니다.

flowchart TD
    주문["주문"] --> 결제["결제"]
    주문 --> 재고["재고"]
    결제 --> 알림["알림"]

방향 그래프에서는 간선 하나가 칸 하나에만 적힙니다. 출발 노드의 행과 도착 노드의 열이 만나는 칸에 1 을 적습니다. 그래서 표가 대각선을 사이에 두고 대칭이 아닙니다.

calls = [
    [0, 1, 1, 0],  # 주문
    [0, 0, 0, 1],  # 결제
    [0, 0, 0, 0],  # 재고
    [0, 0, 0, 0],  # 알림
]

이렇게 담으면 행과 열이 뜻을 나눠 가집니다. 한 행은 그 노드가 부르는 쪽을 적습니다. 한 열은 그 노드를 부르는 쪽을 적습니다.

calls[0]                   # [0, 1, 1, 0]
[row[1] for row in calls]  # [1, 0, 0, 0]

첫 줄은 주문 행입니다. 결제와 재고 칸이 1 이라서 주문이 부르는 서비스는 그 둘입니다.

둘째 줄은 결제 열을 위에서 아래로 읽습니다. 주문 칸만 1 이라서 결제를 부르는 서비스는 주문 하나입니다. 들어오는 간선을 찾으려고 표를 따로 하나 더 만들 필요가 없습니다.

가중치가 붙은 그래프

이 소절은 앞의 서비스 호출 그래프에 수를 하나씩 붙여 봅니다. 호출 한 번에 걸리는 시간을 밀리초로 적은 값입니다.

간선에 붙는 이런 수를 가중치라고 합니다. 걸리는 시간 말고 거리나 요금이 붙기도 합니다. 가중치가 있으면 칸에 1 대신 그 수를 적습니다.

이때 0 으로 「간선 없음」을 적으면 헷갈립니다. 걸리는 시간이 0 인 간선과 구별되지 않기 때문입니다. 그래서 없는 간선은 무한대로 적는 경우가 많습니다. 닿을 수 없는 곳까지의 비용을 끝없이 크다고 보는 셈입니다.

대각선에는 0 을 적습니다. 자기 자신까지 가는 데는 비용이 들지 않기 때문입니다.

주문이 결제를 부르는 간선에 40 을, 재고를 부르는 간선에 15 를 붙입니다. 결제가 알림을 부르는 간선에는 5 를 붙입니다.

INF = float("inf")
cost = [
    [0,   40,  15,  INF],  # 주문
    [INF, 0,   INF, 5  ],  # 결제
    [INF, INF, 0,   INF],  # 재고
    [INF, INF, INF, 0  ],  # 알림
]
cost[0][2]                      # 15
cost[2][0]                      # inf

주문에서 재고로 가는 호출에 15 가 붙어 있습니다. 이 호출에 걸리는 시간입니다. 재고에서 주문으로 가는 간선은 없어서 무한대가 나옵니다.

float("inf") 는 파이썬에서 무한대를 뜻하는 값입니다. 어떤 수보다도 크므로 더 싼 길을 고르는 비교에 섞어 써도 계산이 어긋나지 않습니다.

칸 수가 정하는 메모리

노드 수를 V 라고 하면 인접 행렬은 늘 V × V 칸을 씁니다. V 는 노드의 다른 이름인 정점(vertex) 에서 딴 글자입니다. 간선이 하나도 없어도 칸 수는 같습니다.

간선 수는 E 라고 적습니다. 간선(edge)에서 딴 글자입니다. 앞 예시에서 친구가 없던 사람 E 와는 다른 E 입니다.

칸에 0 과 1 만 적는다면 칸마다 비트 하나면 됩니다. 한 바이트에 칸 여덟 개가 들어가므로 메모리가 8분의 1 로 줄어듭니다. 그래도 칸 수가 V × V 라는 것은 바뀌지 않습니다.

노드가 열 배 늘 때마다 칸은 백 배 늡니다. 사용자 백만 명의 친구 관계를 담으면 비트로 줄여도 125기가바이트입니다. 한 사람의 친구가 100명 안팎이라면 1 이 적힌 칸은 1억 개뿐입니다. 나머지 9999억 칸은 0 입니다.

노드를 하나 더하는 일도 비쌉니다. 표의 크기가 V × V 로 정해져 있어서 행 하나와 열 하나를 새로 붙여야 합니다. 크기가 정해진 배열로 두었다면 한 칸 큰 표를 새로 만들고 옛 칸을 모두 옮깁니다.

인접 리스트와 견준 비용

이 소절은 인접 행렬이 드는 시간과 공간을 다른 대표 방법과 한 표에 놓고 견줍니다. 먼저 견줄 상대와 비용을 적는 표기를 봅니다.

인접 리스트는 노드마다 이어진 상대만 적은 목록을 하나씩 둡니다. 이어지지 않은 짝은 어디에도 적지 않습니다. C 의 목록에는 A · B · D 만 들어 있습니다.

그래프가 커질 때 비용이 어떻게 늘어나는지는 빅오 표기법으로 적습니다. 늘어나는 꼴만 남기는 표기법입니다. 자잘한 차이는 버립니다.

O(V²) 는 드는 시간이나 공간이 노드 수의 제곱에 비례해 늘어난다는 뜻입니다. 앞 소절에서 본 인접 행렬의 칸 수가 이 꼴입니다.

O(1) 은 그래프가 커져도 드는 시간이 같다는 뜻입니다. 칸 하나로 이어짐을 답하는 일이 이 꼴입니다.

O(차수) 는 그 노드에 붙은 간선 수만큼 걸린다는 뜻입니다. 인접 리스트에서 한 노드의 목록을 훑는 일이 이 꼴입니다.

O(V) 는 노드 수에 비례한다는 뜻입니다. 인접 행렬에서 한 행을 처음부터 끝까지 읽는 일이 이 꼴입니다.

O(V+E) 는 노드 수와 간선 수를 더한 만큼 든다는 뜻입니다. 인접 리스트가 차지하는 공간이 이 꼴입니다. 노드마다 목록 하나를 두고, 목록에 적힌 이름 수는 간선 수에 비례하기 때문입니다.

아래 표는 이 다섯 꼴로 두 방법을 견줍니다.

표에서 행렬이 이기는 것은 이어짐 묻기와 간선 빼기입니다. 두 노드가 만나는 칸 하나만 보면 됩니다.

리스트가 이기는 것은 공간 · 이웃 꺼내기 · 전체 훑기입니다. 행렬은 이웃이 몇 없어도 한 행의 V 칸을 전부 봐야 합니다. 리스트는 적힌 이웃만 봅니다.

인접 행렬이 맞는 경우

이 소절은 인접 행렬이 유리한 그래프 두 종류를 먼저 봅니다. 이어서 행렬 계산을 그대로 쓰는 알고리즘 둘을 봅니다.

거의 모든 짝이 이어진 그래프를 밀집 그래프라고 부릅니다. 이때는 인접 리스트도 목록마다 거의 모든 노드를 적게 됩니다. 공간 차이가 줄어듭니다. 이어짐을 칸 하나로 답하는 이점만 남습니다.

노드 수가 작은 그래프도 인접 행렬이 편합니다. 노드가 수십 개면 칸은 수천 개라 메모리가 문제되지 않습니다. 코드는 2차원 배열 하나로 끝납니다.

모든 짝 사이의 최단 거리를 한꺼번에 구하는 플로이드 알고리즘은 인접 행렬 위에서 돕니다. 가중치를 적은 행렬에서 출발합니다. 중간에 들를 노드를 하나씩 늘려 가며 칸 값을 더 짧은 거리로 고쳐 씁니다. 끝나면 i 행 j 열에 i 에서 j 까지의 최단 거리가 남습니다.

인접 행렬은 행렬이라서 행렬 곱도 할 수 있습니다. 두 행렬을 곱한 결과의 i 행 j 열은 앞 행렬의 i 행과 뒤 행렬의 j 열을 칸끼리 차례로 곱해 모두 더한 값입니다.

0 과 1 로 된 인접 행렬을 자기 자신과 곱해 봅니다. i 행 k 열과 k 행 j 열이 둘 다 1 이면 그 곱이 1 입니다. i 에서 k 를 거쳐 j 로 가는 길이 하나 있다는 뜻입니다.

그래서 결과의 i 행 j 열은 i 에서 간선 두 개를 거쳐 j 에 닿는 길의 개수입니다.

인접 행렬이 안 맞는 경우

이 소절은 인접 행렬이 불리한 그래프와 탐색 절차를 봅니다. 끝으로 빈칸을 덜어 낸 저장 방식이 인접 리스트와 어떻게 닮는지 봅니다.

간선이 가능한 짝의 수보다 훨씬 적은 그래프를 희소 그래프라고 부릅니다. 앞에서 본 백만 명의 친구 관계가 그렇습니다. 칸 대부분이 0 이라서 메모리를 거의 빈칸에 씁니다.

백엔드에서 만나는 그래프도 대개 희소합니다. 서비스가 수백 개여도 한 서비스가 부르는 곳은 몇 개뿐입니다. 이런 의존성 그래프를 행렬로 담으면 행마다 1 이 몇 칸뿐입니다.

이웃을 되풀이해 꺼내는 절차에서도 불리합니다. 너비 우선 탐색은 시작 노드에서 가까운 노드부터 한 겹씩 넓혀 가는 탐색입니다. 노드를 꺼낼 때마다 이웃을 모두 보므로 인접 행렬에서는 노드마다 행 하나를 읽습니다. 전체가 O(V²) 입니다. 인접 리스트라면 O(V+E) 로 끝납니다.

0 이 대부분인 행렬을 희소 행렬이라고 부릅니다. 희소 행렬은 0 이 아닌 칸만 골라 적는 저장 방식을 따로 씁니다. 인접 행렬을 그렇게 담으면 행마다 1 인 열 번호만 남습니다. 그 모양은 인접 리스트와 같아집니다.

관련 항목

인접 행렬이 속하는 상위 분류

자료구조 · 그래프 · 그래프 표현 · 행렬 · 2차원 배열 · 배열

인접 행렬을 이루는 구성 요소

노드 · 정점 · 간선 · 이웃 · 차수 · 가중치 · 무한대 · 자기 루프 · 대칭 행렬

인접 행렬과 겨루는 그래프 표현 방식

인접 리스트 · 간선 리스트 · 희소 행렬 · 압축 희소 행 · 순방향 스타

인접 행렬로 담는 그래프의 종류

무방향 그래프 · 방향 그래프 · 가중 그래프 · 밀집 그래프 · 희소 그래프 · DAG · 완전 그래프

인접 행렬 위에서 도는 알고리즘

플로이드 알고리즘 · 너비 우선 탐색 · 깊이 우선 탐색 · 프림 알고리즘 · 최단 경로 · 이행적 폐쇄 · 행렬 곱

인접 행렬의 칸을 비트로 줄이는 저장 방식

비트 · 비트맵 · 비트셋 · 비트 마스크

인접 행렬로 담는 관계

의존성 그래프 · 소셜 그래프 · 호출 그래프 · 지식 그래프

인접 행렬의 비용을 적는 표기

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