정점·간선·인접 목록과 인접 행렬

지하철 노선도, 친구 관계, 강의의 선수 과목처럼 우리가 다루는 자료 중에는 값 자체보다 값들 사이의 연결이 중요한 것이 많습니다. 어느 역에서 어느 역으로 갈 수 있는지, 두 사람이 몇 다리를 건너 아는 사이인지는 연결을 따라가야 답할 수 있습니다. 이런 연결 구조를 나타내는 도구가 그래프(graph)입니다. 이 글에서는 그래프의 기본 용어를 익히고, 그래프를 Python 코드에 담는 두 가지 방법을 비교합니다. 이어서 연결을 따라 이동하는 방식을 보행, 경로, 사이클로 구분하고, 모든 연결을 한 번씩 지나는 길이 언제 가능한지 판정해 봅니다.

정점과 간선

그래프는 정점(vertex)과 간선(edge)으로 이루어집니다. 정점은 역이나 사람 같은 대상이고, 간선은 두 정점 사이의 연결입니다. 간선에 방향이 없어서 A—B가 A에서 B로도, B에서 A로도 갈 수 있다는 뜻이면 무방향 그래프(undirected graph)라고 합니다. 일방통행 도로처럼 A→B가 A에서 B로만 갈 수 있다는 뜻이면 방향 그래프(directed graph)라고 합니다. 방향 그래프에서 A→B와 B→A는 서로 다른 간선입니다. 간선에 거리나 비용 같은 수가 붙어 있으면 그 수를 가중치(weight)라고 합니다.

무방향 그래프에서 한 정점에 붙은 간선의 개수를 그 정점의 차수(degree)라고 합니다. 방향 그래프에서는 들어오는 간선의 수인 진입 차수(in-degree)와 나가는 간선의 수인 진출 차수(out-degree)를 따로 셉니다. 무방향 그래프에서 모든 정점의 차수를 더하면 언제나 간선 수의 두 배가 됩니다. 간선 하나가 양 끝의 두 정점에서 한 번씩, 모두 두 번 세어지기 때문입니다. 그래서 차수가 홀수인 정점은 늘 짝수 개만 있습니다.

이 글에서는 한 정점에서 자기 자신으로 가는 간선이나, 같은 두 정점 사이에 간선이 여러 개 있는 경우는 다루지 않습니다. 이런 간선이 없는 그래프를 단순 그래프(simple graph)라고 합니다.

그래프를 코드에 담는 두 방법

간선 A—B, B—C, C—A, A—D가 있는 무방향 그래프를 예로 들겠습니다. 첫 번째 방법인 인접 목록(adjacency list)은 정점마다 이웃 정점의 목록을 적습니다. Python에서는 정점을 키로, 이웃의 리스트를 값으로 하는 딕셔너리가 자연스럽습니다. 무방향 간선 A—B는 A의 목록에 B를, B의 목록에 A를 모두 적어야 합니다.

두 번째 방법인 인접 행렬(adjacency matrix)은 정점에 0부터 번호를 붙이고, i번 정점과 j번 정점이 이어져 있으면 i행 j열에 1을, 아니면 0을 적은 표입니다. 무방향 그래프라면 i행 j열과 j행 i열이 늘 같으므로 행렬이 대각선을 기준으로 대칭입니다. 방향 그래프는 A→B만 있을 때 A행 B열은 1이지만 B행 A열은 0이라서 일반적으로 대칭이 아닙니다.

edges = [("A", "B"), ("B", "C"), ("C", "A"), ("A", "D")]
vertices = ["A", "B", "C", "D"]

adjacency = {v: [] for v in vertices}
for u, v in edges:
    adjacency[u].append(v)
    adjacency[v].append(u)

index = {v: i for i, v in enumerate(vertices)}
matrix = [[0] * len(vertices) for _ in vertices]
for u, v in edges:
    matrix[index[u]][index[v]] = 1
    matrix[index[v]][index[u]] = 1

print(adjacency)
for v, row in zip(vertices, matrix):
    print(v, row)
degrees = {v: len(neighbors) for v, neighbors in adjacency.items()}
print(degrees, sum(degrees.values()), 2 * len(edges))

{'A': ['B', 'C', 'D'], 'B': ['A', 'C'], 'C': ['B', 'A'], 'D': ['A']}
A [0, 1, 1, 1]
B [1, 0, 1, 0]
C [1, 1, 0, 0]
D [1, 0, 0, 0]
{'A': 3, 'B': 2, 'C': 2, 'D': 1} 8 8

{v: [] for v in vertices}는 정점마다 빈 리스트를 값으로 갖는 딕셔너리를 만드는 딕셔너리 컴프리헨션입니다. index는 정점 이름을 행렬의 번호로 바꾸는 딕셔너리이고, zip(vertices, matrix)는 정점 이름과 행렬의 행을 짝지어 줍니다. 마지막 줄에서 차수의 합 8이 간선 수 4의 두 배와 같다는 것도 확인할 수 있습니다.

행렬을 만들 때 [[0] * 4] * 4처럼 쓰면 안 됩니다. 이렇게 하면 함수·리스트·복사와 작은 검사에서 본 별칭처럼 네 행이 모두 같은 리스트를 가리켜서, 한 칸을 바꾸면 모든 행의 같은 칸이 함께 바뀝니다.

wrong = [[0] * 3] * 3
wrong[0][1] = 1
print(wrong)

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

본문 코드의 [[0] * len(vertices) for _ in vertices]는 반복할 때마다 새 리스트를 만들므로 행들이 서로 독립입니다.

어느 표현을 고를까

두 표현은 잘하는 일이 다릅니다. 인접 행렬은 두 정점이 이어져 있는지를 칸 하나로 확인하므로 O(1)입니다. 인접 목록은 한 정점의 이웃 목록을 훑어야 하므로 그 정점의 차수만큼 걸립니다. 반대로 한 정점의 이웃을 모두 나열할 때는 인접 목록이 차수만큼이면 되지만, 인접 행렬은 행 하나의 칸 V개를 모두 보아야 합니다. 여기서 V는 정점의 수, E는 간선의 수입니다.

공간의 차이는 간선이 적은 그래프에서 크게 드러납니다. 정점 100개와 간선 3개인 무방향 그래프를 인접 행렬로 저장하면 100 × 100 = 10,000칸이 필요합니다. 간선 하나가 대칭인 두 칸을 1로 만드므로 1은 6칸뿐이고, 나머지 9,994칸, 곧 99.94%가 0입니다. 0이라고 해서 칸이 사라지지는 않으므로 이 공간은 모두 쓰입니다. 인접 목록이라면 정점 100개의 항목과 이웃 항목 6개면 됩니다. 이처럼 칸의 대부분이 0인 행렬을 희소 행렬(sparse matrix)이라고 합니다. 실제로 다루는 도로망이나 친구 관계의 그래프는 정점마다 이웃이 몇 개 되지 않는 경우가 많아서, 이 교재의 그래프 알고리즘은 주로 인접 목록을 씁니다. 여기서 센 것은 칸과 항목의 개수이고, Python 객체가 실제로 차지하는 바이트 수는 이와 따로 따져야 합니다.

간선이 하나도 없거나 모두 있는 그래프

차수가 0인 정점, 곧 이웃이 하나도 없는 정점을 고립점(isolated vertex)이라고 합니다. {"A": [], "B": []}는 정점 두 개가 모두 고립점이고 간선이 하나도 없는 그래프입니다. 간선이 없는 그래프를 널 그래프(null graph)라고 부르는 교재도 있는데, 이 이름을 정점까지 하나도 없는 {}에 쓰는 자료도 있으므로 읽을 때 어느 쪽인지 확인해야 합니다.

반대로 서로 다른 모든 정점 쌍이 간선으로 이어진 단순 무방향 그래프를 완전 그래프(complete graph)라고 합니다. 정점이 n개이면 각 정점이 다른 n - 1개와 이어지므로 n(n - 1)을 생각할 수 있지만, 이렇게 세면 A—B를 A 쪽에서 한 번, B 쪽에서 한 번 세게 됩니다. 그래서 간선 수는 n(n - 1)/2이고, 이것이 정점 n개인 단순 무방향 그래프가 가질 수 있는 간선의 최대 개수입니다. 정점이 A, B, C, D 넷이면 A—B, A—C, A—D, B—C, B—D, C—D의 6개입니다. 자기 자신으로 가는 간선이 없는 방향 그래프에서는 A→B와 B→A가 서로 다른 간선이므로 최대 n(n - 1)개, 정점 넷이면 12개입니다.

보행·경로·트레일·사이클

간선을 따라 정점에서 정점으로 이동한 차례를 정점의 열로 적은 것을 보행(walk)이라 하고, 지나간 간선의 개수를 보행의 길이라고 합니다. 보행에서는 같은 정점이나 같은 간선을 다시 지나도 됩니다. 이 가운데 같은 정점을 다시 지나지 않는 보행을 경로(path), 정확히는 단순 경로(simple path)라 하고, 같은 간선을 다시 지나지 않는 보행을 트레일(trail)이라고 합니다. 무방향 그래프에서 A—B를 지난 뒤 B에서 A로 돌아가는 것도 같은 간선을 다시 쓴 것입니다.

같은 정점을 지나지 않으면 같은 간선도 지날 수 없으므로, 모든 경로는 트레일입니다. 하지만 트레일은 간선만 겹치지 않으면 되므로 같은 정점을 다시 지날 수 있습니다. 출발점으로 돌아오는 트레일 가운데 마지막에 다시 쓴 출발점을 빼면 모든 정점이 서로 다른 것을 사이클(cycle)이라고 합니다. 단순 무방향 그래프에서 사이클은 간선이 적어도 세 개 필요합니다. A, B, A처럼 같은 간선으로 갔다가 돌아오는 것은 출발점으로 돌아오기는 하지만 같은 간선을 두 번 썼으므로 사이클이 아닙니다.

앞의 그래프에서 몇 가지 정점 열을 분류해 보겠습니다.

용어는 교재마다 조금씩 다르게 쓰입니다. 간선이 반복되지 않는 보행을 "기본 경로"라고 부르거나, 이 글의 보행을 "경로"라고 부르는 교재도 있습니다. 그래서 그래프 문제를 읽을 때는 이름보다 정점과 간선의 반복이 허용되는지를 먼저 확인하는 것이 안전합니다. 이 교재의 용어는 Python 그래프 라이브러리 NetworkX의 단순 경로와 단순 사이클 정의와도 맞습니다. 라이브러리를 설치할 필요는 없습니다.

모든 간선을 한 번씩 지나는 길

1736년 Leonhard Euler는 쾨니히스베르크라는 도시의 일곱 다리를 모두 한 번씩만 건너는 산책길이 있는지를 묻는 문제를 풀었습니다. 땅을 정점으로, 다리를 간선으로 보면 이것은 모든 간선을 정확히 한 번씩 지나는 트레일을 찾는 문제입니다. 이런 트레일을 오일러 경로(Euler trail)라 하고, 출발점으로 돌아오면 오일러 순환(Euler circuit)이라고 합니다. 이름에는 경로라는 말이 들어 있지만, 앞에서 정한 경로와 달리 같은 정점을 여러 번 지나도 되는 트레일이라는 점에 주의해야 합니다.

Euler가 찾은 답의 핵심은 차수입니다. 순환을 따라 어떤 정점을 지날 때마다 들어오는 간선 하나와 나가는 간선 하나를 쓰므로, 모든 간선을 한 번씩 쓰고 돌아오려면 모든 정점의 차수가 짝수여야 합니다. 출발점과 도착점이 다른 오일러 경로라면 그 두 정점만 차수가 홀수일 수 있습니다. 거꾸로, 간선이 있는 정점들이 모두 하나로 이어져 있으면 이 조건만으로 충분하다는 것도 알려져 있으며, 그 증명은 이산수학의 오일러와 해밀턴 경로에서 다룹니다. 쾨니히스베르크는 같은 두 땅을 잇는 다리가 여러 개인 곳이 있어 이 글에서 다루는 단순 그래프가 아니지만, 차수 조건은 이런 그래프에도 그대로 쓸 수 있습니다. 네 땅의 차수는 5, 3, 3, 3으로 모두 홀수라서 그런 산책길이 없었습니다.

아래 함수는 이 조건으로 무방향 단순 그래프를 판정합니다. 먼저 간선이 있는 정점들이 모두 이어져 있는지 확인하는데, 스택을 써서 한 정점에서 닿을 수 있는 정점을 모두 방문합니다. 이 방문 방법은 다음 글의 깊이 우선 탐색에서 자세히 다룹니다. 이어지지 않은 부분이 있으면 한 번의 산책으로 모든 간선을 지날 수 없으므로 차수와 상관없이 불가능합니다.

def euler_kind(graph):
    active = [v for v, neighbors in graph.items() if neighbors]
    if not active:
        return "간선 없음"
    seen, stack = set(), [active[0]]
    while stack:
        vertex = stack.pop()
        if vertex not in seen:
            seen.add(vertex)
            stack.extend(graph[vertex])
    if len(seen) != len(active):
        return "불가능"
    odd = sum(1 for v in active if len(graph[v]) % 2 == 1)
    if odd == 0:
        return "오일러 순환"
    if odd == 2:
        return "오일러 경로"
    return "불가능"


triangle = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B"]}
two_triangles = {**triangle, "D": ["E", "F"], "E": ["D", "F"], "F": ["D", "E"]}
example = {"A": ["B", "C", "D"], "B": ["A", "C"], "C": ["B", "A"], "D": ["A"]}
for graph in [triangle, two_triangles, example, {"A": [], "B": []}]:
    print(euler_kind(graph))

오일러 순환
불가능
오일러 경로
간선 없음

active는 이웃이 있는 정점들입니다. 고립점은 지날 간선이 없으므로 연결 여부를 따질 때 뺍니다. seen은 이미 방문한 정점의 집합이고, 스택에서 꺼낸 정점이 처음 보는 것이면 방문 표시를 한 뒤 그 이웃을 모두 스택에 넣습니다. {**triangle, ...}는 triangle의 항목들을 새 딕셔너리에 펼쳐 넣고 뒤에 적은 항목을 더하는 문법입니다.

삼각형은 모든 차수가 2라서 오일러 순환이 있습니다. 삼각형 두 개를 떨어뜨려 놓은 그래프도 모든 차수가 2이지만, 둘이 이어져 있지 않아 불가능합니다. 차수만 보고 판정하면 안 되는 이유입니다. 이 글의 예제 그래프는 A와 D의 차수가 홀수인 3과 1이라서, D에서 출발해 A, B, C를 거쳐 A에서 끝나는 오일러 경로가 있습니다. 모든 정점을 한 번씩 지나는 길은 이와 다른 문제로, 간단한 판정 조건이 알려져 있지 않은 어려운 문제입니다.

정리

• 그래프는 대상인 정점과 연결인 간선으로 이루어지며, 간선에 방향이 있는지에 따라 방향 그래프와 무방향 그래프로 나뉩니다. 무방향 그래프에서 차수의 합은 간선 수의 두 배입니다.
• 인접 목록은 정점마다 이웃의 리스트를 두어 O(V + E)의 공간을 쓰고, 인접 행렬은 V × V 표에 연결 여부를 적어 O(V²)의 공간을 쓰는 대신 두 정점의 연결을 O(1)에 확인합니다.
• 간선이 적은 그래프의 인접 행렬은 칸 대부분이 0인 희소 행렬이 되어 공간을 낭비하므로, 이런 그래프에는 인접 목록이 알맞습니다.
• 단순 무방향 그래프의 간선은 많아야 n(n - 1)/2개이고, 자기 자신으로 가는 간선이 없는 방향 그래프는 많아야 n(n - 1)개입니다.
• 보행은 반복을 허용하고, 경로는 정점을, 트레일은 간선을 반복하지 않습니다. 사이클은 출발점으로 돌아오며 그 밖의 정점을 반복하지 않습니다.
• 간선이 있는 정점들이 이어져 있을 때, 차수가 홀수인 정점이 0개면 오일러 순환이, 2개면 오일러 경로가 있습니다.

연습 문제

1. 일직선 그래프의 오일러 경로

간선이 A—B, B—C뿐인 그래프에서 각 정점의 차수를 구하고, 오일러 순환과 오일러 경로가 있는지 판정하세요.

2. 간선의 최대 개수

정점이 5개일 때, 단순 무방향 그래프와 자기 자신으로 가는 간선이 없는 방향 그래프의 간선은 각각 최대 몇 개일까요?

3. 정점 열 분류하기

간선 P—Q, Q—R, R—P, P—S가 있는 그래프에서 정점 열 P, Q, R, P, S와 P, Q, P, S를 보행, 경로, 트레일 기준으로 분류하세요.

4. 희소한 인접 행렬

정점 200개와 간선 20개인 단순 무방향 그래프를 인접 행렬로 저장할 때, 전체 칸 수와 1인 칸 수, 0인 칸 수를 구하세요. 인접 목록이라면 항목이 몇 개 필요할까요?

다음 글 스택과 깊이 우선 탐색 DFS에서는 오일러 판정에서 잠깐 쓴, 스택으로 이어진 정점을 모두 방문하는 방법을 자세히 다룹니다.