그래프 표현 방법

6.1 인접 행렬: 작동 원리, 장점과 단점.

인접 행렬은 그래프를 크기 n x n의 정사각형 행렬로 나타내는 방법이야, 여기서 n은 그래프의 정점 수야. 행렬의 요소들은 정점들 간의 간선의 존재 여부를 나타내:

• 정점 i와 j 사이에 간선이 있으면, 요소 A[i][j] = 1 (가중치 그래프의 경우 간선의 가중치)로 표시돼.
• 간선이 없으면, A[i][j] = 0이야.

예시:

정점이 A, B, C이고 간선이 (A, B), (B, C), (C, A)인 그래프에 대해 인접 행렬은 다음과 같아:

모든 정점이 모두 연결되어 있다면 인접 행렬은 이렇게 보일 거야:

장점:

• 간단함: 이해하고 구현하기 쉬워.
• 빠른 접근: 두 정점 사이의 간선 존재 여부를 O(1)에 확인할 수 있어.
• 밀도가 높은 그래프에 적합: 많은 간선을 가진 그래프에 효율적이야.

단점:

• 높은 메모리 소모: 그래프에 간선이 거의 없더라도 O(n^2) 메모리가 필요해.
• 희소 그래프에 비효율적: 정점이 많고 간선이 적으면 대부분의 행렬 요소가 0이라 메모리 사용이 비효율적이야.

6.2 인접 리스트: 작동 원리, 장점과 단점.

인접 리스트는 그래프를 리스트 배열로 나타내는 방법이야. 배열의 각 요소는 그래프의 정점에 해당하고, 그와 인접한 모든 정점의 리스트를 포함해.

예시:

정점이 A, B, C이고 간선이 (A, B), (B, C), (C, A)인 그래프에 대해 인접 리스트는 다음과 같아:

모든 정점이 모두 연결되어 있다면 인접 리스트는 이렇게 보일 거야:

장점:

• 효율적인 메모리 사용: 정점 수 V와 간선 수 E에 대해 O(V + E) 메모리가 필요해, 그래서 희소 그래프에 더 적합해.
• 순회하기 쉬움: 그래프 탐색 작업(예: 너비 우선 탐색, 깊이 우선 탐색) 수행에 유리해.

단점:

• 복잡한 접근: 두 정점 사이의 간선 존재 여부 확인에 O(k) 시간이 필요해, 여기서 k는 정점의 이웃 수야.
• 덜 명확한 구조: 인접 행렬에 비해 구현과 이해가 더 복잡해.

6.3 다양한 그래프 표현 방식의 비교.

다양한 그래프 표현 방식을 비교해보자.

1. 인접 행렬:

• 간단함: 이해하고 구현하기 쉬워.
• 메모리: O(n^2) 메모리가 필요해서 희소 그래프에는 비효율적일 수 있어.
• 접근 속도: 간선 존재 여부를 O(1)에 확인할 수 있어.
• 적합: 많은 간선을 가진 밀도가 높은 그래프에 적합해.

2. 인접 리스트:

• 간단함: 인접 행렬보다 덜 명확하지만 이해 가능한 수준이야.
• 메모리: O(V + E) 메모리가 필요해서 희소 그래프에 더 효율적이야.
• 접근 속도: 간선 존재 여부를 O(k)에 확인할 수 있어, 여기서 k는 정점의 이웃 수야.
• 적합: 적은 간선을 가진 희소 그래프에 적합해.

비교:

인접 행렬은 대부분의 정점이 간선으로 연결된 밀도가 높은 그래프에 더 적합해, 간선 정보에 빠르게 접근할 수 있고 구현이 쉬워.

인접 리스트는 가능한 정점 쌍 수에 비해 간선의 수가 훨씬 적은 희소 그래프에 선호돼. 메모리 사용이 효율적이고, 그래프 탐색 작업에 유리해.