그래프 연습 (1) - 인접 행렬과 인접 리스트

그래프를 표현하는 방법은 대표적으로 두 가지가 있다.

 

1. 인접 행렬 (Adjacency Matrix)

 

인접 행렬은 그래프의 노드들 간의 연결 관계를 행렬로 표현한다. 행렬에서 행과 열은 그래프의 노드를 나타내고, 행렬의 각 요소는 해당 노드들 간의 연결을 나타낸다. 예를 들어, 1 행 2 열의 값은 노드 1과 2가 연결되어 있다는 것을 의미하고 값이 1이다(가중치가 없을경우). 따라서 그래프가 무방향이라 가정했을 때, 인접 행렬은 대칭적이다.

 

연결관계:

1 2
1 3
1 4
2 4
3 4

 

인접행렬:

   1 2 3 4
1 0 1 1 1
2 1 0 0 1
3 1 0 0 1
4 1 1 1 0

 

장점

• 직관적인 표현: 행렬을 사용하기 때문에 그래프의 연결 관계를 한눈에 파악하기 쉽다.
• 빠른 접근 시간: 특정 두 노드가 연결되어 있는지를 확인하는데 O(1)의 시간이 걸린다.
• 행렬 연산: 행렬을 사용하기 때문에 행렬 연산을 이용한 고급 그래프 알고리즘 구현이 가능하다.

단점

• 메모리 낭비: 노드가 많고 간선이 적은 희소 그래프(sparse graph)의 경우, 대부분의 행렬 요소가 0으로 채워지므로 메모리를 비효율적으로 사용한다.
• 간선 추가/삭제의 비효율성: 간선을 추가하거나 삭제할 때 행렬 전체를 업데이트해야 할 수 있다.

간단 구현

# 노드의 개수 (노드 1, 2, 3, 4를 가정하므로)
n = 4

# 인접 행렬 초기화 (0으로 채워진 4x4 행렬)
adj_matrix = [[0] * (n + 1) for _ in range(n + 1)]

# 연결 관계
edges = [
    (1, 2),
    (1, 3),
    (1, 4),
    (2, 4),
    (3, 4)
]

# 인접 행렬 채우기
for (i, j) in edges:
    adj_matrix[i][j] = 1
    adj_matrix[j][i] = 1  # 무방향 그래프이므로 양방향에 1을 채웁니다.

# 인접 행렬 출력
for row in adj_matrix[1:]:  # 0번 인덱스는 사용하지 않으므로 제외하고 출력
    print(row[1:])

결과:

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

---

2. 인접 리스트 (Adjacency List)

인접 리스트는 각 노드에 연결된 노드의 리스트를 할당하여 그래프를 표현한다. 이 방식은 노드별로 연결된 간선의 정보만을 저장한다.

 

연결관계:

1 2
1 3
1 4
2 4
3 4

 

인접리스트:

1: [2, 3, 4]
2: [1, 4]
3: [1, 4]
4: [1, 2, 3]

 

장점

• 메모리 효율성: 인접 리스트는 간선의 수에 비례하는 메모리만을 사용하므로, 희소 그래프를 표현하는데 효율적이다.
• 간선 추가/삭제 용이: 새로운 간선을 추가하거나 기존의 간선을 삭제하는 것이 인접 행렬에 비해 훨씬 쉽고 빠르다.

단점

• 빠른 접근 시간 부재: 특정 두 노드가 연결되어 있는지 확인하기 위해서는 해당 노드의 리스트를 순회해야 하므로 최악의 경우 O(N)의 시간이 걸릴 수 있다.
• 간선 검색 비효율성: 특정 간선의 존재를 확인하거나 가중치를 얻기 위해서는 해당 노드의 연결 리스트를 전부 탐색해야 한다.

간단 구현

n = 4

# 인접 리스트 초기화 (노드 1부터 시작하므로 n+1의 크기로 만듦)
adj_list = {i: [] for i in range(1, n + 1)}

# 연결 관계
edges = [
    (1, 2),
    (1, 3),
    (1, 4),
    (2, 4),
    (3, 4)
]

# 인접 리스트 채우기
for (i, j) in edges:
    adj_list[i].append(j)
    adj_list[j].append(i)  # 무방향 그래프이므로 양쪽에 추가

# 인접 리스트 출력
for key in adj_list:
    print(f"{key}: {adj_list[key]}")

결과:

1: [2, 3, 4]
2: [1, 4]
3: [1, 4]
4: [1, 2, 3]