Adjacency List (인접 리스트)

✅ 인접 리스트 (Adjacency List)

Adjacency List (인접 리스트)

 

1️⃣ 인접 리스트의 특징

그래프를 표현하는 또 다른 방법으로, 연결된 노드만 저장하는 방식입니다.

• 메모리 효율적: 필요한 간선만 저장하므로 **공간 복잡도가 O(N + E)**로 줄어듭니다.
• 연결 여부 확인 속도가 느림: 특정 두 노드가 연결되었는지 확인하려면 리스트를 탐색해야 하므로 O(N)의 시간이 걸립니다.

✅ 장점:

• 메모리를 절약할 수 있음 (O(N + E)) → 불필요한 공간 낭비 없이 저장 가능
• 노드가 많고 간선이 적은 경우(희소 그래프)에 유리

❌ 단점:

• 특정 노드 간 연결 여부 확인 속도가 느림 (O(N))
• 구현이 다소 복잡할 수 있음

 

---

 

2️⃣ 인접 리스트 예제 (양방향 그래프)

다음과 같은 그래프를 인접 리스트로 표현해보겠습니다.

예제 그래프

    (0) --- (1)
     |    /
     |   /
    (2)

이 그래프의 노드(0, 1, 2)와 간선(연결선)은 다음과 같습니다:

• 0번 노드 ↔ 1번 노드
• 0번 노드 ↔ 2번 노드
• 1번 노드 ↔ 2번 노드

✅ 인접 리스트 표현 (양방향 그래프)

# 그래프 표현 (0번 노드, 1번 노드, 2번 노드 연결)
graph = {
    0: [1, 2],  # 0번 노드는 1, 2번과 연결
    1: [0, 2],  # 1번 노드는 0, 2번과 연결
    2: [0, 1]   # 2번 노드는 0, 1번과 연결
}

출력하면 다음과 같은 딕셔너리 형태의 리스트가 생성됩니다.

{
    0: [1, 2],
    1: [0, 2],
    2: [0, 1]
}

 

---

 

3️⃣ 인접 리스트 예제 (단방향 그래프)

✅ 인접 리스트 표현 (단방향 그래프)

# 단방향 그래프 표현 (화살표 방향대로만 이동 가능)
graph = {
    0: [1, 2],  # 0번 노드 → 1, 2번 노드로 이동 가능
    1: [2],     # 1번 노드 → 2번 노드로 이동 가능
    2: []       # 2번 노드는 어디에도 갈 수 없음
}

출력하면 다음과 같은 딕셔너리가 생성됩니다:

{
    0: [1, 2],
    1: [2],
    2: []
}

 

---

 

4️⃣ 인접 리스트를 활용한 그래프 탐색

✅ BFS(너비 우선 탐색) 구현

from collections import deque

def bfs(graph, start):
    queue = deque([start])
    visited = set()
    visited.add(start)
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        for next_node in graph[node]:
            if next_node not in visited:
                queue.append(next_node)
                visited.add(next_node)
    
    print("BFS 탐색 순서:", *result)

# 그래프 입력
graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1]
}

bfs(graph, 0)

✅ 출력 결과

BFS 탐색 순서: 0 1 2

 

---

✅ DFS(깊이 우선 탐색) 구현

def dfs(graph, node, visited):
    visited.add(node)
    print(node, end=' ')
    for next_node in graph[node]:
        if next_node not in visited:
            dfs(graph, next_node, visited)

# 그래프 입력
graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1]
}

visited = set()
print("DFS 탐색 순서:", end=' ')
dfs(graph, 0, visited)

✅ 출력 결과

DFS 탐색 순서: 0 1 2

 

---

 

5️⃣ 인접 행렬 vs 인접 리스트 비교

방식	인접 행렬 (Adjacency Matrix)	인접 리스트 (Adjacency List)
공간 복잡도	O(N^2)	O(N + E)
연결 여부 확인 속도	O(1)	O(N)
메모리 효율성	낮음 (희소 그래프에 불리)	높음 (필요한 간선만 저장)
추천 사용 경우	노드 개수가 적고 간선이 많은 경우	노드 개수가 많고 간선이 적은 경우

 

---

 

마무리

인접 리스트는 그래프를 저장하는 메모리 효율적인 방식입니다.

특히 노드가 많고 간선이 적은 경우(희소 그래프)에서 매우 유리하며, 노드가 숫자가 아닌 이름(문자열)일 때도 더 직관적으로 사용할 수 있습니다.

다음 포스팅에서는 인접 리스트와 인접 행렬을 실제 사례에서 어떻게 적용할 수 있는지 비교해보겠습니다! 🚀

더 궁금한 점이 있다면 댓글로 남겨주세요! 😊