[자료구조 13] 그래프 표현하기

친구 관계를 떠올려 보겠습니다. 민수는 지은, 현우와 친구이고 지은은 또 다른 사람과 친구입니다. 이렇게 여러 대상이 서로 얽혀 연결된 관계는 한 줄로 세우거나 위아래 계층으로 정리하기가 어렵습니다. 이런 데이터를 담는 자료구조가 그래프(graph, 점과 선으로 관계를 나타내는 구조)입니다. 지하철 노선도, 웹 페이지 사이의 링크, 사회 관계망이 모두 그래프입니다. 이번 글에서는 그래프가 무엇인지 살펴보고, 파이썬에서 그래프를 담는 두 가지 방법을 손으로 따라 치며 익혀 보겠습니다.

13.1 그래프는 노드와 엣지로 이루어집니다

그래프는 두 가지 요소로 만들어집니다. 하나는 노드(node, 점. 정점이라고도 합니다), 다른 하나는 엣지(edge, 노드와 노드를 잇는 선)입니다. 친구 관계라면 사람 한 명이 노드이고, 두 사람이 친구라는 사실이 엣지입니다. 한 노드에 선으로 직접 이어진 다른 노드를 그 노드의 이웃(neighbor)이라고 부릅니다.

예를 들어 A, B, C, D 네 개의 노드가 있고 A와 B, A와 C, B와 D, C와 D가 서로 이어져 있다고 하겠습니다. 사람 넷이 서로 아는 관계를 그린 것이라고 보아도 좋습니다. 이 관계를 컴퓨터가 다루려면 "누가 누구와 이어져 있는지"를 어딘가에 담아 두어야 합니다. 담는 방법이 크게 두 가지인데, 하나는 인접 리스트이고 다른 하나는 인접 행렬입니다. 두 방법은 담는 모양도 다르고, 잘 어울리는 상황도 다릅니다. 순서대로 보겠습니다.

13.2 인접 리스트: 딕셔너리로 이웃 목록 담기

가장 많이 쓰는 방법은 인접 리스트(adjacency list, 노드마다 이웃 목록을 붙이는 방식)입니다. 각 노드를 키로 두고, 그 값으로 이웃들의 목록을 담습니다. 파이썬에서는 딕셔너리 하나로 깔끔하게 표현됩니다.

graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D"],
"D": ["B", "C"],
}
print(graph["A"]) # A의 이웃

['B', 'C']

딕셔너리의 키가 노드이고, 그 값이 노드의 이웃 목록입니다. graph["A"]라고 하면 A와 이어진 이웃 ['B', 'C']가 곧바로 나옵니다. 딕셔너리 조회는 평균 O(1)이므로, 어떤 노드의 이웃이 누구인지 개수와 상관없이 즉시 꺼낼 수 있습니다.

여기서 한 가지 눈여겨볼 점이 있습니다. A의 목록에 B가 들어 있고, B의 목록에도 A가 들어 있습니다. 서로 친구라는 관계는 양쪽 모두에 성립하기 때문입니다. 이렇게 연결에 방향이 없는 그래프를 무방향 그래프(undirected graph)라고 합니다. 반대로 "누가 누구를 팔로우한다"처럼 한쪽으로만 향하는 관계는 한쪽 목록에만 상대를 담으며, 이런 그래프를 방향 그래프(directed graph)라고 부릅니다. 어느 쪽이든 딕셔너리로 담는 방식은 똑같습니다.

이 방식의 장점은 공간을 아낀다는 점입니다. 실제로 이어져 있는 엣지만 목록에 담기기 때문입니다. 그래서 연결이 드문드문한 그래프에서 특히 효율적입니다. 이렇게 연결이 적은 그래프를 희소 그래프(sparse graph)라고 부릅니다. 필요한 공간은 노드 수와 엣지 수를 합한 만큼입니다. 대부분의 실전 문제에서 그래프는 인접 리스트로 담습니다.

13.3 인접 행렬: 표로 연결 여부 담기

다른 방법은 인접 행렬(adjacency matrix, 연결 여부를 표로 나타내는 방식)입니다. 노드 수만큼의 행과 열을 가진 표를 만들고, i번 노드와 j번 노드가 이어져 있으면 그 칸에 1을, 아니면 0을 적습니다. 2차원 리스트로 표현합니다.

nodes = ["A", "B", "C", "D"]
idx = {n: i for i, n in enumerate(nodes)}
matrix = [[0] * 4 for _ in range(4)]
for n, nbrs in graph.items():
for m in nbrs:
matrix[idx[n]][idx[m]] = 1
for i, row in enumerate(matrix):
print(nodes[i], row)

A [0, 1, 1, 0]
B [1, 0, 0, 1]
C [1, 0, 0, 1]
D [0, 1, 1, 0]

노드 이름을 번호로 바꾸려고 idx라는 딕셔너리를 먼저 만들었습니다. A는 0번, B는 1번 하는 식입니다. 그다음 4행 4열짜리 표를 0으로 채워 두고, 이어진 노드끼리 그 칸을 1로 바꿨습니다. 표를 읽는 법은 간단합니다. matrix[i][j]가 1이면 i번 노드와 j번 노드가 연결되어 있다는 뜻입니다. 덕분에 "두 노드가 서로 이어져 있나?"라는 질문에 칸 하나만 확인하면 되어 O(1)에 답할 수 있습니다.

대신 대가가 있습니다. 실제 연결이 몇 개든 노드 수의 제곱만큼 칸을 만들어야 합니다. 노드가 1000개면 100만 칸이 필요합니다. 그래서 인접 행렬은 연결이 빽빽한 밀집 그래프(dense graph)나, 두 노드의 연결 여부를 아주 자주 물어봐야 하는 경우에 어울립니다.

13.4 인접 행렬을 만들 때의 함정

2차원 리스트를 만들 때 초보가 자주 저지르는 실수가 하나 있습니다. 곱셈으로 빈 표를 만들면 안 된다는 것입니다. 앞의 예제에서 리스트 컴프리헨션(for _ in range 형태)을 쓴 데에는 이유가 있습니다.

wrong = [[0] * 3] * 2
wrong[0][0] = 1
print(wrong) # 두 행이 같이 바뀝니다

right = [[0] * 3 for _ in range(2)]
right[0][0] = 1
print(right) # 정상

[[1, 0, 0], [1, 0, 0]]
[[1, 0, 0], [0, 0, 0]]

[[0] * 3] * 2는 같은 안쪽 리스트 하나를 두 번 가리키게 만듭니다. 그래서 첫 행의 한 칸만 바꿨는데 둘째 행까지 함께 바뀝니다. 반면 for _ in range(2)로 만들면 매번 새 리스트가 생겨 서로 독립적입니다. 인접 행렬처럼 2차원 표를 만들 때는 반드시 이 방식을 써야 합니다.

13.5 정리: 두 방법의 선택 기준

두 표현 방법은 목적이 다릅니다. 인접 리스트는 실제 엣지만 담아 공간을 아끼고, 한 노드의 이웃을 훑기가 편합니다. 공간은 노드와 엣지를 합한 만큼입니다. 인접 행렬은 두 노드의 연결 여부를 O(1)에 확인할 수 있지만 노드 수의 제곱만큼 공간을 씁니다.

정리하면 연결이 드문 그래프나 이웃을 자주 훑어야 하는 경우에는 인접 리스트(딕셔너리)를, 연결이 빽빽하거나 두 노드의 연결 여부를 빠르게 물어야 하는 경우에는 인접 행렬을 씁니다. 대부분의 현실 그래프는 노드 수에 비해 연결이 드문 편이라, 실제 문제에서는 딕셔너리로 담는 인접 리스트가 훨씬 자주 쓰입니다. 그래서 그래프를 딕셔너리로 표현하는 형태에 먼저 익숙해지는 것이 좋습니다. 두 방법으로 같은 그래프를 각각 담아 보고, 이웃을 꺼내는 코드와 연결을 확인하는 코드가 어떻게 달라지는지 손으로 비교해 보시기 바랍니다.