-
문제 9:
그래프 자료구조를 저장하는데 크게 Linked list를 이용하는 방법과 Adjacency matrix를 이용하는 방법이 있다. 각각의 장단점을 설명하시오.
1. Linked List (인접 리스트) 방식:
- 정의: 각 노드가 자신과 인접한 노드들을 연결 리스트로 저장하는 방식.
장점
- 공간 효율성: 간선이 적은 희소 그래프에서 사용 공간이 적음
- 동적 성격: 간선의 추가와 삭제가 쉬우며, 새로운 노드와의 연결을 삽입하는 데 시간 복잡도 \(O(1)\)로 효율적단점
- 간선 탐색 속도: 특정 노드 간 연결 여부를 확인하려면 리스트를 순차적으로 탐색해야 하므로, 최악의 경우 시간 복잡도는 \(O(n)\)
2. Adjacency Matrix (인접 행렬) 방식:
- 정의: 그래프의 노드들 간 연결 여부를 2차원 배열로 저장하는 방식
장점
- 빠른 탐색: 두 노드 간 간선이 존재하는지 확인하는 데 시간 복잡도는 \(O(1)\)
- 간선 상태 시각화: 행렬 형태로 전체 그래프의 연결 상태를 직관적으로 파악할 수 있음단점
- 공간 비효율성: 희소 그래프에서는 많은 메모리가 낭비될 수 있습니다. 간선이 없는 노드들 간의 값이 0으로 채워지기 때문에, \(O(n^2)\)의 공간 복잡도가 발생
- 간선 추가 및 삭제 어려움: 인접 리스트 방식보다 간선 추가 및 삭제가 복잡
문제 14
무향 그래프(undirected graph)와 유향 그래프(directed graph) 각각의 정의를 쓰시오. (50점)
1. 무향 그래프 (Undirected Graph)
- 정의: 노드들 간의 간선이 방향성을 가지지 않는 그래프입니다. 즉, 간선 \(A-B\)가 있으면, \(A\)에서 \(B\)로 이동하는 것과 \(B\)에서 \(A\)로 이동하는 것이 동일- 특징:
- 간선은 대칭적
만약 \(A\)와 \(B\) 사이에 간선이 존재하면 \(A \rightarrow B\)와 \(B \rightarrow A\)가 동일한 간선으로 처리
- 인접 행렬에서 \(A[i][j] = A[j][i]\)가 성립합니다.
2. 유향 그래프 (Directed Graph)
- 정의: 노드들 간의 간선이 방향성을 가지는 그래프입니다. 즉, 간선 \(A \rightarrow B\)가 있을 경우, \(B \rightarrow A\)는 다른 간선으로 처리- 특징:
- 간선의 방향이 존재하기 때문에, 노드 사이의 경로가 일방적일 수 있음
- 인접 행렬에서 대칭이 아닐 수 있으며, \(A[i][j] \neq A[j][i]\)일 수 있음
문제 16:
그래프를 표현하는 방법들 중에서 인접 행렬(Adjacency Matrix) 방식이 무엇인지를 노드와 간선이 각각 네 개인 무향 그래프(Undirected graph)를 예로 들어 설명하시오. (40점)
1. 인접 행렬 (Adjacency Matrix) 정의:
- 인접 행렬은 그래프를 2차원 배열로 표현하는 방법
- 행렬의 크기는 그래프의 노드 수에 따라 결정되며, 노드의 개수가 \(n\)개일 경우, 행렬의 크기는 \(n \times n\)
- 만약 노드 \(i\)와 노드 \(j\) 사이에 간선이 존재하면, \(A[i][j]\)의 값은 1이 되고, 간선이 없으면 0
- 무향 그래프의 경우, \(A[i][j]\)와 \(A[j][i]\)가 동일합니다. 즉, 대칭적인 행렬을 이룸
2. 예시 (노드와 간선이 네 개인 무향 그래프):
4개의 노드가 있는 무향 그래프에서 예시
노드 : 1, 2, 3, 4
간선 : (1-2), (1-3), (2-4)
\[
A = \begin{pmatrix}
0 & 1 & 1 & 0 \\
1 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
\end{pmatrix}
\]
여기서,
- \(A[1][2] = 1\), \(A[2][1] = 1\)은 노드 1과 노드 2 사이에 간선이 있음을 나타냄
- \(A[1][3] = 1\), \(A[3][1] = 1\)은 노드 1과 노드 3 사이에 간선이 있음을 나타냄
- \(A[2][4] = 1\), \(A[4][2] = 1\)은 노드 2와 노드 4 사이에 간선이 있음을 나타냄
3. 장점
- 인접 행렬은 행렬을 통해 그래프의 연결 상태를 쉽게 확인할 수 있음
- 노드 사이에 간선이 있는지 여부를 \(O(1)\) 시간 복잡도로 빠르게 확인할 수 있음
4. 단점:
- 노드가 많은 희소 그래프(Sparse Graph)일 경우, 대부분의 값이 0이기 때문에 공간 낭비가 발생할 수 있습니다. 이 경우 인접 리스트(Adjacency List) 방식이 더 효율적