🧵그래프를 표현하는 표현, 인접 리스트와 인접 행렬

관련글 : 

인접 리스트 생성, 변환 (+ 간선 입력)	https://waydd.tistory.com/23
인접 리스트, 인접 행렬 배열 초기화	https://waydd.tistory.com/153
행렬	https://waydd.tistory.com/14

 

 

1. 인접 리스트 (Adjacency List)

 

(공통) 그래프를 컴퓨터 내부에서 저장하는 자료구조로, 알고리즘(BFS, Dijkstra 등)의 기반이 됨

→ 동시에 그래프 알고리즘의 효율성을 좌우하는 핵심 기반 구조

• 각 노드에 연결된 이웃 노드를 리스트(딕셔너리) 로 저장
• 리스트 안에 리스트 또는 딕셔너리로 구현됨 ex) dict[ int, list[int]]  또는 list[ list[int] ], list[ list[tuple(int, int)] ](가중치)
  →  {정점: [이웃들]} 형태를 띔
• 메모리 사용(공간 복잡도, 전체 탐색) → O(V + E) (방향),  O(V + 2E) (무방향) : 간선 수만큼 메모리 사용(효율적)
  ※ O(V) : 각 정점을 위한 리스트 또는 딕셔너리, 즉 각 정점마다 리스트 하나
  ※ O(E) : 실제 간선을 표현하는 이웃 정점들 (리스트 항목들), 무방향 그래프면 간선 하나당 두개 저장되어 2E
  
• 간선 유무 탐색 속도(u와 v가 연결되어 있는지, 간선 확인) → 느림, O(정점의 차수)
  ex) 리스트 탐색, in 연산 (O(N))
• 간선 추가 → 평균 O(1) ( 리스트 끝에 추가하므로 )
  ex) graph[u].append(v)  (무방향일때는 양쪽 다 추가해야함)
• 간선 제거 → O(정점의 차수) ( 리스트에서 v를 찾아서 삭제해야 함 )
  ex) graph[u].remove(v)  (무방향일때는 양쪽 다 삭제 필요)
• 연결된 노드만 순회 → 희소 그래프에 적합함 (메모리 효율적)

# 예시 (가중치 X)
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0],
    3: [1]
}

# 가중치 인접 리스트
graph = {
    0: [(1, 2)],
    1: [(0, 2), (2, 3)],
    2: [(1, 3), (3, 4), (4, 1)],
    3: [(2, 4), (4, 6)],
    4: [(2, 1), (3, 6)]
}

※ 여기서 V : 정점(Vertex) 수, E : 간선(Edge) 수

※  인접 리스트 공간 복잡도와 특성
- 정점(V) 개수만큼 리스트 배열 생성 → O(V)
- 각 리스트에 간선(E) 정보 저장 → O(E)
- E가 적은 희소 그래프에서 효율적
- E가 많으면 인접 행렬과 비슷한 공간 차지하기 때문

※ 사용에 유리한 경우
- 이웃 정점 순회가 많을때 (해당 정점의 간선만 저장되어 있기 때문)
- 대부분의 트리 문제나 희소 그래프는 인접 리스트가 기본
- DFS/BFS 문제
- 가중치 그래프 전체 경로 필요 (다익스트라) →  우선순위 큐 사용 + 희소 그래프 대응 효율성

 

- A와 B 사이에 간선이 있는지(존재 여부) 확인 (느림)

graph = {
    'A': ['C', 'D'],
    'B': ['E'],
}

if 'B' in graph['A']:  # B가 A의 인접 리스트에 있는지 검색
# → 리스트 안에서 B를 직접 찾아야함 (O(정점 차수))

 

- 정점 A의 이웃 탐색 (빠름)

graph = {
    'A': ['B', 'C'],
    'B': ['A'],
}

for neighbor in graph['A']:  # A의 이웃만 바로 나옴
    print(neighbor)
# → A의 이웃만 저장되어 있음 
# → 바로 순회 가능 (O(정점 차수))

 

 

2. 인접 행렬 (Adjacency Matrix)

• 노드 간 연결 여부를 2차원 배열로 저장, 두 노드가 연결되어있으면 1(또는 가중치)
  → 간선 유무를 1(연결됨), 0(없음) 혹은 숫자(연결 + 가중치), INF(연결 없음) 으로 표현 가능
       자기 자신의 연결+가중치 표현이 0인 이유 : 자기 자신으로 가는 비용 = 0 (최단 경로)
  → 전자는 단순 연결 표현만 있기때문에 무가중치에만 적합, 후자는 가중치 그래프 표현에도 적합
• 2차원 배열 (N x N)로 구현  ex) list[ list[int] ] with 0/1
• 메모리 사용 → O(V²) : 정점 수 제곱 (메모리 많이 씀)
• 간선 유무 탐색 속도 → 빠름, O(1)
  ex) matrix[u][v] ( 바로 접근 )
• 간선 추가 → O(1) ( 2차원 배열에 인덱스로 접근 )
  ex) graph[u][v] = 1  (무방향일 경우엔 양쪽 다 추가)
• 간선 삭제 →  O(1) ( 추가와 동일하게, 배열 접근 )
  ex) graph[u][v] = 0  (무방향일 경우엔 양쪽 다 삭제)
• 모든 노드에 대해 직접 탐색 가능 → 조밀(혹은 밀집) 그래프에 적합 (연산 속도에 유리)

# 예시 (가중치 X)
graph = [
    [0, 1, 1, 0],  # 0번 정점
    [1, 0, 0, 1],  # 1번 정점
    [1, 0, 0, 0],  # 2번 정점
    [0, 1, 0, 0]   # 3번 정점
]

# 혹은 비연결을 INF로 표현 (가중치 인접 행렬)
INF = float('inf')
graph = [
    [0, 2, INF, INF, INF],
    [2, 0, 3, INF, INF],
    [INF, 3, 0, 4, 1],
    [INF, INF, 4, 0, 6],
    [INF, INF, 1, 6, 0]
]

※ 메모리를 많이 차지하지만 탐색 속도가 빠른 이유
- 인접 행렬은 정점 간 모든 관계를 2차원 배열로 저장
- 연결이 없더라도 0으로 공간을 차지하지만, 한 정점의 인접 정점 확인, 탐색 속도는 빠름
  (= 인덱스로 바로 접근, 연결 여부 확인 시 유리)

※ 사용에 유리한 경우
- 정점 수 적을 때(= 그래프가 작음) (V ≤ 1000) → 공간 문제 해소
- 간선이 많아서 대부분의 정점이 서로 연결되어 있을때(= dense) (E ≥ V² × 0.1 이상, 400,000 up)
  → 때문에 조밀 그래프에 써도 괜찮고, 완전그래프는 기본 (매번 리스트 탐색보다 빠름)
- u → v 간선 존재(연결) 여부를 자주 검사/즉시 확인해야할 때 (간선 탐색 속도가 빠름, O(1) 접근 가능)
- 간선 추가/삭제가 빈번
- 2차원 배열을 그대로 그래프로 보는 문제 (미로, 좌표 기반 등)
- 위와 연계한 특수한 BFS 문제(+ 0-1 BFS 등 DFS도 구현 가능하지만 비효율적)
  → 0-1 BFS : 가중치 0 or 1, 정점 수 적음, 연결 밀집 / 단순 연결 확인이 많은 문제 유형
  → 간선 가중치가 0 또는 1로 제한 : 우선순위 큐 없이 deque 하나로 충분함
- 모든 쌍 최단거리 필요, 완전 그래프 문제 (TSP, 플로이드-워셜)

 

- A와 B 사이에 간선이 있는지 확인 (빠름)

graph = [
    [0, 1, 0],  # A
    [1, 0, 0],  # B
    [0, 0, 0],  # C
] # 행렬은 0 또는 1로 간선 존재 여부 표현

graph[A][B] == 1  # → 바로 인덱스로 접근 (O(1))

 

- 정점 A의 이웃 탐색 (느림)

graph = [
    [0, 1, 1],  # A
    [1, 0, 0],  # B
    [1, 0, 0],  # C
]

for i in range(V):
    if graph[A][i] == 1:
        print(i)
# → 모든 정점 V개를 다 확인해야 함
# → 이웃이 적어도 행 전체(V)를 순회해야 함 (O(V))