한양과학기술고등학교

그래프 기본 용어

그래프(Graph)는 정점(Vertex, 노드) 들과 그것을 잇는 간선(Edge) 들의 모임이다. 간선에 방향이 있으면 방향 그래프(directed), 없으면 무방향 그래프(undirected)라 하고, 간선마다 비용(거리·시간 등) 숫자가 붙으면 가중치 그래프(weighted)라 한다.

인접 행렬 (Adjacency Matrix)

정점이 N개면 N×N 표를 만들고, matrix[i][j] = 1이면 i에서 j로 가는 간선이 있다는 뜻이다. "i와 j가 연결돼 있는가?"를 표 한 칸 조회로 바로 알 수 있어 간선 존재 확인이 O(1)이다. 대신 정점 수와 무관하게 항상 N² 칸을 다 차지하므로 공간이 O(V²) — 간선이 거의 없는 그래프에도 빈 칸이 낭비된다.

인접 리스트 (Adjacency List)

각 정점마다 자신과 연결된 정점들의 리스트만 들고 있는다. 실제로 존재하는 간선 수만큼만 저장하므로 공간이 O(V+E) — 정점 목록 V개 + 간선 기록 E개뿐이다. 다만 "i와 j가 연결됐나?"를 확인하려면 i의 리스트를 처음부터 훑어야 하므로 간선 존재 확인이 O(degree(i))로, 행렬보다 느릴 수 있다.

직접 편집해보기 — 행렬 · 리스트 · 그림, 동시에 바뀐다

밀집 vs 희소 그래프 — 메모리 트레이드오프

언제 뭘 쓰나

파이썬 코드로 보기

# 인접 리스트: 딕셔너리로 표현
graph_list = {
    'A': ['B', 'D'],
    'B': ['A', 'C'],
    'C': ['B'],
    'D': ['A'],
}

# "B와 C가 연결됐나?" → B의 리스트를 훑어야 함: O(degree)
if 'C' in graph_list['B']:
    print('연결됨')

# 인접 행렬: 2차원 리스트로 표현 (0=A, 1=B, 2=C, 3=D)
graph_matrix = [
    [0, 1, 0, 1],  # A: B, D 와 연결
    [1, 0, 1, 0],  # B: A, C 와 연결
    [0, 1, 0, 0],  # C: B 와 연결
    [1, 0, 0, 0],  # D: A 와 연결
]

# "B(1)와 C(2)가 연결됐나?" → 표 한 칸만 보면 됨: O(1)
if graph_matrix[1][2] == 1:
    print('연결됨')